LeetCode 150. 逆波兰表达式求值:用栈实现后缀表达式计算(leetcode 题解)
LeetCode 150. 逆波兰表达式求值:用栈实现后缀表达式计算(leetcode 题解)
本篇技术指南围绕 leetcode 题解仓库中的 150. 逆波兰表达式求值 展开,完整讲解逆波兰表达式(后缀表达式)的概念、为什么它天生适合用栈求值,以及如何用 JS / Python / Java / CPP 四种语言实现一次遍历的线性解法。读完本文,你将掌握"遇数字入栈、遇运算符弹两数计算再压栈"这一核心套路,理解 JS 除法与取整的坑、操作数出栈顺序等关键易错点,并能将其迁移到计算器、表达式求值、代码编译求值等实战场景。
题目描述
根据逆波兰表示法,求表达式的值。
有效的运算符包括 +, -, *, /。每个运算对象可以是整数,也可以是另一个逆波兰表达式。
说明:
- 整数除法只保留整数部分。
- 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1:
输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: 该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9
示例 2:
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: 该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6
示例 3:
输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
输出: 22
解释:
该算式转化为常见的中缀算术表达式为:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
在 collections/medium.md 中,本题被归类为中等难度(medium)的经典题目,并在 README.md 的题目索引中被收录。
什么是逆波兰表达式
逆波兰表达式(Reverse Polish Notation,RPN)是一种后缀表达式,所谓后缀就是指算符写在后面。
- 平常使用的算式是一种中缀表达式,如
( 1 + 2 ) * ( 3 + 4 ); - 该算式的逆波兰表达式写法为
( ( 1 2 + ) ( 3 4 + ) * ); - 去掉括号后即为
1 2 + 3 4 + *,依据运算次序即可计算出正确结果。
逆波兰表达式主要有以下两个优点:
- 去掉括号后表达式无歧义,上式即便写成
1 2 + 3 4 + *也可以依据次序计算出正确结果; - 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中。
从历史渊源看,波兰逻辑学家 J.Lukasiewicz 于 1929 年提出了另一种表示表达式的方法,按此方法,每一运算符都置于其运算对象之后,故称为"后缀表示"。逆波兰表达式是一种十分有用的表达式,它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式,例如 (a+b)*(c+d) 转换为 ab+cd+*。
前置知识:栈(Stack)
本题的前置知识只有一条:栈。
仓库 thinkings/basic-data-structure.md 的"栈"章节对栈这一数据结构做了系统讲解,可以对照阅读:
- 栈是一种受限的序列,它受限就受限在只能够操作栈顶,不管入栈还是出栈,都是在栈顶操作;而数组没有这个限制;
- 在计算机科学中,栈是一种抽象数据类型(ADT),具有两种主要操作:
push(添加元素到栈的顶端)和pop(移除栈顶元素),两种操作概括为后进先出(LIFO = last in, first out); - 此外,通常还有一个
peek操作用于访问栈当前顶端的元素(只返回不弹出)。
该章节还指出:栈常见的应用有进制转换、括号匹配、栈混洗、中缀表达式、后缀表达式(逆波兰表达式)等。本题正是"后缀表达式"这一栈典型应用的直接落地。同时,"用递归的解法和用循环 + 栈的解法本质上是差不多的"这一观察,也提示了栈在处理嵌套/递归结构时的通用价值——逆波兰表达式求值之所以能消除括号、消除优先级,正是因为它把表达式的递归结构"压平"成了线性 token 序列,交给一个简单的栈即可顺序还原。
解题思路
逆波兰表达式又叫做后缀表达式。在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,这种表示法也称为中缀表示;而逆波兰表达式将运算符放在两个运算对象之后。
核心思路非常简单,只有三步:
- 遍历 token 列表,依次入栈,直到遇到算术运算符;
- 将栈顶两个元素出栈运算,将结果压回栈中;
- 重复以上过程直到所有的 token 都处理完毕,此时栈中剩下的唯一元素就是最终结果。
用一句话概括:遇数字入栈,遇运算符弹出两个数字计算,再把结果压栈。由于逆波兰表达式本身已经通过后缀顺序消除了中缀表达式中的运算符优先级和括号问题,我们无需任何优先级判断,直接按 token 顺序执行即可。
以示例 2 ["4", "13", "5", "/", "+"] 为例的完整推演:
| 当前 token | 操作 | 栈内状态(栈顶在右) |
|---|---|---|
"4" |
数字入栈 | [4] |
"13" |
数字入栈 | [4, 13] |
"5" |
数字入栈 | [4, 13, 5] |
"/" |
弹出 5、13,计算 13 / 5 = 2(整数除法),压栈 |
[4, 2] |
"+" |
弹出 2、4,计算 4 + 2 = 6,压栈 |
[6] |
最终返回 6。
关键点与易错点
原文档总结了四个关键点,每一个都直接影响代码的正确性:
-
栈的基本用法:只操作栈顶,
push与pop成对出现,这是本题的唯一数据结构基础。 -
JS 的
/与很多语言不一样:JS 中5 / 2的结果是2.5(浮点除法),而本题要求整数除法只保留整数部分,因此 JS 实现中需要用位运算或Math.trunc等方式显式取整。 -
JS 需要先将字符串转化为数字:输入 tokens 是字符串数组,直接做算术运算会发生字符串拼接等意想不到的结果(例如
"1" + "2"得到"12"),必须用Number()或parseInt转换。 -
操作符的顺序:先出栈的是第二位,后出栈的是第一位。这在不符合交换律的操作中很重要,比如减法和除法。若 token 为
"/",先pop出栈顶元素a为被除数右边的操作数,后pop出的b才是被除数,正确的运算是b / a,而非a / b。加法和乘法符合交换律,顺序无关紧要,但减法和除法一旦顺序颠倒,结果就完全不同。
代码实现
原文档代码支持 JS、Python、Java、CPP 四种语言,以下逐一给出并补充注释。
JS Code
/**
* @param {string[]} tokens
* @return {number}
*/
var evalRPN = function (tokens) {
// 这种算法的前提是 tokens 是有效的,当然这由算法来保证
const stack = [];
for (let index = 0; index < tokens.length; index++) {
const token = tokens[index];
// 对于运算数,我们直接入栈
if (!Number.isNaN(Number(token))) {
stack.push(token);
} else {
// 遇到操作符,我们直接大胆运算,不用考虑算术优先级
// 然后将运算结果入栈即可
// 当然如果题目进一步扩展,允许使用单目等其他运算符,
// 我们的算法需要做微小的调整
const a = Number(stack.pop());
const b = Number(stack.pop());
if (token === "*") {
stack.push(b * a);
} else if (token === "/") {
// JS 中除法结果是浮点数,用 >> 0 进行向零取整
// (注意:>> 只对 32 位整数有效,负数时与 Math.trunc 同为向零截断)
stack.push((b / a) >> 0);
} else if (token === "+") {
stack.push(b + a);
} else if (token === "-") {
stack.push(b - a);
}
}
}
return stack.pop();
};
JS 实现要点:
Number(token)判断是否为数字;Number.isNaN过滤掉非数字的运算符 token;- 负数(如示例 3 中的
"-11")也能被Number正确识别为数字并入栈,无需特殊处理; - 除法用
(b / a) >> 0实现向零取整(truncate),满足"整数除法只保留整数部分"的要求。
Python Code
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
if len(tokens) > 2:
stack = []
operations = ['+', '-', '*', '/']
for token in tokens:
if token in operations:
b = int(stack.pop())
a = int(stack.pop())
if '+' == token:
tmp = a + b
elif '-' == token:
tmp = a - b
elif '*' == token:
tmp = a * b
else:
# Python 的 / 是浮点除法,int() 截断小数实现向零取整
tmp = int(a / b)
stack.append(tmp)
else:
stack.append(token)
return stack[0]
return int(tokens[-1])
Python 实现要点:
stack.pop()弹出的是后入栈的b位置,先b后a,即a是栈中更早的元素;- Python 3 中
a / b是浮点除法,int(a / b)将其向零截断为整数,注意这与//(向下取整)在负数场景下结果不同,例如int(-132 / 12)与-132 // 12在正负号处理上需要留意; - 对
len(tokens) <= 2的边界情况直接返回末尾数字,简化处理。
Java Code
class Solution {
public static int evalRPN(String[] tokens) {
// 用定长数组模拟栈:最大深度不会超过 tokens 长度的一半 + 1
int[] numStack = new int[tokens.length / 2 + 1];
int index = 0;
for (String s : tokens) {
if (s.equals("+")) {
numStack[index - 2] += numStack[--index];
} else if (s.equals("-")) {
numStack[index - 2] -= numStack[--index];
} else if (s.equals("*")) {
numStack[index - 2] *= numStack[--index];
} else if (s.equals("/")) {
numStack[index - 2] /= numStack[--index];
} else {
numStack[index++] = Integer.parseInt(s);
}
}
return numStack[0];
}
}
Java 实现要点:
- 没有使用
Stack类,而是用定长 int 数组模拟栈,index即栈顶指针,避免了装箱开销; - 关键优化:
new int[tokens.length / 2 + 1]—— 由于每个运算符都会消耗两个数字并压回一个结果(净减少 1 个元素),栈的最大深度不超过数字数量,即tokens.length / 2 + 1,因此可以精确预分配数组大小,从源码层面印证了"栈深度有界"这一性质; - 对于运算符,直接改写栈顶前两个位置的合并结果(如
numStack[index - 2] += numStack[--index]),将"弹出两个、压回一个"压缩为一次原地更新; - Java 的
int除法本身就是向零取整,天然满足"整数除法只保留整数部分"。
CPP Code
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> s;
for (string t : tokens) {
// 判断最后一个字符是否为数字,以区分负数和运算符
if (isdigit(t.back())) s.push(stoi(t));
else {
int n = s.top();
s.pop();
switch(t[0]) {
case '+': s.top() += n; break;
case '-': s.top() -= n; break;
case '*': s.top() *= n; break;
case '/': s.top() /= n; break;
}
}
}
return s.top();
}
};
CPP 实现要点:
- 用
t.back()(字符串最后一个字符)配合isdigit判断是否为数字,巧妙地将"-11"这类负数归为数字分支(负数的最后一个字符仍是数字); stoi(t)将字符串转为int;- 弹出栈顶
n作为右操作数,直接与新的栈顶元素(左操作数)进行运算并写回,s.top()在switch分支中被更新为运算结果,代码非常紧凑; - C++ 的
int除法同样是向零取整。
复杂度分析
- 时间复杂度:O(n),其中 n 为 tokens 的数量。整个 token 序列只需顺序扫描一遍,每个 token 只做常数次入栈/出栈/算术运算。
- 空间复杂度:O(n),最坏情况下(表达式几乎全是数字、运算符集中在末尾),栈中需要同时保存 O(n) 个数字。Java 实现中
tokens.length / 2 + 1的数组预分配正是对这一上界的最优利用——事实上可以证明任意合法逆波兰表达式中,任一前缀里数字数量都严格多于运算符数量,栈深度始终有界且不超过数字总数。
扩展思考
原文档在"扩展"部分提出了一个值得深思的性质:
逆波兰表达式中只改变运算符的顺序,并不会改变操作数的相对顺序,这是一个重要的性质。另外逆波兰表达式完全不关心操作符的优先级,这在中缀表达式中是做不到的。
这两点值得展开:
-
操作数相对顺序不变:从
(a+b)*(c+d)到ab+cd+*,操作数a b c d的相对顺序完全保持一致,变的只是运算符的位置。这意味着我们可以通过一遍线性扫描(如调度场算法,Shunting-yard algorithm)将中缀表达式转换为后缀表达式,而不需要调整操作数的排列——这也是编译器、计算器实现表达式求值的经典路径。 -
不关心运算符优先级:中缀表达式求值之所以困难,是因为
*必须先于+计算、括号必须优先,需要符号栈和优先级表配合;而逆波兰表达式中,优先级已经被"后置"的书写顺序天然消解,每个运算符出现时,它的两个操作数一定已经完整出现在栈中。这正是"遇到运算符直接大胆运算,不用考虑算术优先级"(JS 代码注释中的原话)背后的数学原理。 -
扩展性思考:若题目进一步扩展,允许单目运算符(如取负、阶乘)、
^幂运算等非常规运算符,算法只需做微小的调整——单目运算符只需弹出栈顶一个操作数,非常规运算符补充对应的计算分支即可,栈的整体框架保持不变。这也体现了栈解法对表达式求值这一类问题的普适性。
小结
逆波兰表达式求值是"栈"这一数据结构最经典的应用场景之一,题目本身不涉及复杂的算法设计,却集中考察了栈的 LIFO 语义、操作数顺序、整数除法、类型转换等大量工程细节,因此成为面试中频繁出现的"考察基础是否扎实"的题目(原文档标注该题出现于阿里、腾讯等公司的面试场景)。掌握本题的"遇数字入栈、遇运算符弹两数计算再压栈"套路,再配合 thinkings/basic-data-structure.md 中关于栈的系统知识,就足以应对中缀转后缀、表达式求值、计算器系列题目的核心部分。