150. 逆波兰表达式求值

题目描述

求逆波兰(后缀)表达式的值。运算符在两个操作数之后，如 “2 1 + 3 *” 表示 (2+1)×3。

思路解析

从左到右：是数字就压栈；是运算符就弹出栈顶两个数(注意顺序：先弹的是右操作数)，算完把结果压回栈。扫完栈里剩的唯一一个数就是答案。

读 2 · 入栈：读到数字 2，压入栈。

读 1 · 入栈：读到数字 1，压入栈。现在栈是 [2, 1]。

读 + · 弹两个：读到 +，弹出栈顶 1 和 2，算 2 + 1 = 3，把 3 压回栈。栈变成 [3]。

读 3 · 入栈：读到数字 3，压入栈。栈是 [3, 3]。

读 * · 弹两个：读到 ×，弹出两个 3，算 3 × 3 = 9，压回栈。

结束 · 栈顶即答案：所有 token 读完，栈里只剩 9，就是表达式的值。

后缀表达式没有优先级和括号的烦恼，操作数先存栈、运算符来了就地结算——这是表达式求值的经典栈应用。

参考代码（Python）

1stack = []
2for tk in tokens:
3    if tk in class="cl-str">"+-*/":
4        b = stack.pop(); a = stack.pop()   # 先弹的是右操作数
5        stack.append(int(eval(fclass="cl-str">"{a}{tk}{b}")))  # 按 a op b 算
6    else: stack.append(int(tk))            # 数字入栈
7return stack[0]

复杂度分析

• 时间复杂度：O(n) —— 每个 token 处理一次
• 空间复杂度：O(n) —— 栈最多装一半数字

套路模板

记住骨架：操作数入栈、运算符弹两个(下面是左、上面是右)算完入栈。中缀转后缀、基本计算器都用栈处理。

1stack = []
2for tk in tokens:
3    if 是操作数: stack.append(转换(tk))
4    else:                              # 是运算符
5        b = stack.pop(); a = stack.pop()   # 顺序: a op b
6        stack.append(运算(a, tk, b))
7return stack[-1]

易错点

• ❌ a、b 顺序搞反 → ✅ b=先弹(右), a=后弹(左), 算 a op b（减法、除法不满足交换律，反了就错）
• ❌ 除法没按题目取整规则 → ✅ 注意向零取整 int(a/b)（负数除法 Python // 和题目要求可能不同）

以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。