LeetCode 224. 基本计算器
目录
题目描述
题意分析
输入是一个合法的表达式字符串，只包含非负整数、
+、-、括号和空格，要求算出它的值。约束里有两个重要信号：一是没有乘除，所有运算优先级相同，只有括号会改变计算顺序；二是-可能是一元负号，比如"-(2+3)"、"-2+1"，负号前面没有左操作数。边界上还要留意：数字可能是多位数（
"123"要拼成一个整数而不是三个）；空格可以出现在任何位置，必须被无视；括号可以嵌套任意多层，如"(1+(4+5+2)-3)"。也就是说，难点不在「算加减」，而在「括号改变了外层与内层的关系」以及「负号不一定是减法」这两件事上。
解法：栈保存括号外上下文
核心思路
问题关键：表达式只有加减，优先级本身不难；难点是多位数、嵌套括号和一元负号。反复寻找最内层括号并替换字符串会产生重复扫描，最坏达到 $O(n^2)$。
为什么选栈：扫描到
(时，当前层还没算完，只需保存“括号外已累计的结果”和“括号前的符号”；扫描到)时恢复这两个值即可。因为只有加减，括号整体只会以+1或-1的系数并回外层，不需要通用的运算符优先级栈。状态定义与不变量：
result表示当前括号层已结算的值，num表示正在读取的数字，sign表示num前的符号。任意扫描位置，result + sign × num就是当前层已读取部分的值；栈中按层保存每个未闭合括号的(outerResult, outerSign)。遇到左括号时压入外层状态，并从
result = 0、sign = 1开始计算内层；遇到右括号时先结算内层最后一个数，再计算outerResult + outerSign × innerResult。表达式开头或左括号后的-可视为0 - x，无需单独分支。
解题步骤
- 初始化
result = 0、num = 0、sign = 1，从左到右扫描。- 遇到数字，用
num = num × 10 + digit拼接多位数。- 遇到
+或-，先把sign × num加入result，清空num，再更新下一个数字的符号。- 遇到
(，依次保存result和sign，然后重置当前层状态。- 遇到
)，先结算内层最后一个数字，再弹出符号和外层结果，合并为outerResult + outerSign × innerResult。- 空格直接忽略；扫描结束后补结算最后一个数字。
例如
1-(2-3)：进入括号前保存(1,-1)，内层算得-1，出括号后合并为1 + (-1) × (-1) = 2。
代码实现
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)$。最坏情况下括号嵌套深度与字符串长度同阶。
关键点总结
- 只有加减时，括号可以抽象成“外层结果 + 外层符号 × 内层结果”。
- 栈保存的是括号外上下文，不是每个数字；这比通用双栈表达式求值更贴合本题。
- 运算符负责结算前一个数字，字符串结束时还要补一次结算。
- 若题目加入乘除，需要额外处理运算优先级，当前单纯的正负号模型就不够了。
易错点总结
- 遇到运算符时必须先结算前一个数字；扫描结束也要补结算，否则
1+2会漏掉末尾的 2。- 遇到
)时要先结算括号内最后一个数字，再恢复外层；(1+2)中的 2 否则不会进入内层结果。- 左括号前的符号必须和外层结果一起保存。
-(2+3)若丢失符号会被算成 5。- 压栈与弹栈顺序必须匹配：代码先压
result再压sign，所以出栈时先取sign，再取result。- 多位数要十进制拼接，空格要忽略；不能把
12当作两个独立数字。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 150. 逆波兰表达式求值 | 中等 | 后缀表达式无括号无优先级，纯操作数栈即可 |
| 227. 基本计算器 II | 中等 | 无括号但有乘除，需对上一个操作数延迟结算 |
| 772. 基本计算器 III | 困难 | 括号与乘除并存，符号上下文叠加优先级处理 |
| LCR 036. 逆波兰表达式求值 | 中等 | 150 的镜像题，巩固后缀求值的入栈出栈模板 |
| 面试题 16.26. 计算器 | 中等 | 227 的变体，练习中缀四则运算的一遍扫描写法 |