用栈结构实现表达式求值

表达式求值可以使用栈实现。具体步骤如下：

1. 创建一个操作数栈和一个操作符栈。

2. 遍历表达式中的每个字符，如果是操作数，则将其推入操作数栈中；如果是操作符，则将其推入操作符栈中。

3. 如果遇到左括号，则将其推入操作符栈中。

4. 如果遇到右括号，则取出操作符栈中的顶部元素进行计算，直到遇到左括号为止。每次计算后将结果推入操作数栈中。

5. 如果遇到操作符，先判断操作符栈顶的操作符优先级是否大于等于当前操作符的优先级，如果是，则取出操作符栈顶元素进行计算，并将结果推入操作数栈中，直到操作符栈顶的操作符优先级小于当前操作符的优先级，或者操作符栈为空为止。

6. 遍历完表达式后，如果操作符栈不为空，则取出操作符栈顶元素进行计算，并将结果推入操作数栈中，直到操作符栈为空。

7. 最终操作数栈中只剩下一个元素，即为表达式的值。

下面是使用 Java 代码实现：

import java.util.Stack;

public class ExpressionEvaluation {
    public static int evaluate(String expression) {
        Stack<Integer> operandStack = new Stack<>();
        Stack<Character> operatorStack = new Stack<>();
        
        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);
            
            if (ch == ' ') {  // 忽略空格
                continue;
            } else 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--;
                operandStack.push(operand);
            } else if (ch == '(') {  // 如果是左括号，将其入栈
                operatorStack.push(ch);
            } else if (ch == ')') {  // 如果是右括号，计算括号内的表达式
                while (operatorStack.peek() != '(') {
                    int result = calculate(operatorStack.pop(), operandStack.pop(), operandStack.pop());
                    operandStack.push(result);
                }
                operatorStack.pop();  // 弹出左括号
            } else if (isOperator(ch)) {  // 如果是操作符
                while (!operatorStack.isEmpty() && operatorStack.peek() != '(' && hasPriority(operatorStack.peek(), ch)) {
                    int result = calculate(operatorStack.pop(), operandStack.pop(), operandStack.pop());
                    operandStack.push(result);
                }
                operatorStack.push(ch);
            }
        }
        
        while (!operatorStack.isEmpty()) {  // 计算剩余的操作符
            int result = calculate(operatorStack.pop(), operandStack.pop(), operandStack.pop());
            operandStack.push(result);
        }
        
        return operandStack.pop();  // 返回最终结果
    }
    
    private static boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    }
    
    private static boolean hasPriority(char op1, char op2) {
        if (op1 == '*' || op1 == '/') {
            return true;
        } else if (op1 == '+' || op1 == '-') {
            return op2 == '+' || op2 == '-';
        } else {
            return false;
        }
    }
    
    private static int calculate(char operator, int operand2, int operand1) {
        if (operator == '+') {
            return operand1 + operand2;
        } else if (operator == '-') {
            return operand1 - operand2;
        } else if (operator == '*') {
            return operand1 * operand2;
        } else {
            return operand1 / operand2;
        }
    }
    
    public static void main(String[] args) {
        String expression = "2 * (3 + 4) - 5 / 2";
        int result = evaluate(expression);
        System.out.println(expression + " = " + result);
    }
}

输出结果为：

2 * (3 + 4) - 5 / 2 = 11