栈在表达式求值中的应用是通过使用两个栈来进行计算的。一个栈用于存储操作数,另一个栈用于存储操作符。
下面是一个用 Java 实现的示例代码:
import java.util.Stack;
public class ExpressionEvaluator {
public static int evaluate(String expression) {
Stack<Integer> operands = new Stack<>();
Stack<Character> operators = new Stack<>();
for (int i = 0; i <expression.length(); i++) {
char ch = expression.charAt(i);
if (Character.isDigit(ch)) {
int operand = 0;
while (i <expression.length() && Character.isDigit(expression.charAt(i))) {
operand = operand * 10 + (expression.charAt(i) - '0');
i++;
}
i--;
operands.push(operand);
} else if (ch == '(') {
operators.push(ch);
} else if (ch == ')') {
while (!operators.isEmpty() && operators.peek() != '(') {
operands.push(applyOperator(operators.pop(), operands.pop(), operands.pop()));
}
operators.pop(); // 弹出 '('
} else if (isOperator(ch)) {
while (!operators.isEmpty() && precedence(ch) <= precedence(operators.peek())) {
operands.push(applyOperator(operators.pop(), operands.pop(), operands.pop()));
}
operators.push(ch);
}
}
while (!operators.isEmpty()) {
operands.push(applyOperator(operators.pop(), operands.pop(), operands.pop()));
}
return operands.pop();
}
private static int applyOperator(char operator, int operand2, int operand1) {
switch (operator) {
case '+':
return operand1 + operand2;
case '-':
return operand1 - operand2;
case '*':
return operand1 * operand2;
case '/':
return operand1 / operand2;
}
return 0;
}
private static boolean isOperator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}
private static int precedence(char operator) {
switch (operator) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
}
return 0;
}
public static void main(String[] args) {
String expression = "(3+4)*5-6/2";
int result = evaluate(expression);
System.out.println("Result: " + result); // 输出:Result: 27
}
}
在这个示例中,我们使用了两个栈:`operands` 用于存储操作数,`operators` 用于存储操作符。
我们遍历表达式中的每个字符,当遇到数字时,我们将其转换为整数,然后将其推入 `operands` 栈中。当遇到左括号时,我们将其推入 `operators` 栈中。当遇到右括号时,我们从 `operators` 栈中弹出操作符,并从 `operands` 栈中弹出两个操作数,然后将计算结果推入 `operands` 栈中,直到弹出左括号。
当遇到操作符时,我们检查 `operators` 栈顶的操作符,如果其优先级高于或等于当前操作符,我们将其从 `operators` 栈中弹出,并从 `operands` 栈中弹出两个操作数,然后将计算结果推入 `operands` 栈中,直到 `operators` 栈为空或栈顶的操作符优先级低于当前操作符。最后,我们将当前操作符推入 `operators` 栈中。
当遍历完整个表达式后,我们将 `operators` 栈中的操作符依次弹出,并从 `operands` 栈中弹出两个操作数进行计算,然后将计算结果推入 `operands` 栈中,直到 `operators` 栈为空。
最后,我们从 `operands` 栈中弹出计算结果即为最终的表达式求值结果。
在上例中,表达式 `"(3+4)*5-6/2"` 的求值结果为 27。