LeetCode 772. 基本计算器 III

约 7 分钟
文章信息 22 个分类 4 个标签
分类
LeetCode CodeTop 困难 未解决 会员题 10-20 腾讯 字节 阿里 华为 微软 美团 拼多多 京东 百度 网易 滴滴 携程 B站 虾皮 金山 商汤
标签
字符串 数学 栈 递归

题目描述

✅ 772. 基本计算器 III

题意分析

计算一个包含整数、加减乘除、括号和空格的合法表达式。括号内先算，同一层中乘除优先于加减，同优先级运算按从左到右的顺序计算。

整数字面量按非负数读取，但减法和括号内计算可以得到负数。整数除法向零截断；只需返回计算结果，不需要保留表达式或调用通用表达式求值工具。

解法：递归处理括号 + 两级累计

核心思路

[!blue]

把一层表达式看成若干个用加减连接的乘除项。若读到一个数字就立刻把所有运算混在一起计算，后面出现乘除时便无法只修改它所属的项。因此分别维护 sum 和 term：sum 保存已经结束的项之和，term 保存当前尚可能继续乘除的带符号项。

op 记录当前操作数前面的运算符。读完一个完整操作数 num 后，按它更新状态：

  • 前置符号为 +：把旧 term 加入 sum，以 num 开始新项。
  • 前置符号为 -：同样结算旧项，以 -num 开始新项，把减法体现在项的符号中。
  • 前置符号为 * 或 /：只更新当前 term，不影响此前已经结束的项。

每次应用完整操作数后，sum + term 就是本层当前已读部分的值。乘除始终留在当前项中，并按扫描顺序执行，所以同时满足优先级和从左到右的结合顺序。初始 op = '+'、sum = term = 0，使首个操作数也能使用相同规则。

括号只负责产生一个完整操作数：遇到 ( 就递归计算其中表达式，将返回值作为当前层的 num，再应用当前层的 op。每层拥有自己的 sum、term 和 op，因此内层加减不会提前结算外层的乘除项。

扫描位置需要在递归层之间连续传递。Java 用共享的一元素数组保存下标，Go 同时返回计算值和下一下标；内层负责消费自己的 )，父层从括号后继续读取。遇到当前层右括号或字符串末尾时结束，返回 sum + term，把最后一个尚未结算的项一并计入。

解题步骤

  1. 从下标零开始解析，初始化本层 sum = 0、term = 0、op = '+'。
  2. 跳过空格，连续读取数字组成一个整数；若遇到左括号，则递归取得括号内结果。
  3. 根据操作数前的 op 更新状态：加减结束旧项并开启新项，乘除直接修改当前项。
  4. 跳过空格并读取下一个运算符；遇到当前层右括号或末尾则结束。
  5. 当前层消费自己的右括号，返回 sum + 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
}

复杂度分析

设字符串长度为 $n$，括号最大嵌套深度为 $h$。

  • 时间复杂度：$O(n)$。扫描位置始终向右，各层合计只读取每个字符常数次，不会重新扫描整个括号区间。
  • 辅助空间复杂度：$O(h+1)$，每层保存常数状态，顶层也占一个调用。

关键点总结

[!green]

  • 括号递归解决嵌套，sum 与 term 分开解决同层优先级。
  • op 属于当前操作数之前，只有完整读出操作数后才执行它。
  • 每层消费自己的右括号，并把更新后的扫描位置交还父层。
  • 最后一项还在 term 中，返回时必须加上它。

易错点总结

[!yellow]

  • 乘除直接修改总和，会把前面已经结束的加减项也卷进运算，破坏优先级。
  • 减法对应的当前项应保存为负值，后续乘除继续作用于这个带符号项。
  • 只在读到后续运算符时结算，容易漏掉最后一个操作数或最后一项。
  • 递归不共享或返回扫描位置，会重复读取内层内容；不消费自己的右括号，又会让父层提前结束。
  • 多位数按 num = num * 10 + digit 累积，不能把每个字符都当成独立操作数。
  • Java、Go 的整数除法都向零截断，不能改为对负数向下取整。

相似题目

题目 难度 关联与区别
224. 基本计算器 困难 复用括号与加减解析，再补充乘除优先级。
227. 基本计算器 II 中等 复用乘除优先级处理，再增加括号嵌套与递归返回。
394. 字符串解码 中等 用栈保存嵌套表达式的中间状态；本题同时处理括号与运算优先级，该题展开带重复次数的嵌套片段。
770. 基本计算器 IV 困难 计算器系列，复用表达式解析与运算优先级。IV 保留未替换变量，将中间结果表示为多项式。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/83573269
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！