LeetCode 772. 基本计算器 III
目录
题目描述
题意分析
给一个字符串形式的算术表达式，求它的值。表达式里可能出现非负整数、四则运算符
+ - * /、圆括号，以及任意位置的空格。要什么：一个整数结果。除法是整数除法，向零截断（例如
3/2得 1）。约束信号有三条。第一，运算符有优先级：乘除高于加减。这意味着不能简单地从左到右一路算下去。第二，有括号：括号内的表达式必须先算完，而且括号可以任意嵌套。第三，表达式保证合法，不会出现除零、不会有多余的运算符，也不会出现一元负号——所有减号都是二元的。这一点很重要，它省掉了大量特判。
空格可以出现在任何位置，包括数字和运算符之间，所以读取时必须随时准备跳过它们，但空格本身不携带任何语义，不能影响当前正在攒的数字或已记录的运算符。
边界情况包括：整个表达式就是一个数字；括号紧跟在运算符后面；括号内又嵌括号；表达式末尾是数字（后面没有运算符来触发结算）；以及多位数的连续读取。
解法：递归处理括号 + 两级累计
核心思路
括号与运算符优先级是两个独立问题：括号表示“先把这一段算成一个操作数”，适合递归；同一层内只有四则运算，用两个累计量即可处理优先级，不必构造表达式树，也不必额外维护栈。
解析每一层时维护：
sum：已经被加减号封口、以后不会再改变的项之和。term：当前尚未封口的乘除链结果。op：当前操作数前面的运算符。读到操作数
num后，若op是+或-，先把旧term加入sum，再以num或-num开启新项；若是*或/，直接更新term。这样乘除立即结算，加减延迟结算，优先级自然成立。遇到
(就递归解析，返回值被当成普通数字；当前层遇到)时返回。所有递归共享扫描位置，因此每个字符只经过一次。循环不变量是：sum + term始终等于当前层已读表达式的值。四种运算都按其结合规则更新这两个量，所以扫描结束返回sum + term正确。
解题步骤
- 从下标 0 调用解析函数，解析函数负责处理当前位置到同层右括号或字符串末尾。
- 跳过空格后读取一个操作数：连续数字组成多位数；若遇到左括号，则递归取得括号内结果。
- 根据前一个运算符更新
sum和term：加减封口旧项，乘除延长当前项。- 读取下一个运算符；若当前层遇到右括号，消费右括号并把本层结果返回。
- 顶层扫描结束后返回
sum + term。以
2*(5+5*2)/3为例：括号层把5+5*2算成 15；顶层的term依次变为 2、30、10，最终结果为 10。若把乘法也延迟到求和阶段，就会错误地把括号层算成5+5+2，这正是必须单独维护term的原因。
代码实现
class Solution {
public int calculate(String s) {
return parse(s, new int[1]);
}
private int parse(String s, int[] index) {
int sum = 0;
int term = 0;
char op = '+';
while (index[0] < s.length()) {
while (index[0] < s.length() && s.charAt(index[0]) == ' ') {
index[0]++;
}
if (index[0] == s.length() || s.charAt(index[0]) == ')') {
break;
}
int num = 0;
if (s.charAt(index[0]) == '(') {
index[0]++;
num = parse(s, index);
} else {
while (index[0] < s.length()
&& s.charAt(index[0]) >= '0'
&& s.charAt(index[0]) <= '9') {
num = num * 10 + s.charAt(index[0]++) - '0';
}
}
if (op == '+') {
sum += term;
term = num;
} else if (op == '-') {
sum += term;
term = -num;
} else if (op == '*') {
term *= num;
} else {
term /= num;
}
while (index[0] < s.length() && s.charAt(index[0]) == ' ') {
index[0]++;
}
if (index[0] < s.length() && s.charAt(index[0]) != ')') {
op = s.charAt(index[0]++);
}
}
if (index[0] < s.length() && s.charAt(index[0]) == ')') {
index[0]++;
}
return sum + term;
}
}
func calculate(s string) int {
value, _ := parseExpression(s, 0)
return value
}
func parseExpression(s string, index int) (int, int) {
sum, term := 0, 0
op := byte('+')
for index < len(s) {
for index < len(s) && s[index] == ' ' {
index++
}
if index == len(s) || s[index] == ')' {
break
}
num := 0
if s[index] == '(' {
index++
num, index = parseExpression(s, index)
} else {
for index < len(s) && s[index] >= '0' && s[index] <= '9' {
num = num*10 + int(s[index]-'0')
index++
}
}
switch op {
case '+':
sum += term
term = num
case '-':
sum += term
term = -num
case '*':
term *= num
case '/':
term /= num
}
for index < len(s) && s[index] == ' ' {
index++
}
if index < len(s) && s[index] != ')' {
op = s[index]
index++
}
}
if index < len(s) && s[index] == ')' {
index++
}
return sum + term, index
}
复杂度分析
- 时间复杂度：$O(n)$。递归层共享且只向前推进同一个下标，每个字符只被读取常数次。
- 空间复杂度：$O(h)$，其中 $h$ 是括号最大嵌套深度；除递归栈外只使用常数状态。
关键点总结
- 括号递归返回一个数，同层再用
sum + term处理两级优先级。op表示当前操作数前面的运算符，初始必须是+。- 不变量是
sum存已封口项、term存当前乘除项，因此sum + term始终等于已读部分。- 解析函数消费右括号并返回新下标，避免上层重复读取。
- 面试追问若要求支持更复杂语法，再升级为明确的
expression / term / factor递归下降；本题只有固定四则运算，不需要先建语法树。
易错点总结
- 只在读到下一个运算符时结算，会漏掉表达式最后一个操作数。
- 乘除直接并入
sum会破坏优先级；例如1+2*3应为 7。- 递归层不共享或不返回扫描位置，会重复解析括号内容。
- 返回前忘记消费
)，上层会把右括号误当成运算符。- 多位数必须按
num = num * 10 + digit累积。- Java 和 Go 的整数除法都向零截断，不能改成向下取整。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 227. 基本计算器 II | 中等 | 无括号的优先级处理 |
| 224. 基本计算器 | 困难 | 括号与一元负号 |
| 150. 逆波兰表达式求值 | 中等 | 后缀表达式栈求值 |
| LCR 036. 逆波兰表达式求值 | 中等 | 后缀式的整数除法语义 |
| 面试题 16.26. 计算器 | 中等 | 单层四则运算模拟 |