LeetCode 150中等栈
逆波兰表达式求值 图解题解
逆波兰表达式看起来没有括号、顺序怪，其实它天生就是为栈量身定制的。
像排队取快递再合并：数字token一个个压进栈等待；遇到运算符，就从栈顶取出最近放进来的两个数（先弹的是右操作数、再弹的是左操作数），当场运算，结果压回去继续排队。后进先出恰好和逆波兰的「先写操作数、再写运算符」配合得天衣无缝，扫一遍结束，栈里剩下的就是答案。
这道题到底在问什么
给一串 token，是数字或运算符（+ − × ÷）。按逆波兰规则求值。除法向零截断。
- 输入
- tokens=["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
- 输出
- 22
最优解：一步一步想明白
- 3记住这一条，下面每个 token 都在套它。
- 4栈一开始是空的。指针从最左边的 token 出发。
- 5第 0 个 token 是数字 10，数字一律直接压进栈。
- 610 进栈，现在栈里有 1 个数，栈顶是 10。
- 7第 1 个 token 是数字 6，数字一律直接压进栈。
- 86 进栈，现在栈里有 2 个数，栈顶是 6。
- 9第 2 个 token 是数字 9，数字一律直接压进栈。
- 109 进栈，现在栈里有 3 个数，栈顶是 9。
- 11第 3 个 token 是数字 3，数字一律直接压进栈。
- 123 进栈，现在栈里有 4 个数，栈顶是 3。
- 13第 4 个 token 是运算符 +。弹出栈顶两个数：先弹的 3 是右操作数，后弹的 9 是左操作数。
- 14算 9 加 3 = 12（顺序是左 加 右，别弹反）。把结果 12 压回栈，替换掉刚弹走的两个数。
- 15第 5 个 token 是数字 -11，数字一律直接压进栈。
- 16-11 进栈，现在栈里有 4 个数，栈顶是 -11。
- 17第 6 个 token 是运算符 *。弹出栈顶两个数：先弹的 -11 是右操作数，后弹的 12 是左操作数。
- 18算 12 乘 -11 = -132（顺序是左 乘 右，别弹反）。把结果 -132 压回栈，替换掉刚弹走的两个数。
- 19第 7 个 token 是运算符 /。弹出栈顶两个数：先弹的 -132 是右操作数，后弹的 6 是左操作数。
- 20算 6 除 -132 = 0（顺序是左 除 右，别弹反）。把结果 0 压回栈，替换掉刚弹走的两个数。
- 21第 8 个 token 是运算符 *。弹出栈顶两个数：先弹的 0 是右操作数，后弹的 10 是左操作数。
- 22算 10 乘 0 = 0（顺序是左 乘 右，别弹反）。把结果 0 压回栈，替换掉刚弹走的两个数。
- 23第 9 个 token 是数字 17，数字一律直接压进栈。
- 2417 进栈，现在栈里有 2 个数，栈顶是 17。
- 25第 10 个 token 是运算符 +。弹出栈顶两个数：先弹的 17 是右操作数，后弹的 0 是左操作数。
- 26算 0 加 17 = 17（顺序是左 加 右，别弹反）。把结果 17 压回栈，替换掉刚弹走的两个数。
- 27第 11 个 token 是数字 5，数字一律直接压进栈。
- 285 进栈，现在栈里有 2 个数，栈顶是 5。
- 29第 12 个 token 是运算符 +。弹出栈顶两个数：先弹的 5 是右操作数，后弹的 17 是左操作数。
- 30算 17 加 5 = 22（顺序是左 加 右，别弹反）。把结果 22 压回栈，替换掉刚弹走的两个数。
- 31所有 token 处理完（全部变灰），栈里只剩一个数 22，它就是整个表达式的值。
⚠️ 容易写错的地方
✗ 错：a、b 顺序弄反
✓ 对：先弹的是右操作数 b，后弹的是左操作数 a
减法/除法不满足交换律，反了答案就错
✗ 错：除法忘记向零截断
✓ 对：用 int(a/b) / a/b（C++/Java 天然截断）
题目规定向零取整，不是向下取整
✗ 错：数字误当运算符
✓ 对：负数如 "-11" 是数字不是减号
判断要看整个 token，不能只看首字符
完整代码（Python / C++ / Java）
Python
def evalRPN(tokens):
st = []
for t in tokens:
if t in ("+", "-", "*", "/"):
b = st.pop(); a = st.pop()
if t == "+": st.append(a + b)
elif t == "-": st.append(a - b)
elif t == "*": st.append(a * b)
else: st.append(int(a / b)) # 向零截断
else:
st.append(int(t))
return st[0]C++
int evalRPN(vector<string>& tokens){
stack<long> st;
for(auto& t : tokens){
if(t=="+"||t=="-"||t=="*"||t=="/"){
long b = st.top(); st.pop();
long a = st.top(); st.pop();
if(t=="+") st.push(a + b);
else if(t=="-") st.push(a - b);
else if(t=="*") st.push(a * b);
else st.push(a / b); // C++ 整除即向零截断
} else st.push(stol(t));
}
return st.top();
}Java
public int evalRPN(String[] tokens){
Deque<Integer> st = new ArrayDeque<>();
for(String t : tokens){
switch(t){
case "+": case "-": case "*": case "/": {
int b = st.pop(), a = st.pop();
if(t.equals("+")) st.push(a + b);
else if(t.equals("-")) st.push(a - b);
else if(t.equals("*")) st.push(a * b);
else st.push(a / b); // Java 整除向零截断
break;
}
default: st.push(Integer.parseInt(t));
}
}
return st.pop();
}复杂度
时间
O(n)
每个 token 只进出栈常数次
空间
O(n)
最坏全是数字，栈装一半
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 逆波兰表达式求值 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么逆波兰表达式不需要括号？+
运算顺序已由 token 的位置唯一确定，扫到运算符时它的两个操作数必然就在栈顶，无歧义。
怎么把中缀表达式转成逆波兰？+
用「调度场算法」（Shunting-yard）：再用一个运算符栈按优先级弹出输出，即可得到后缀序列。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 逆波兰表达式求值 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。