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

约 5 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 数学 栈 LCR

题目描述

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

image-20260928235522792

image-20260928235522793

image-20260928235522794

题意分析

后缀表达式把运算符写在两个操作数之后，操作数也可以是前面已经完成的子表达式。运算顺序由 token 的排列确定，不需要再处理括号或乘除优先级。

从左到右读到运算符时，要使用最近得到的两个值。题目保证表达式合法且除数不为零，除法只保留整数部分，也就是向零截断；负数和多位数都是完整的数字 token。

解法：栈计算逆波兰表达式

核心思路

[!blue]

用栈保存已处理部分中“已经算出、尚未被外层运算使用”的值。遇到数字就入栈；遇到运算符时，最近产生的两个值恰好位于栈顶，可以立即合并。

对形如 x y op 的后缀片段，右操作数 y 更晚入栈，因此先弹出的是 y，后弹出的是 x。必须计算 x op y，尤其减法和除法不能交换顺序。

每次运算后把结果重新压栈，相当于把对应的整个子表达式缩成一个数字。这样处理完一个 token 后，栈仍准确保存尚待使用的各段结果；合法表达式扫描结束时恰好只剩一个值，就是最终答案。

四种运算符都是单个非数字字符，所以代码将“长度大于一，或首字符为数字”的 token 当作整数解析，能够同时识别多位数和负数。Java 与 Go 的整数除法都向零截断，可以直接使用 /。

解题步骤

  1. 创建空栈，按原顺序扫描全部 token。
  2. 数字 token 整体解析为整数后入栈。
  3. 运算符先弹出右操作数 y，再弹出左操作数 x，按照 x op y 计算。
  4. 将运算结果压回栈，供后续更外层的运算使用。
  5. 全部处理完后，返回栈中唯一剩下的值。

代码实现

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();
    }
}

import (
    "strconv"
)

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)$，当很多操作数先于运算符出现时，栈中可能同时保存线性数量的值。

关键点总结

[!green]

  • 栈顶保存最近完成的值，与后缀表达式遇到运算符时的取值顺序一致。
  • 运算结果重新入栈，让嵌套子表达式逐步归并为一个最终值。
  • 运算符的位置已经确定计算时机，不需要额外比较优先级。

易错点总结

[!yellow]

  • 先取右操作数，再取左操作数，减法和除法要保持 x op y 的顺序。
  • 不能只看首字符是否为数字来分类，否则负数 token 会被误当成减法运算符。
  • 每次计算后必须压回结果，不能直接丢掉子表达式的值。
  • 除法是向零截断，不能替换成向下取整；题目保证合法输入，无需补充未定义运算符的处理分支。

相似题目

题目 难度 关联与区别
224. 基本计算器 困难 原题中缀表达式要处理括号和优先级，本题后缀顺序已确定，遇运算符直接弹出两个操作数。
227. 基本计算器 II 中等 同样用栈保存尚未合并的结果，原题仍需按乘除优先级决定计算时机。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/42754912
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！