LeetCode 224 基本计算器：Python 栈解法与追踪演示

LeetCode 224「基本计算器」要求你计算一个包含数字、+、-、括号和空格的字符串表达式，且不能使用 eval。题目中没有乘除法，所以不需要处理运算符优先级。唯一的难点是括号，而用一个栈保存状态就能一趟扫描干净利落地解决。

题目

给定一个字符串 s，表示一个由非负整数、+、-、(、) 和空格组成的表达式，返回它的值。减号也可以作为一元运算符，例如 -(2 + 3)。

示例：

核心思路

从左到右扫描，同时维护三个东西：当前累计结果、当前符号、正在构建的数字。遇到 ( 时，说明要开始一个子表达式。把当前结果和括号前面的符号压入栈中保存，然后以结果 0、符号 +1 重新开始。遇到 ) 时，子表达式计算完毕，把它乘以保存的符号，再加到保存的结果上。

逐个字符处理：

最后，把最后的 sign * num 加上。

def calculate(s):
    result, sign, num = 0, 1, 0
    stack = []
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch in "+-":
            result += sign * num
            num = 0
            sign = 1 if ch == "+" else -1
        elif ch == "(":
            stack.append(result)
            stack.append(sign)
            result, sign = 0, 1
        elif ch == ")":
            result += sign * num
            num = 0
            result *= stack.pop()   # the sign before the parenthesis
            result += stack.pop()   # the result before the parenthesis
    return result + sign * num

出栈顺序很重要：符号是最后压入的，所以最先弹出。

追踪过程

表达式：1-(2+3)。

1 - (2 + 3) = -4，结果吻合。

一元负号

开头的负号不需要特殊处理。一开始 num 是 0，所以第一个 - 把 sign * 0 加到结果上，然后把符号设为 -1。( 之后也是同理：保存的状态把 result 重置为 0、sign 重置为 +1，所以 (-2) 也以同样的方式处理。

复杂度

• 时间：O(n)，对字符串一趟扫描。
• 空间：最坏情况下为 O(n)，即括号深度嵌套时，因为每个左括号在栈中保存两个值。

我用 4,000 个带有嵌套括号和一元负号的随机表达式测试了这个函数，与 Python 自身的求值结果对比，全部一致。

替代方案：递归

你也可以写一个递归函数来解析表达式，遇到 ( 时调用自身。它读起来很自然，但在深度嵌套的输入上可能触及递归深度限制，所以在 Python 中栈版本更安全。

面试官常问的扩展

边界情况

常见错误

1. 把每个数字当成单独的数。
2. 忘记在最后加上 sign * num。
3. 出栈顺序弄错。
4. 运算符之后没有重置 num。
5. 开头的负号处理不当。

面试中如何讲解

1. 先确认允许的字符，以及是否会出现一元负号。
2. 说明没有优先级问题，所以括号是唯一的挑战。
3. 描述三个变量以及栈保存了什么。
4. 在白板上走一遍 1-(2+3)。
5. 给出复杂度，然后提到计算器 II 的扩展。

相关练习

复杂度术语可参考我们的 Big O 速查表，还有 AI LeetCode 辅导指南 和 编程面试助手指南。「有效的括号」和「字符串解码」用的是同样的栈思路。

练习时把追踪过程大声讲出来。一份模拟面试记录能看出你是否解释了栈的用途。在任何实时评估中，请遵守雇主关于 AI 工具的规定。