如何用栈计算逆波兰表达式（后缀表达式）？中缀又怎么转后缀？

简化版

逆波兰（后缀）表达式求值用一个栈：遇到数字入栈，遇到运算符就弹出栈顶两个数做运算、结果再压回栈，最后栈里剩的就是答案。中缀转后缀（调度场算法）也用栈处理运算符优先级。栈之所以适合，是因为运算符总是作用于「最近的两个操作数」，正是后进先出。

详细版

逆波兰表达式（RPN） 把运算符写在操作数后面，如 3 4 + 2 * 表示 (3+4)*2。它没有括号、没有优先级歧义，天生适合栈求值：

int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (String t : tokens) {
        switch (t) {
            case "+": case "-": case "*": case "/": {
                int b = stack.pop(), a = stack.pop();   // 注意顺序：先弹的是右操作数
                stack.push(apply(a, b, t));
                break;
            }
            default: stack.push(Integer.parseInt(t));   // 数字入栈
        }
    }
    return stack.pop();
}
int apply(int a, int b, String op) {
    return switch (op) {
        case "+" -> a + b;  case "-" -> a - b;
        case "*" -> a * b;  default  -> a / b;
    };
}

关键坑：对 - 和 / 这类不满足交换律的运算，先弹出的是右操作数 b，后弹出的是左操作数 a，必须算 a - b、a / b，顺序反了就错。

完整版教学

一、为什么栈能求后缀表达式

后缀表达式的规则是「运算符紧跟在它的两个操作数之后」。当你从左往右扫，遇到运算符时，它要用的两个操作数一定是刚刚出现的、离它最近的两个数——也就是栈顶的两个。用完把结果压回，继续往后。这种「就近取最新的两个操作数」正是后进先出，所以栈是最自然的工具，一趟 O(n) 就能算完，且不需要处理括号和优先级（后缀表达式已经把优先级信息编码进了顺序里）。

二、求值过程走一遍

tokens = ["3","4","+","2","*"]   （即 (3+4)*2）
"3" → 栈: [3]
"4" → 栈: [3,4]
"+" → 弹 4、3，算 3+4=7，压回 → 栈: [7]
"2" → 栈: [7,2]
"*" → 弹 2、7，算 7*2=14，压回 → 栈: [14]
结束，栈顶 14 即答案

三、为什么用后缀而不是直接算中缀

我们平时写的是中缀表达式（(3+4)*2），运算符在中间，需要括号和优先级规则才能确定运算顺序，直接求值要处理这些，较复杂。而后缀表达式没有括号、没有优先级歧义，一个栈线性扫描即可。所以编译器/计算器常先把中缀转成后缀（或前缀），再求值。

四、中缀转后缀：调度场算法

Dijkstra 的**调度场算法（Shunting Yard）**用一个「运算符栈」把中缀转后缀：

遇到操作数：直接输出到结果。
遇到运算符 op：把栈里优先级 ≥ op 的运算符先弹出到结果，再把 op 入栈。
遇到左括号 (：入栈。
遇到右括号 )：不断弹出运算符到结果，直到遇到 (，丢弃这对括号。
扫描结束：把栈里剩余运算符全部弹出到结果。

核心还是用栈处理优先级：高优先级的运算符先被输出，从而在后缀里排到前面先计算。

五、复杂度与应用

求值：时间 O(n)、空间 O(n)。
应用：计算器、编译器表达式解析、公式引擎。很多脚本语言/数据库的表达式求值内部都是「中缀→后缀→栈求值」这套流程。

六、常见误区与追问

token 类型	栈操作	例子
数字	入栈	读到 `4`，push 4
二元运算符	弹出两个操作数再计算	`a op b`
表达式结束	栈中应剩 1 个结果	`((2+1)*3)=9`

记忆钩子：后缀表达式把“运算符什么时候执行”写在 token 顺序里，所以遇到运算符时，栈顶两个数就是它需要的操作数。

以 ["2","1","+","3","*"] 为例：读到 2、1 入栈；遇到 + 弹出 1 和 2，得到 3 入栈；读到 3 入栈；遇到 * 弹出 3 和 3，得到 9。整个过程每个 token 只进出栈常数次，所以时间 O(n)、空间最坏 O(n)。

误区：弹出的第一个数一定是左操作数。 对减法和除法，先弹出的是右操作数 b，再弹出的是左操作数 a，计算 a-b 或 a/b。
误区：后缀表达式还需要括号。 运算顺序已经由 token 顺序表达，不需要括号来改变优先级。
误区：所有运算都满足交换律。 加法乘法顺序影响不大，减法除法顺序错了结果就错。
追问：为什么栈适合求后缀表达式？ 最近出现的两个未被消费的值，正好是当前运算符的操作数，符合 LIFO。
追问：中缀表达式为什么更难直接求？ 要处理括号和运算符优先级，通常需要两个栈或先转后缀。
追问：表达式非法怎么处理？ 遇到运算符时栈元素不足、结束后栈里不止一个结果，都说明表达式不合法。

七、加强记忆

后缀（逆波兰）表达式求值用栈：数字入栈，运算符弹两个算完再压回，最后栈顶是答案，O(n) 且无需处理括号优先级——因为运算符总作用于最近两个操作数（LIFO）。减法/除法要注意先弹的是右操作数。中缀转后缀用调度场算法（运算符栈按优先级弹出）。栈适配是因为表达式求值本质就是就近取最新操作数。

简化版

详细版