LeetCode LCR 036. 逆波兰表达式求值

2026-03-28 HGNULB 约 9 分钟

文章信息 5 个分类 4 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 036. 逆波兰表达式求值

题意分析

给一个用逆波兰记法（后缀表达式）表示的算式，求它的值。运算符只有加减乘除四种，都是二元运算，除法向零截断。

后缀记法的定义决定了一切：运算符写在它的两个操作数之后。这带来一个极强的性质——表达式里没有括号，也不需要优先级规则，因为运算顺序已经被书写顺序完全确定了。中缀表达式求值之所以难，正是因为要处理优先级和括号；后缀记法把这部分复杂度提前消化掉了。

从数据流的角度看：从左往右扫描，遇到数字就是「一个待用的操作数」，遇到运算符就说明「最近产生的两个操作数该被合并了」。最近产生的先被消费，这个后进先出的访问模式直接指向栈。

题目保证表达式合法，这意味着不需要处理「运算符出现时栈里不足两个元素」或「扫完后栈里剩多个元素」这类异常，代码可以少写一大堆校验。

两个容易被忽略的细节。其一，减法和除法不满足交换律，先弹出的是右操作数、后弹出的才是左操作数，顺序搞反结果就错。其二，数字 token 可能是负数（如 "-11"）也可能是多位数（如 "12"），判断「这个 token 是不是数字」不能只看首字符是不是数字。

解法：数学推导

核心思路

先想能不能不用额外结构：直接在原数组上原地归约？每遇到一个运算符就把它和前两个数合并、再把后面的元素前移，这需要 $O(n)$ 的搬移，整体退化成 $O(n^2)$，而且改动输入本身也不干净。

瓶颈在于「运算符要消费的是最近的两个操作数」这一访问模式。数组的随机访问能力在这里毫无用处，我们只需要一端的插入与删除——这正是栈的语义，一次入栈一次出栈都是 $O(1)$。

于是状态定义为：栈里自底向上保存的是「已扫描部分归约后剩下的、尚未被消费的操作数」，栈顶是最近产生的那一个。

扫描规则只有两条。遇到数字：解析成整数入栈，它成为新的「最近操作数」。遇到运算符：连续弹出两个数，先弹出的是右操作数 y、后弹出的是左操作数 x（因为右操作数在后缀表达式里离运算符更近，入栈更晚），计算 x op y 后把结果压回栈——注意压回去这一步，结果本身就是一个新的操作数，可能马上被更外层的运算符消费。

循环不变量是：每处理完一个 token，栈中元素恰好是「把已扫描的这段前缀能算的都算完」之后剩下的操作数序列。合法的后缀表达式保证扫描结束时栈中恰好剩一个元素，它就是整个表达式的值。

判断 token 类型的写法值得单独说：t.length() > 1 || Character.isDigit(t.charAt(0))。四个运算符都是长度为 1 的非数字字符，所以「长度大于 1」必然是数字（多位数或负数），「长度为 1 且是数字」也是数字，两者取或就覆盖了全部数字情形，剩下的必是运算符。这个判断比逐个比对四种运算符更短，也天然处理了负数 token。

解题步骤

准备栈：Java 用 ArrayDeque 而不是 Stack，前者没有同步开销且是官方推荐的栈实现；Go 直接用切片模拟，尾部即栈顶。

逐个 token 分类：if (t.length() > 1 || Character.isDigit(t.charAt(0))) 判定为数字，Integer.parseInt(t) 后入栈。这个条件的两支分别覆盖「多位数与负数」和「一位数」，运算符只可能落进 else。

弹出顺序决定正负：int y = stk.pop(); int x = stk.pop();。先弹出的 y 是右操作数，后弹出的 x 是左操作数。因为在 x y op 这样的书写顺序里，y 后入栈所以先出栈——减法和除法必须靠这个顺序才正确。

按运算符计算并压回：加减乘除四选一，结果 stk.push(...)。压回是必须的，它让本次归约的结果参与后续运算，整个过程才能层层收敛。

除法直接用整数除：Java 与 Go 的整数除法都向零截断，与题目要求一致，不需要额外的取整处理。

返回栈顶：表达式合法时扫描结束栈中只剩一个元素，弹出即答案。

以 tokens = ["2", "1", "+", "3", "*"] 走一遍，它对应中缀的 (2 + 1) * 3。

扫 "2"：数字，入栈，栈为 [2]。扫 "1"：入栈，栈为 [2, 1]。扫 "+"：弹出 y = 1、x = 2，算得 3 压回，栈为 [3]——此刻栈里唯一的元素代表「左边这一整段已经归约成 3」。扫 "3"：入栈，栈为 [3, 3]。扫 "*"：弹出 y = 3、x = 3，算得 9 压回，栈为 [9]。扫描结束，返回 9。

再看一个能暴露弹出顺序的用例 ["4", "13", "5", "/", "+"]，对应 4 + (13 / 5)。扫描前三个后栈为 [4, 13, 5]。扫 "/"：弹出 y = 5、x = 13，算 13 / 5 = 2（向零截断）压回，栈为 [4, 2]。扫 "+"：弹出 y = 2、x = 4，算得 6，返回 6。如果把顺序写反成 y / x，这里会算成 5 / 13 = 0，最终答案变成 4。

最后看负数 token 的情形 ["-11", "2", "*"]："-11" 长度为 2，命中「长度大于 1」这一支，被正确解析成 -11 入栈；若只用首字符判断，'-' 不是数字，它会被当成减法运算符，直接弹栈失败。

代码实现

class Solution {
    public int evalRPN(String[] tokens) {
        // 栈里存「已归约但尚未被消费的操作数」，栈顶是最近产生的那个。
        Deque<Integer> stk = new ArrayDeque<>();
        for (String t : tokens) {
            // 运算符都是长度为 1 的非数字，其余情形一律是数字。
            if (t.length() > 1 || Character.isDigit(t.charAt(0))) {
                stk.push(Integer.parseInt(t));
            } else {
                // 先弹出的是右操作数，减法与除法靠这个顺序才正确。
                int y = stk.pop();
                int x = stk.pop();
                switch (t) {
                case "+":
                    stk.push(x + y);
                    break;
                case "-":
                    stk.push(x - y);
                    break;
                case "*":
                    stk.push(x * y);
                    break;
                default:
                    stk.push(x / y);
                    break;
                }
            }
        }
        return stk.pop();
    }
}

func evalRPN(tokens []string) int {
    // 栈里存「已归约但尚未被消费的操作数」，尾部是栈顶。
    stack := []int{}
    for _, token := range tokens {
        // 运算符都是长度为 1 的非数字，其余情形一律是数字。
        if len(token) > 1 || token[0] >= '0' && token[0] <= '9' {
            num, _ := strconv.Atoi(token)
            stack = append(stack, num)
            continue
        }
        // 先取的是右操作数，减法与除法靠这个顺序才正确。
        y := stack[len(stack)-1]
        x := stack[len(stack)-2]
        stack = stack[:len(stack)-2]
        if token == "+" {
            stack = append(stack, x+y)
        } else if token == "-" {
            stack = append(stack, x-y)
        } else if token == "*" {
            stack = append(stack, x*y)
        } else {
            stack = append(stack, x/y)
        }
    }
    return stack[len(stack)-1]
}

复杂度分析

时间复杂度：$O(n)$，n 为 token 个数。每个 token 只被扫描一次，数字入栈一次、运算符触发两次弹栈与一次压栈，全是常数操作；数字解析的代价与 token 长度成正比，总量仍是线性。

空间复杂度：$O(n)$，栈的最大深度由表达式形态决定。全是数字在前、运算符在后的表达式（如 ["1","2","3","4","+","+","+"]）会让栈先堆到 $O(n)$ 深，这就是最坏情况。

关键点总结

后缀表达式不需要处理优先级和括号，因为书写顺序已经唯一确定了运算顺序——识别出这一点，题目就从「表达式解析」降级成「一次线性扫描」。

「最近产生的先被消费」这一访问模式是选择栈的唯一理由，面试时要说出这句话而不是只说「用栈」。

减法与除法不满足交换律，先弹出的必须当右操作数；凡是涉及非交换运算的栈式归约，都要在纸上写一遍 x op y 确认顺序。

计算结果必须压回栈，它是下一次归约的操作数；忘记压回等于把整段子表达式的值丢掉。

用「长度大于 1 或首字符是数字」来识别数字 token，一句话同时覆盖多位数与负数，比列举四种运算符更稳。

面试视角：面试官常顺势追问「如果给的是中缀表达式呢」。标准回答是用双栈（操作数栈加运算符栈）按优先级归约，或先用调度场算法把中缀转成后缀再套用本题解法——能说出「后缀是中缀求值的中间产物」这条关系，说明你理解了这套记法存在的意义。

易错点总结

弹出顺序写反：["4","13","5","/","+"] 中把先弹出的当左操作数会算成 5 / 13 = 0，最终返回 4 而不是 6。

只用首字符判断是不是数字：["-11","2","*"] 里 "-11" 的首字符是 '-'，会被当成减法运算符，弹栈时元素不足直接崩溃。

只判断 t.length() == 1 就当运算符：单个数字如 "5" 长度也是 1，会被误当运算符，["5","3","+"] 直接出错。

计算完忘记把结果压回栈：["2","1","+","3","*"] 在处理 "*" 时栈里只剩一个元素，弹栈失败或结果错误。

用浮点除法再取整：-7 / 2 用向下取整会得到 -4，而题目要求向零截断应为 -3；直接用整数除法即可，不要绕道浮点。

返回栈底或遍历栈求和：["2","1","+","3","*"] 结束时栈里只有 9，但若表达式更长而误取栈底，会返回中间结果。

用 Stack 类实现：功能正确但带同步开销，且它的迭代顺序与栈语义相反，一旦后续需要遍历栈会踩坑。

Go 里弹栈只截断一个元素：写成 stack = stack[:len(stack)-1] 却取了两个值，栈里会残留一个已被消费的操作数，["4","13","5","/","+"] 最终返回错误的中间值。

假设操作数都是一位数而用 token[0] - '0' 解析：["12","3","+"] 会把 "12" 解析成 1，结果变成 4。

相似题目

题目	难度	考察点
150. 逆波兰表达式求值	中等	与本题同题，可直接套用单栈归约
227. 基本计算器 II	中等	中缀且含乘除优先级，需要用栈延迟加减、乘除即时结算
224. 基本计算器	困难	中缀且含括号与一元负号，要用栈保存括号外的符号与累计值
772. 基本计算器 III	困难	括号与优先级同时存在，通常递归处理括号内子表达式
面试题 16.26. 计算器	中等	与 227 同型，无括号但有乘除优先级
20. 有效的括号	简单	同样是「最近的先匹配」，但栈里存的是待配对的符号而非操作数
394. 字符串解码	中等	嵌套结构的栈式归约，要同时维护数字栈与字符串栈
71. 简化路径	中等	用栈处理 `..` 的回退，是「遇到某标记就消费栈顶」的另一种形态