個案研究：評估表達式

堆疊可用來計算表達式。堆疊和佇列有很多應用。本節提供了一個使用堆疊來計算表達式的應用程式。您可以輸入來自Google的算術表達式來計算該表達式，如下圖所示。

Google 如何評估表達式？本節介紹一個程序，用於計算具有多個運算符和括號的 複合表達式 （例如 (15 + 2) * 34 – 2）。為簡單起見，假設運算元為整數，運算子有四種：+、-、** 和*/ .

這個問題可以使用兩個堆疊來解決，分別命名為operandStack和operatorStack，分別用於儲存運算元和運算子。操作數和運算子在處理之前被推入堆疊。當處理 運算子 時，它會從operatorStack 中彈出，並應用於operandStack 中的前兩個操作數（這兩個操作數從operandStack 中的前兩個操作數（這兩個操作數從operandStack）。結果值被推回operandStack

.

演算法分兩個階段進行：

第一階段：掃描表達式

程式從左到右掃描表達式以提取運算元、運算子和括號。

1. 如果提取的項目是操作數，則將其推送到 operandStack
。
2. 如果提取的項是+ 或- 運算符，則處理operatorStack 頂部的所有運算符，並將提取的運算符壓入運算符棧
.
3. 如果提取的項目是***** 或/ 運算符，則處理operatorStack/ 運算符>並將擷取的運算子推送到operatorStack.
4. 如果提取的項是 ( 符號，則將其推送到 operatorStack.
5. 如果提取的項是) 符號，則從operatorStack 頂部開始重複處理運算符，直到在堆疊上看到(符號。

第 2 階段：清除堆疊

從operatorStack頂部開始重複處理操作符，直到operatorStack為空。

下表顯示如何應用此演算法計算表達式 (1 + 2) * 4 - 3.

下面的程式碼給出了程序，下圖顯示了一些範例輸出。

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;
    }

}

您可以使用本書提供的GenericStack類別或Java API中定義的java.util.Stack類別來建立堆疊。此範例使用 java.util.Stack 類別。如果將其替換為 GenericStack.

，程式將運行。

程式將表達式作為一個字串中的命令列參數。

evaluateExpression 方法建立兩個堆疊，operandStack 和operatorStack（第24、27 行），並提取由空格分隔的操作數、運算符和括號（第30-33 行）。 insertBlanks 方法用於確保運算元、運算子和括號之間至少有一個空格分隔（第 30 行）。

程式掃描 for 循環中的每個標記（第 36-72 行）。如果標記為空，則跳過它（第 38 行）。如果令牌是操作數，則將其推送到 operandStack（第 70 行）。如果令牌是+ 或– 運算子（第39 行），則處理operatorStack 頂部的所有運算子（如果有）（第41-43行） ，並將新掃描的運算子推入堆疊（第46 行）。如果令牌是***** 或/ 運算子（第48 行），則處理operatorStack/ 運算符🎜>，如果有的話（第50-51 行），並將新掃描的運算子推入堆疊（第55 行）。如果令牌是( 符號（第57 行），則將其推入operatorStack。如果令牌是) 符號（第60 行），則處理從operatorStack 直到看到) 符號（第62-64 行），然後從堆疊中彈出) 符號。

考慮完所有標記後，程式將處理 operatorStack 中剩餘的運算子（第 75-77 行）。

processAnOperator 方法（第 84-96 行）處理一個運算子。此方法從 operatorStack 中彈出運算子（第 85 行），並從 operandStack 中彈出兩個操作數（第 86-87 行）。根據運算符，此方法執行操作並將操作結果推送回 operandStack（第 89、91、93、95 行）。

以上是個案研究：評估表達式的詳細內容。更多資訊請關注PHP中文網其他相關文章！