逆波兰表达式求值 · 栈扫描后缀表达式

栈 · 后缀表达式

从左到右扫描 tokens：数字入栈，运算符弹出栈顶两个数计算 left op right 后再压回栈。逆波兰表达式不需要括号，也不需要运算符优先级。

当前输入

tokens = ["2","1","+","3","*"]

先算 2+1=3,再乘 3 → 9

最终答案

栈中唯一元素

复杂度

时间 O(n) — 每个 token 处理一次

空间 O(n) — 操作数栈

两个测试用例 · 经典 vs 操作数顺序

① 题目

后缀表达式 + 无需优先级

② 逐步扫描

push / pop left & right

③ 结论

栈剩唯一答案

Step 1/12 · 题目

题目 · 逆波兰表达式求值

当前发生了什么

题目 · 逆波兰表达式求值

给定 token 数组 ["2","1","+","3","*"]，从左到右扫描。数字直接入栈；运算符弹出栈顶两个数，计算后再压回栈。最终栈中唯一元素就是答案。

机器状态

当前 token: —
栈深度: 0
栈顶元素: —
right（右操作数）: —
left（左操作数）: —
计算结果: —

为什么正确

后缀表达式的运算符永远出现在它的两个操作数之后，所以扫描到运算符时，栈顶两个值一定就是它的左右操作数。

面试该怎么说 · 开题：这题用栈，顺序扫描 tokens，数字 push，运算符 pop 两次算完 push。

执行轨迹 · Token 流 + 操作数栈

tokens (左 → 右扫描)

操作数栈 (栈顶在右)

[ ] 空栈

执行轨迹

stack = []

Go 代码 · pop 顺序

题目

重点：第一次 pop → right，第二次 pop → left，然后 left op right

1func evalRPN(tokens []string) int {
2    stack := []int{}
3    ops := map[string]bool{"+": true, "-": true, "*": true, "/": true}
4 
5    for _, token := range tokens {
6        if !ops[token] {
7            num, _ := strconv.Atoi(token)
8            stack = append(stack, num)
9            continue
10        }
11 
12        right := stack[len(stack)-1]
13        stack = stack[:len(stack)-1]
14        left := stack[len(stack)-1]
15        stack = stack[:len(stack)-1]
16 
17        switch token {
18        case "+":
19            stack = append(stack, left+right)
20        case "-":
21            stack = append(stack, left-right)
22        case "*":
23            stack = append(stack, left*right)
24        case "/":
25            stack = append(stack, left/right)
26        }
27    }
28    return stack[0]
29}

不变量

尚未开始扫描，栈为空。

剧本时间线 · 共 12 步

为什么不用处理优先级？

逆波兰表达式是后缀表达式：运算符出现在两个操作数之后。

所以每遇到一个运算符，栈顶两个值一定就是它的左右操作数。因此不需要括号、不需要运算符优先级、不需要递归解析表达式。

中缀: 3 + 4 × 2 → 需要先算 4×2

后缀: ["3","4","2","*","+"] → 读到 + 时栈顶已是 3 和 8

面试怎么答

这题用栈。顺序扫描 tokens，遇到数字就转 int 入栈；遇到运算符就弹出两个数，注意第一次弹出的是右操作数，第二次弹出的是左操作数，计算 left op right 后把结果压回栈。逆波兰表达式保证每个运算符出现时，它的两个操作数已经在栈顶，所以不需要处理括号和优先级。最终栈里唯一的元素就是答案。时间 O(n)，空间 O(n)。

常见误区

✗ 错误「减除顺序：第二个弹出的是右操作数」
✓ 正确减法和除法顺序：第一次 pop 出来的是右操作数，第二次 pop 出来的是左操作数。示例：right = stack.pop(); left = stack.pop(); result = left op right

right = stack.pop()   // 第一次 pop → 右操作数
left = stack.pop()    // 第二次 pop → 左操作数
result = left op right

✗ 把 pop 顺序写反 —— 用例 ["4","13","5","/","+"]：遇到 / 必须是 13 / 5 = 2，不能写成 5 / 13。
✗ 忘记整数除法 trunc 向零 —— Go 中 left / right 截断小数部分。