150. 逆波兰表达式求值

题目链接：150. 逆波兰表达式求值

题目描述

给定一个字符串数组 tokens，表示一个根据 逆波兰表示法 表示的算术表达式。请计算并且返回该表达式的整数结果。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/'。
• 两个整数之间的除法总是 向零截断。
• 表达式中不含除零运算。
• 输入是一个有效的逆波兰表达式，即对于每一个算符，都有两个对应的操作数。

核心思考：栈机制解决后缀表达式

逆波兰表达式（RPN）也就是后缀表达式，它的最大优势是不需要括号就能严格规定运算的优先级，这对于计算机来说非常友好。

求解逆波兰表达式也是**栈（Stack）**这一后进先出数据结构的最典型应用场景：

1. 遇到数字：压入栈中备用。
2. 遇到运算符：从栈顶连续弹出两个数字作为操作数计算。注意，“后弹出”的元素应该是被操作的“左操作数”，“先弹出”的元素是“右操作数”（例如先弹 a 后弹 b，减法应当是 b - a）。
3. 遇到除法（重难点避坑）：由于题目要求向零截断，但在 Python 中，双斜杠 // 执行的是向下取整（向负无穷取整）。比如 -1 // 2 得到的是 -1 而不是向零靠拢的 0。因此计算除法时，我们需要转而使用浮点数除法 b / a ，然后再通过 int() 强转，就能完美实现向零保留整数部分的截断效果。

解题思路 (Python)

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stk = []
        for token in tokens:
            if token in "+-*/":
                a = stk.pop() # a 为先弹出的：右操作数
                b = stk.pop() # b 为后弹出的：左操作数
                if token == "+":
                    stk.append(a + b)
                elif token == "*":
                    stk.append(a * b)
                elif token == "-":
                    stk.append(b - a)
                elif token == "/":
                    # 使用 int(b / a) 进行向零截断，避开 Python // 的向下取整陷阱
                    stk.append(int(b / a))
            else:
                stk.append(int(token))
        return stk.pop()

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是数组 tokens 的长度。我们只需要向前遍历一遍字符串序列，对于每个元素，只有一次 $O(1)$ 常数时间开销的进栈、出栈或计算操作，总体时间代价是线性的。
• 空间复杂度：$O(N)$。最坏情况下（例如表达式前半段全部是数字，后半段全部是运算符），栈内将堆积近一半规模的元素，空间峰值增长呈现正比为 $O(N)$。