LeetCode 224. 基本计算器
题目描述
题意分析
计算只含整数、加减号、括号和空格的表达式，返回最终结果。数字可能有多位，括号可以嵌套；负号既可能表示两数相减，也可能在表达式开头或左括号后表示取负，还可能作用于整个括号。
输入保证语法有效，数字和运算结果都在 32 位有符号整数范围内，无需处理非法表达式，也没有乘除优先级。空格不参与计算，不能调用直接执行字符串表达式的求值函数。
解法：栈保存括号外上下文
核心思路
[!blue]
同一层只有加减，可以把每一项看成带正负号的数，读完一项就累加，无需保留所有运算符。用
result保存当前层已经结算的和，num保存正在读取、尚未结算的数字，sign保存这一项应取的符号。数字字符通过
num = num * 10 + digit连成多位数。遇到新的+或-，说明前一个数字已结束，先把sign * num加入result，清零num，再让新运算符决定下一项的sign。字符串结束时也要做最后一次结算，因为末尾不一定有运算符触发它。遇到左括号时，整个括号将作为外层的一项参与运算，但它的值还不知道。把外层的
result和括号前的sign依次压栈，然后用result = 0、sign = 1开始计算内层。合法表达式中，左括号前不会紧跟一个未结算的数字，因此此时num已经为零。遇到右括号，先结算内层末尾的
num，再弹出外层符号与外层已有结果，按outerResult + outerSign * innerResult合并。栈后进先出，恰好让最内层先计算完，再逐层并回外面。合并后的括号值已经包含在
result中，所以代码将num保持为零。后面即使紧接运算符、另一个右括号或字符串结束，也只会额外结算零，不会把括号重复加一次；下一个运算符会重新设置符号，因此右括号处无需恢复旧的sign变量。一元负号也由同一流程处理：当前层开头
result、num都是零，读到负号时结算零，再把下一项的符号设为负。下一项可以是数字，也可以是完整的括号，不需要另设特殊分支。
解题步骤
- 初始化
result = 0、num = 0、sign = 1，从左到右扫描。- 遇到数字，用
num = num × 10 + digit拼接多位数。- 遇到
+或-，先把sign × num加入result，清空num，再更新下一个数字的符号。- 遇到
(，依次保存result和sign，然后重置当前层状态。- 遇到
)，先结算内层最后一个数字，再弹出符号和外层结果，合并为outerResult + outerSign × innerResult。- 空格直接忽略；扫描结束后补结算最后一个数字。
代码实现
class Solution {
public int calculate(String s) {
Deque<Integer> stack = new ArrayDeque<>();
int result = 0;
int num = 0;
int sign = 1;
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (Character.isDigit(ch)) {
num = num * 10 + ch - '0';
} else if (ch == '+' || ch == '-') {
result += sign * num;
num = 0;
sign = ch == '+' ? 1 : -1;
} else if (ch == '(') {
// 先保存外层结果再保存符号，出栈顺序正好相反。
stack.push(result);
stack.push(sign);
result = 0;
sign = 1;
} else if (ch == ')') {
result += sign * num;
num = 0;
// 内层最后数字已结算，先应用外层符号，再加回外层结果。
result *= stack.pop();
result += stack.pop();
}
}
return result + sign * num;
}
}
func calculate(s string) int {
stack := make([]int, 0)
result := 0
num := 0
sign := 1
for i := 0; i < len(s); i++ {
ch := s[i]
if ch >= '0' && ch <= '9' {
num = num*10 + int(ch-'0')
} else if ch == '+' || ch == '-' {
result += sign * num
num = 0
if ch == '+' {
sign = 1
} else {
sign = -1
}
} else if ch == '(' {
// 先保存外层结果再保存符号，出栈顺序正好相反。
stack = append(stack, result)
stack = append(stack, sign)
result = 0
sign = 1
} else if ch == ')' {
result += sign * num
num = 0
// 内层最后数字已结算，先应用外层符号，再加回外层结果。
result *= stack[len(stack)-1]
stack = stack[:len(stack)-1]
result += stack[len(stack)-1]
stack = stack[:len(stack)-1]
}
}
return result + sign*num
}
复杂度分析
- 时间复杂度：$O(n)$。每个字符只扫描一次，每个栈元素只进出一次。
- 空间复杂度：$O(n)$。最坏情况下括号嵌套深度与字符串长度同阶。
关键点总结
[!green]
- 只有加减时，括号可以抽象成“外层结果 + 外层符号 × 内层结果”。
- 栈保存的是括号外上下文，不是每个数字；这比通用双栈表达式求值更贴合本题。
- 运算符负责结算前一个数字，字符串结束时还要补一次结算。
- 若题目加入乘除，需要额外处理运算优先级，当前单纯的正负号模型就不够了。
易错点总结
[!yellow]
- 遇到运算符时必须先按旧符号结算前一个数字，再更新符号；扫描结束也要补结算，否则会漏掉末尾数字。
- 遇到
)时要先结算括号内最后一个数字，再清零num并恢复外层，避免漏算或重复结算。- 左括号前的符号必须和外层结果一起保存，尤其是减去整个括号时，负号要作用于内层的完整结果。
- 压栈与弹栈顺序必须匹配：代码先压
result再压sign，所以出栈时先取sign，再取result。- 多位数要按十进制拼接，空格不触发结算；逐字符扫描不等于把每个数字字符都当成独立的一项。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 227. 基本计算器 II | 中等 | 本题重点处理括号与加减，原题没有括号但增加乘除优先级。 |
| 772. 基本计算器 III | 困难 | 将括号与四则运算合在一起，需同时处理本题的嵌套状态与乘除优先级。 |
| 394. 字符串解码 | 中等 | 用栈保存嵌套表达式的中间状态；本题处理带括号的加减表达式，该题展开带重复次数的嵌套片段。 |
| 770. 基本计算器 IV | 困难 | 计算器系列。IV 在加减及括号解析上加入乘法和变量，还需合并多项式同类项。 |