用栈实现简单表达式求值

算法思路：

- 遍历表达式中的每一个字符：
- 如果字符是数字，将其转化为数字后入栈。
- 如果字符是运算符，弹出栈顶的两个数字进行计算，计算结果入栈。
- 遍历结束后，栈内剩下的唯一元素即为表达式的计算结果。

代码实现：

import java.util.Stack;

public class ExpressionEvaluation {
    public int evaluate(String expression) {
        Stack<Integer> operandStack = new Stack<>();
        Stack<Character> operatorStack = new Stack<>();
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (Character.isDigit(c)) {
                operandStack.push(Character.getNumericValue(c));
            } else if (c == '+' || c == '-') {
                while (!operatorStack.isEmpty() && (operatorStack.peek() == '+' || operatorStack.peek() == '-')) {
                    char operator = operatorStack.pop();
                    int operand2 = operandStack.pop();
                    int operand1 = operandStack.pop();
                    int result = applyOperation(operator, operand1, operand2);
                    operandStack.push(result);
                }
                operatorStack.push(c);
            } else if (c == '*' || c == '/') {
                while (!operatorStack.isEmpty() && (operatorStack.peek() == '*' || operatorStack.peek() == '/')) {
                    char operator = operatorStack.pop();
                    int operand2 = operandStack.pop();
                    int operand1 = operandStack.pop();
                    int result = applyOperation(operator, operand1, operand2);
                    operandStack.push(result);
                }
                operatorStack.push(c);
            }
        }
        while (!operatorStack.isEmpty()) {
            char operator = operatorStack.pop();
            int operand2 = operandStack.pop();
            int operand1 = operandStack.pop();
            int result = applyOperation(operator, operand1, operand2);
            operandStack.push(result);
        }
        return operandStack.pop();
    }

    private int applyOperation(char operator, int operand1, int operand2) {
        if (operator == '+') {
            return operand1 + operand2;
        } else if (operator == '-') {
            return operand1 - operand2;
        } else if (operator == '*') {
            return operand1 * operand2;
        } else if (operator == '/') {
            return operand1 / operand2;
        } else {
            throw new IllegalArgumentException("Invalid operator: " + operator);
        }
    }
}

使用样例：

ExpressionEvaluation expressionEvaluation = new ExpressionEvaluation();
int result = expressionEvaluation.evaluate("2 + 3 * 4 - 5");
System.out.println(result); // Output: 9