堆疊可用來計算表達式。堆疊和佇列有很多應用。本節提供了一個使用堆疊來計算表達式的應用程式。您可以輸入來自Google的算術表達式來計算該表達式，如下圖所示。
Google 如何評估表達式？本節介紹一個程序，用於計算具有多個運算符和括號的 複合表達式 （例如 (15 + 2) * 34 – 2）。為簡單起見，假設運算元為整數，運算子有四種：+、-、** 和*/ .
這個問題可以使用兩個堆疊來解決，分別命名為operandStack和operatorStack，分別用於儲存運算元和運算子。操作數和運算子在處理之前被推入堆疊。當處理 運算子 時，它會從operatorStack 中彈出，並應用於operandStack 中的前兩個操作數（這兩個操作數從operandStack 中的前兩個操作數（這兩個操作數從operandStack）。結果值被推回operandStack
.演算法分兩個階段進行：
程式從左到右掃描表達式以提取運算元、運算子和括號。
從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中文網其他相關文章！
