150. 逆波兰表达式求值（Evaluate Reverse Polish Notation）

频次 ★★★ · 难度 🟡 · 高频：百度

题目

计算逆波兰表达式（后缀表达式）的值。有效的运算符为 + - * /，每个操作数可能是整数或另一个表达式的结果。

示例：

输入: tokens = ["2","1","+","3","*"]
输出: 9    ((2 + 1) * 3 = 9)

思路

后缀表达式天生适合用栈求值：从左到右扫描，遇到数字就压栈；遇到运算符就弹出栈顶两个数做运算，再把结果压回去。扫描结束时栈里唯一剩下的数就是答案。

注意运算顺序：弹出的第一个数是右操作数，第二个才是左操作数（因为后弹出的先入栈），对减法、除法这种不满足交换律的运算尤其要注意顺序。

代码

public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (String token : tokens) {
        if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
            int b = stack.pop(); // 右操作数（后压栈的先弹出）
            int a = stack.pop(); // 左操作数
            int result;
            switch (token) {
                case "+": result = a + b; break;
                case "-": result = a - b; break;
                case "*": result = a * b; break;
                default:  result = a / b;
            }
            stack.push(result);
        } else {
            stack.push(Integer.parseInt(token));
        }
    }
    return stack.pop();
}

复杂度

• 时间：O(n) — 每个 token 处理一次
• 空间：O(n) — 最坏情况栈存满所有操作数

边界条件

• 只有一个操作数（如 ["5"]）：直接压栈，循环结束后 stack.pop() 返回它本身，没有运算符介入。
• 操作数为负数（如 "-3"）：Integer.parseInt("-3") 能正确解析负号，不需要额外处理。
• 除法结果需要向下取整还是向零截断：本题按 Java 默认的整数除法语义（向零截断），题目通常也是这样约定的。

变式

• 中缀表达式转后缀表达式再求值（更贴近日常书写的表达式，如 "(1+2)*3"）：需要先用调度场算法（Shunting Yard）转换成后缀表达式，再套用本题的栈求值逻辑。
• 支持更多运算符（如取模 %、幂 ^）：在 switch 分支里加对应 case 即可，整体框架不变。

易错点

• a - b 和 a / b 里 a、b 弹出顺序不能反，反了减法和除法的结果会是错的（加法、乘法反了不影响结果，容易被掩盖成”偶尔对”）。
• Java 的整数除法向零截断（如 -7 / 2 == -3），和数学上的向下取整不同，本题按 Java 语义即可，但面试时最好主动提一句。

面试追问

• 为什么后缀表达式不需要括号、也不需要考虑运算符优先级？ 因为后缀表达式的书写顺序本身就隐含了运算顺序——运算符出现的位置就是它应该被执行的时刻，用栈从左到右扫描处理，天然按照”该算的时候就去算”的顺序执行，不需要额外的优先级规则或括号来消除歧义。
• 如果输入的表达式格式有误（如缺少操作数），应该怎么处理？ 可以在弹栈前检查 stack.size() >= 2，不满足则说明表达式不合法，可以抛出异常或返回错误标记；题目通常保证输入合法，不需要处理，但面试中主动提到这点体现工程严谨性。

关联题

• 同套路：20. 有效的括号、394. 字符串解码 —— 栈结构三件套
• 进阶：224/227. 基本计算器系列 —— 中缀表达式要先处理运算符优先级，逆波兰正是它们转换后的中间产物
• 知识点：JVM 字节码基于操作数栈求值，与逆波兰完全同构，见JVM