题目
LC 224 基本计算器：给你一个字符串表达式
s，请你实现一个基本计算器来计算并返回它的值。
s 由数字、
'+'、
'-'、
'('、
')' 和空格组成，
s 表示一个有效的表达式。
输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23
输入: "1 + 2 - (3 + 4) - 5"
输出: -9
（腾讯特色）：在 224 的基础上加上
'*'、
'/'，处理运算优先级与括号。整数除法截断小数部分（向零取整）。
输入: "2*(5+5*2)/3+(6/2+8)"
输出: 21
两道题是一套题的"退化版与满血版"：224 只有加减 ——
同级、左结合，根本没有优先级要处理；772 加上乘除后优先级不再统一，"来一个结一个"当场失效。腾讯爱考它，是因为一道题能同时考到
词法切分、栈、优先级调度、括号处理、整数除法语义 —— 表达式求值全家桶。
一、LC 224 核心洞察：加减同级，符号 + "欠账栈"就够
先把问题砍到最小。表达式里只有两种运算符
+ -，它们
同级、左结合 —— 这意味着任何数字一旦读到，它前面的符号就已经定了，
没有资格等待：立刻乘上符号结算进累计值就行。所以 224 不需要运算符栈、不需要优先级比较，两个变量横扫一切：
result：当前层从左到右的累计值；sign：下一个数字的符号（+1 / -1）。
唯一的麻烦是
括号。
-(3+4) 里的整个括号要
乘以前面的负号再并回外层 —— 括号内是一个独立的小表达式，但它的值"欠"着外层一笔账。办法和 LC 20 一模一样：
没闭合的上一层进栈，只是栈帧的内容从"等哪个右括号"升级成了
"外层欠账"：
- 遇到
(：把 {result, sign} 压栈 —— 记下"外层已累计多少、这个括号整体该乘什么符号"，然后重启一个干净的累加器（result = 0, sign = +1）；
- 遇到
)：括号内算完得 inner，弹栈合并 result = 外层result + 外层sign * inner。
def calculate(s: str) -> int:
result, sign, stack = 0, 1, []
i = 0
while i < len(s):
c = s[i]
if c == ' ':
i += 1
elif c.isdigit():
j = i
while j < len(s) and s[j].isdigit(): # 连续数字合成一个数
j += 1
result += sign * int(s[i:j])
i = j
elif c == '+':
sign = 1; i += 1
elif c == '-':
sign = -1; i += 1
elif c == '(':
stack.append((result, sign)) # 外层欠账进栈
result, sign = 0, 1 # 重启累加器
i += 1
else: # ')'
inner = result
prev, psign = stack.pop()
result = prev + psign * inner # 括号塌缩成一个数并回外层
i += 1
return result
注意栈里存的
不是中间结果本身，而是"外层欠账"：外层累计值 + 括号符号。
1 + 2 - (3 + 4) - 5 扫到
( 时压入
{3, -1}，扫到
) 时括号内算出
7，合并成
3 + (-1) * 7 = -4 —— 括号作为一个
整体数值回到外层，继续
- 5 得
-9。
二、LC 772 核心洞察：优先级打破"立刻结算" → 双栈调度场
加上
* / 之后，第一节的根基塌了：
2 + 3 * 4 里的数字
3 有资格等待 —— 它右边可能跟一个
*，那时候
3 * 4 必须先于
+ 结算。"来一个结一个"失效，就需要 Dijkstra 的
双栈调度场（shunting-yard）：
nums 存操作数 —— 数字永远只进不出地攒着，什么时候算是运算符的事；ops 存运算符（( 也进 ops，但它只是个挡板，不比优先级）。
核心纪律只有一条：
新运算符来临时，把栈顶所有优先级 >= 它的运算符依次弹出结算，再把自己压进去。 用
>= 而不是
>，顺带解决了同级左结合 ——
10 - 2 - 3 里第二个
- 来临时，栈顶的
- 优先级相等，先结算
10 - 2 = 8，正确；若用
> 就会变成右结合算出
10 - (2 - 3) = 11，错。
这条纪律维持着一个漂亮的栈形不变量：
每层括号内部，ops 从底到顶优先级严格递增。于是扫完后的收尾只需"从栈顶到底依次结算"—— 低优先级的本来就沉在栈底，轮到最后，
这个顺序恰好就是正确的运算顺序。
括号：
( 压栈当挡板，让后面进来的运算符在它面前停下，圈出括号内的小天地；
) 一路结算到挡板为止，再弹掉挡板 —— 括号内塌缩成
nums 顶上的一个数。
def calculate(s: str) -> int:
prec = {'+': 1, '-': 1, '*': 2, '/': 2}
nums, ops = [], []
def apply():
op, b, a = ops.pop(), nums.pop(), nums.pop()
if op == '+': nums.append(a + b)
elif op == '-': nums.append(a - b)
elif op == '*': nums.append(a * b)
else: # 向零截断：// 是 floor，负数会错
q = abs(a) // abs(b)
nums.append(q if (a >= 0) == (b >= 0) else -q)
i = 0
while i < len(s):
c = s[i]
if c == ' ':
i += 1
elif c.isdigit():
j = i
while j < len(s) and s[j].isdigit():
j += 1
nums.append(int(s[i:j]))
i = j
elif c == '(':
ops.append(c); i += 1
elif c == ')':
while ops[-1] != '(': # 结算到挡板
apply()
ops.pop() # 弹掉 '(' 本身
i += 1
else: # + - * /
while ops and ops[-1] != '(' and prec[ops[-1]] >= prec[c]:
apply() # 优先级 >= 我的，先结账
ops.append(c)
i += 1
while ops: # 收尾：从顶到底全结算
apply()
return nums[0]
拿
"2*(5+5*2)/3+(6/2+8)" 走一遍最值钱的三步：
) 关闭
(5+5*2) 时先弹
5*2=10 再弹
5+10=15（乘法在括号内层栈顶，先走）；接着
/ 来临，栈顶
* 优先级相等，先结算
2*15=30 再压
/；最后收尾时
ops 里只剩一个
+，
10 + 11 = 21。全程没有任何一处"回头看"，
优先级全部由栈顶比较当场裁决。
三、动画怎么看
224 动画（
algo-viz--lc224）：顶部是 token 条（金框 = 当前 token，灰 = 已消费，下方三角指针），中部是"当前层累加器"面板（
sign 徽章 +
result 大格子，右侧红字给出本帧结算公式），底部是括号上下文栈。
1 + 2 两帧里 result 一路 1 → 3，全程无结算等待 —— 同级左结合的直观样子；( 帧：{result=3, sign=-1} 压栈变金框，累加器当场清零重启；) 帧：栈顶上下文变橙虚线幽灵，面板公式显示 3 + -1 * (7) = -4 —— 括号乘上外层符号并回；- 最后
result = -9 变绿框。
772 动画（
algo-viz--lc772）：顶部同样是 token 条，其下是
结算横幅（本帧依次弹出的算式），主体左列
nums、右列
ops（
( 也在里面当挡板）。
- 数字帧只动左列；
( 帧只动右列；
- 看第 9 帧
)：横幅一次亮出 5 * 2 = 10 → 5 + 10 = 15 两步 —— 括号内的高优先级先结账；
- 看第 10 帧
/：栈顶 * 优先级相等被结算（2 * 15 = 30），横幅给算式、ops 顶画幽灵、nums 顶亮金格 —— ">= 先结"纪律的逐帧证据；
- 收尾 flush 帧把
ops 排空，nums 恰剩一个数：21。
四、完整推演表
LC 224（
1 + 2 - (3 + 4) - 5，上下文栈按"底 → 顶"写）：
LC 772（
2*(5+5*2)/3+(6/2+8)，两栈都按"底 → 顶"写）：
全表最值钱的是帧 9 → 10：
) 先把括号内两层结算干净（
5*2、
5+10），
/ 再把括号外的
* 结掉（
2*15）——
挡板圈内圈外，各按各的优先级纪律。
五、变体与同族题
- LC 227 基本计算器 II：有
* / 但无括号。调度场照样通吃（少一个挡板分支）；更巧的单栈写法是"数字延迟一步结算"：新数字来临先不上栈，看栈顶运算符是 * / 就地合并，+ - 才把带符号数压栈 —— 扫完再求和。面试常拿 227 → 224 → 772 三连问，逐级加料。
- LC 150 逆波兰表达式求值：调度场的输出端。后缀表达式没有优先级和括号，单栈无脑结算 —— 反过来写一遍，正着就全懂了。
- LC 394 字符串解码：同款"括号上下文栈"。
[ ] 里存的从 {result, sign} 换成 {已拼好的字符串, 重复次数} —— 骨架一模一样，可回看本系列第 28 篇 LC 20。
- 递归下降（编译器的写法）：
expr := term (('+'|'-') term)*、term := factor (('*'|'/') factor)*、factor := 数字 | '(' expr ')' —— 三行文法直接翻成三个递归函数，优先级藏在调用深度里，括号藏在递归里。手写文法清晰但栈是隐式的；调度场是显式栈的迭代版。面试先问一句"允许递归吗"，两边都能写就是降维打击。
- 772 的腾讯式加料：追问方向通常是函数调用/变量/幂运算 —— 全都往
ops 栈里塞新元素、往优先级表里加新行即可，调度场的架构就是为扩展设计的。
六、Java 版
LC 224：
class Solution {
public int calculate(String s) {
Deque<int[]> stack = new ArrayDeque<>(); // {外层result, 括号sign}
int result = 0, sign = 1;
for (int i = 0; i < s.length(); ) {
char c = s.charAt(i);
if (c == ' ') { i++; }
else if (Character.isDigit(c)) {
int j = i;
while (j < s.length() && Character.isDigit(s.charAt(j))) j++;
result += sign * Integer.parseInt(s.substring(i, j));
i = j;
} else if (c == '+') { sign = 1; i++; }
else if (c == '-') { sign = -1; i++; }
else if (c == '(') {
stack.push(new int[]{result, sign});
result = 0; sign = 1; i++;
} else { // ')'
int inner = result;
int[] ctx = stack.pop();
result = ctx[0] + ctx[1] * inner;
i++;
}
}
return result;
}
}
（注意：Java 的
/ 本来就向零截断，
-3 / 2 == -1，比 Python 省心）：
class Solution {
public int calculate(String s) {
Deque<Long> nums = new ArrayDeque<>();
Deque<Character> ops = new ArrayDeque<>();
for (int i = 0; i < s.length(); ) {
char c = s.charAt(i);
if (c == ' ') { i++; }
else if (Character.isDigit(c)) {
long v = 0;
while (i < s.length() && Character.isDigit(s.charAt(i)))
v = v * 10 + (s.charAt(i++) - '0');
nums.push(v);
} else if (c == '(') { ops.push(c); i++; }
else if (c == ')') {
while (ops.peek() != '(') apply(nums, ops);
ops.pop(); i++;
} else {
while (!ops.isEmpty() && ops.peek() != '('
&& rank(ops.peek()) >= rank(c)) apply(nums, ops);
ops.push(c); i++;
}
}
while (!ops.isEmpty()) apply(nums, ops);
return nums.pop().intValue();
}
private int rank(char op) { return op == '+' || op == '-' ? 1 : 2; }
private void apply(Deque<Long> nums, Deque<Character> ops) {
char op = ops.pop();
long b = nums.pop(), a = nums.pop();
long r = switch (op) {
case '+' -> a + b;
case '-' -> a - b;
case '*' -> a * b;
default -> a / b; // 向零截断
};
nums.push(r);
}
}
中间结果用
long 存：
2147483647+1 这类输入会让
int 在
结算中途溢出，最后再
intValue() 截回是这类题的常规防御。
七、边界情况
- 空格满地跑：
" 2-1 + 2 "。逐字符扫时遇到空格跳过即可，别拿 split(' ') 制造一堆空串再过滤。
- 多位数：
"1-11" 必须切成 1、-、11 三个 token —— 连续数字合成一个数，两题共同的词法底线。
- 单数字 / 单括号：
"42"、"(1)" —— 有效表达式保证 nums 收尾恰剩一个数。
- 一元负号：LC 224 官方数据不含一元运算；但 772 的变体常给
"-2+5"、"2*(-3)"。标准处理：当 + - 出现在开头、( 之后、或另一个运算符之后，它不是二元运算符，是数字的一部分 —— 把它并进后面的数字（或先压一个 0 再按二元减处理）。
- 除法截断方向：题目要求向零取整（
-3/2 → -1）。JS Math.trunc(a/b)、Java/C++ 的 / 天然正确；Python // 是 floor（给 -2），必须换写法。
- 除零：LeetCode 数据保证不出现，面试口头确认一句即可。
八、复杂度
772 的
O(n) 值得多说一句：单个
) 帧可能一口气结算好几步（帧 9 弹了两步），看着像
O(n^2)；但每个运算符一生只被弹出一次，
摊还下来全程结算次数恰好等于运算符个数 —— 和 LC 232 双栈队列的均摊账是同款论证。
九、常见坑
9.1 结算判据写成 >：左结合当场坏
while prec[ops[-1]] > prec[c] —— 同级不结算，
10-2-3 的
ops 变成
[−, −]、
nums 变成
[10, 2, 3]，收尾从顶到底算出
10 - (2 - 3) = 11。
>= 是左结合的全部秘密，一个字符的差。
9.2 Python 用 // 做除法：负数截断方向错
-3 // 2 == -2（floor），题目要
-1（向零）。要么
int(a / b) 注意浮点精度，要么
sign * (abs(a) // abs(b))。JS/Java 没这坑，但面试官爱问"Python 怎么办"。
9.3 一元负号没处理
"2*(-3)" 按二元文法扫：
( 后面直接来
-，
ops 拿它当二元运算符和栈顶比较，
nums 少一个操作数，
apply 直接弹空。开头、
( 后、运算符后的
+ - 是
符号不是运算符 —— 见第七节。
9.4 224 的 (：先压栈再清零，顺序不能反
压栈的必须是
外层的
(result, sign)；先手痒把
result 清了再压，存进去的就是
{0, 1}，合并时外层账全丢。
9.5 772 的 )：结算到挡板后忘了弹挡板
while (ops[-1] != '(') apply() 之后必须
ops.pop() 把
( 摘掉 —— 不摘，它就是永久路障，后面所有优先级比较都被它挡住，表达式退化成"括号内永远最后算"。
9.6 扫完直接返回：忘了 flush 收尾
调度场的
ops 里可能还沉着没结账的低优先级运算符（例：
"2+3" 扫完
ops = [+]）。
while (ops) apply() 之后
nums[0] 才是答案 —— 递归下降没有这个问题，因为递归天然"算完再回"。
十、面试怎么答
- 先问清题目给了什么：有没有乘除？有没有括号？有没有一元负号？—— 224/227/772 就是这三个开关的三档组合，先定位自己在哪一档。
- 224：一句话立意"加减同级左结合，数字来一个结一个；栈只干一件事 —— 存括号的外层欠账"。写
{result, sign} 压栈 / 合并，O(n)。
- 772：从"为什么 224 的写法失效"讲起（
3 有资格等待右面的乘法），引出双栈调度场；把纪律说全：栈顶优先级 >= 我就先结账（>= 即左结合），( 是挡板，) 结算到挡板并弹掉，扫完 flush。
- 主动送分点：除法向零截断（Python
// 是坑）、中间结果用 long 防溢出、一元负号处理 —— 这三个细节说过任何一个，都证明你写过真的。
- 被追问扩展：函数/变量/幂运算都往
ops 和优先级表里加；要 AST 就换递归下降，三行文法直接翻代码。
结语
栈家族走到计算器这一站，凑齐了最后一块拼图：
224 证明栈能存"欠账"，772 证明栈能裁决"顺序"。口诀：
同级左结合，符号加欠账栈；优先级不齐，双栈排队等结算。
这是本系列第三十一篇。从 LC 20 的"括号配谁"，到 155 的"记住历史"、232 的"再翻一次"、239 的"按值排队"，再到今天 224/772 的"按优先级结算"—— 栈这个只会后进先出的数据结构，在六道题里换了六张面孔，但每次被逼出来的理由都一样：
当下处理不了、又不能丢的东西，交给栈。