Fallstudie: Ausdrücke auswerten

Stacks können zur Auswertung von Ausdrücken verwendet werden. Stapel und Warteschlangen haben viele Anwendungen. In diesem Abschnitt wird eine Anwendung vorgestellt, die Stapel zum Auswerten von Ausdrücken verwendet. Sie können einen arithmetischen Ausdruck von Google eingeben, um den Ausdruck auszuwerten, wie in der Abbildung unten gezeigt.

Wie wertet Google einen Ausdruck aus? In diesem Abschnitt wird ein Programm vorgestellt, das einen zusammengesetzten Ausdruck mit mehreren Operatoren und Klammern auswertet (z. B. (15 + 2) * 34 – 2). Nehmen Sie der Einfachheit halber an, dass die Operanden ganze Zahlen sind und die Operatoren vier Typen haben: +, -, ** und */.

Das Problem kann mithilfe von zwei Stapeln mit den Namen operandStack und operatorStack zum Speichern von Operanden bzw. Operatoren gelöst werden. Operanden und Operatoren werden vor ihrer Verarbeitung in die Stapel verschoben. Wenn ein Operator verarbeitet wird, wird er aus operatorStack entnommen und auf die ersten beiden Operanden aus operandStack angewendet (die beiden Operanden werden aus operandStack). Der resultierende Wert wird an operandStack zurückgeschoben.

Der Algorithmus läuft in zwei Phasen ab:

Phase 1: Scannen des Ausdrucks

Das Programm durchsucht den Ausdruck von links nach rechts, um Operanden, Operatoren und Klammern zu extrahieren.

Wenn das extrahierte Element ein Operand ist, verschieben Sie es in
1. operandStack.
Wenn das extrahierte Element ein
2. +- oder --Operator ist, verarbeiten Sie alle Operatoren oben im operatorStack und verschieben Sie den extrahierten Operator nach OperatorStack.
Wenn das extrahierte Element ein *****- oder
3. /-Operator ist, verarbeiten Sie die *****- oder /-Operatoren oben im operatorStack und schieben Sie den extrahierten Operator nach operatorStack.
Wenn das extrahierte Element ein
4. (-Symbol ist, schieben Sie es auf operatorStack.
Wenn das extrahierte Element ein
5. )-Symbol ist, verarbeiten Sie die Operatoren von oben im operatorStack wiederholt, bis Sie das Symbol ( auf dem Stapel sehen.

Phase 2: Aufräumen des Stapels

Verarbeiten Sie wiederholt die Operatoren von oben im

operatorStack, bis operatorStack leer ist.

Die folgende Tabelle zeigt, wie der Algorithmus angewendet wird, um den Ausdruck

(1 + 2) * 4 - 3 auszuwerten.

Der Code unten gibt das Programm wieder, und die Abbildung unten zeigt einige Beispielausgaben.

package demo;
import java.util.Stack;

public class EvaluateExpression {

    public static void main(String[] args) {
        // Check number of arguments passed
        if(args.length != 1) {
            System.out.println("Usage: java EvaluateExpression \"expression\"");
            System.exit(1);
        }

        try {
            System.out.println(evaluateExpression(args[0]));
        }
        catch(Exception ex) {
            System.out.println("Wrong expression: " + args[0]);
        }
    }

    /** Evaluate an expression */
    public static int evaluateExpression(String expression) {
        // Create operandStack to store operands
        Stack<Integer> operandStack = new Stack<>();

        // Create operatorStack to store operators
        Stack<Character> operatorStack = new Stack<>();

        // Insert blanks around (, ), +, -, /, and *
        expression = insertBlanks(expression);

        // Extract operands and operators
        String[] tokens = expression.split(" ");

        // Phase 1: Scan tokens
        for(String token: tokens) {
            if(token.length() == 0) // Blank space
                continue; // Back to the while loop to extract the next token
            else if(token.charAt(0) == '+' || token.charAt(0) == '-') {
                // Process all +, -, *, / in the top of the operator stack
                while(!operatorStack.isEmpty() && (operatorStack.peek() == '+' || operatorStack.peek() == '-' || operatorStack.peek() == '*' || operatorStack.peek() == '/')) {
                    processAnOperator(operandStack, operatorStack);
                }

                // Push the + or - operator into the operator stack
                operatorStack.push(token.charAt(0));
            }
            else if(token.charAt(0) == '*' || token.charAt(0) == '/') {
                // Process all *, / in the top of the operator stack
                while(!operatorStack.isEmpty() && (operatorStack.peek() == '*' || operatorStack.peek() == '/')) {
                    processAnOperator(operandStack, operatorStack);
                }

                // Push the * or / operator into the operator stack
                operatorStack.push(token.charAt(0));
            }
            else if(token.trim().charAt(0) == '(') {
                operatorStack.push('('); // Push '(' to stack
            }
            else if(token.trim().charAt(0) == ')') {
                // Process all the operators in the stack until seeing '('
                while(operatorStack.peek() != '(') {
                    processAnOperator(operandStack, operatorStack);
                }

                operatorStack.pop(); // Pop the '(' symbol from the stack
            }
            else {
                // Push an operand to the stack
                operandStack.push(Integer.valueOf(token));
            }
        }

        // Phase 2: Process all the remaining operators in the stack
        while(!operatorStack.isEmpty()) {
            processAnOperator(operandStack, operatorStack);
        }

        // Return the result
        return operandStack.pop();
    }

    /** Process one operator: Take an operator from operatorStack and apply it on the operands in the operandStack */
    public static void processAnOperator(Stack<Integer> operandStack, Stack<Character> operatorStack) {
        char op = operatorStack.pop();
        int op1 = operandStack.pop();
        int op2 = operandStack.pop();
        if(op == '+')
            operandStack.push(op2 + op1);
        else if(op == '-')
            operandStack.push(op2 - op1);
        else if(op == '*')
            operandStack.push(op2 * op1);
        else if(op == '/')
            operandStack.push(op2 / op1);
    }

    public static String insertBlanks(String s) {
        String result = "";

        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(' || s.charAt(i) == ')' || s.charAt(i) == '+' || s.charAt(i) == '-' || s.charAt(i) == '*' || s.charAt(i) == '/')
                result += " " + s.charAt(i) + " ";
            else
                result += s.charAt(i);
        }

        return result;
    }

}

Sie können die im Buch bereitgestellte Klasse

GenericStack oder die in der Java-API definierte Klasse java.util.Stack zum Erstellen von Stapeln verwenden. In diesem Beispiel wird die Klasse java.util.Stack verwendet. Das Programm funktioniert, wenn es durch GenericStack. ersetzt wird

Das Programm akzeptiert einen Ausdruck als Befehlszeilenargument in einer Zeichenfolge.

Die Methode

evaluateExpression erstellt zwei Stapel, operandStack und operatorStack (Zeilen 24, 27) und extrahiert durch Leerzeichen getrennte Operanden, Operatoren und Klammern ( Zeilen 30–33). Mit der Methode insertBlanks wird sichergestellt, dass Operanden, Operatoren und Klammern durch mindestens ein Leerzeichen getrennt sind (Zeile 30).

Das Programm scannt jedes Token in der

for-Schleife (Zeilen 36–72). Wenn ein Token leer ist, überspringen Sie es (Zeile 38). Wenn ein Token ein Operand ist, verschieben Sie ihn auf operandStack (Zeile 70). Wenn ein Token ein +- oder –-Operator ist (Zeile 39), verarbeiten Sie alle Operatoren von oben im operatorStack, falls vorhanden (Zeilen 41–43). , und schieben Sie den neu gescannten Operator in den Stapel (Zeile 46). Wenn ein Token ein *****- oder /-Operator ist (Zeile 48), verarbeiten Sie alle *****- und /-Operatoren von oben im operatorStack, falls vorhanden (Zeilen 50–51), und schieben Sie den neu gescannten Operator auf den Stapel (Zeile 55). Wenn ein Token ein (-Symbol (Zeile 57) ist, schieben Sie es in operatorStack. Wenn ein Token ein )-Symbol ist (Zeile 60), verarbeiten Sie alle Operatoren von oben in operatorStack, bis Sie das Symbol ) sehen (Zeilen 62–64) und das Symbol ) aus dem Stapel entfernen.

Nachdem alle Token berücksichtigt wurden, verarbeitet das Programm die verbleibenden Operatoren in operatorStack (Zeilen 75–77).

Die Methode processAnOperator (Zeilen 84–96) verarbeitet einen Operator. Die Methode entfernt den Operator aus operatorStack (Zeile 85) und zwei Operanden aus operandStack (Zeilen 86–87). Abhängig vom Operator führt die Methode eine Operation aus und schiebt das Ergebnis der Operation zurück an operandStack (Zeilen 89, 91, 93, 95).

Das obige ist der detaillierte Inhalt vonFallstudie: Ausdrücke auswerten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!