LeetCode 面试题 16.26. 计算器

约 5 分钟
文章信息 9 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 程序员面试金典（第 6 版） 腾讯 字节 京东
标签
字符串 数学 栈

题目描述

✅ 面试题 16.26. 计算器

image-20260928231120141

题意分析

计算由非负整数、加减乘除和空格组成的有效表达式，不包含括号，也不能直接调用表达式求值函数。乘除优先于加减，同一优先级按从左到右计算。

一个整数可能有多位，空格需要跳过。除法只保留整数部分，即向零截断；减法可能使中间结果为负，这时也要遵循相同规则。最后返回表达式的整数结果。

解法：单次扫描维护上一段结果

核心思路

[!blue]

加减号可以把表达式分成若干带符号的乘除链。链内运算要先完成，再把各链相加。因此不必保存所有运算符，只需用 last 保存仍可能参与后续乘除的当前链，用 answer 保存已经结束的链之和。

扫描时，num 按十进制累积当前整数，op 保存它前面的运算符。直到遇到下一个运算符或字符串末尾，当前数字才完整，可以用旧 op 结算。新读到的运算符只是给下一个数字准备的，不能拿来提前处理当前数字。

若旧 op 为加或减，当前数字开始一条新链：将旧 last 加入 answer，再把 last 设为 num 或 -num。若旧 op 为乘或除，当前数字还属于同一链，直接更新 last，暂不写入总和。链内按读取顺序执行，所以连续乘除保持左结合。

减号作为整条链的符号保存在 last 中。Java 和 Go 的整数除法都向零截断，带负号链的除法与先算正链再取负相符。首个数字前默认是加号，让它也使用同一套结算逻辑。

空格通常不触发结算，但最后一个字符即使是空格，也必须结算尚未处理的数字。循环结束时，当前最后一条链仍保存在 last，返回 answer + last 才是完整结果。

解题步骤

  1. 初始化已结束部分 answer = 0、当前链 last = 0、数字 num = 0，旧运算符设为加号。
  2. 读取数字字符时，用 num = num * 10 + 当前位 累积多位整数。
  3. 读到运算符或到达末尾时，用旧 op 处理完整的 num：加减开启新链，乘除延长当前链。
  4. 将新字符保存为下一次使用的运算符，并清空数字累加器；中间空格直接跳过。
  5. 遍历完成，返回已结束链之和加最后一条链。

代码实现

class Solution {
    // 可以把已经确定不会再参与乘除的部分累加到 ans，把当前乘除链的值保存在 last。
    public int calculate(String s) {
        int answer = 0;
        int last = 0;
        int num = 0;
        // 保存当前数字之前的运算符，第一个数字视作加号后的一项。
        char op = '+';

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c >= '0' && c <= '9') {
                num = num * 10 + (c - '0');
            }

            if ((c < '0' || c > '9') && c != ' ' || i == s.length() - 1) {
                if (op == '+') {
                    answer += last;
                    last = num;
                } else if (op == '-') {
                    answer += last;
                    // 减法转为带符号的乘除链，后续除法仍向零截断。
                    last = -num;
                } else if (op == '*') {
                    last = last * num;
                } else if (op == '/') {
                    last = last / num;
                }

                op = c;
                num = 0;
            }
        }

        // 最后一条链尚未并入，返回时补上。
        return answer + last;
    }
}

func calculate(s string) int {
    // 可以把已经确定不会再参与乘除的部分累加到 ans，把当前乘除链的值保存在 last。
    answer := 0
    last := 0
    num := 0
    // 保存当前数字之前的运算符，第一个数字视作加号后的一项。
    op := byte('+')

    for i := 0; i < len(s); i++ {
        c := s[i]
        if c >= '0' && c <= '9' {
            num = num*10 + int(c-'0')
        }
        if (c < '0' || c > '9') && c != ' ' || i == len(s)-1 {
            if op == '+' {
                answer += last
                last = num
            } else if op == '-' {
                answer += last
                // 减法转为带符号的乘除链，后续除法仍向零截断。
                last = -num
            } else if op == '*' {
                last = last * num
            } else if op == '/' {
                last = last / num
            }

            op = c
            num = 0
        }
    }

    // 最后一条链尚未并入，返回时补上。
    return answer + last
}

复杂度分析

  • 时间复杂度：$O(n)$，每个字符读取一次，数字和运算符的处理均为常数次操作。
  • 空间复杂度：$O(1)$，只维护已结束总和、当前链、当前数字和前一个运算符。

关键点总结

[!green]

  • 把乘除优先级体现在延迟提交当前链上，无需保存整个表达式栈。
  • 完整数字由它前面的运算符处理，新运算符留给下一数字。
  • 减号并入当前链的符号，连续乘除仍按原顺序计算。
  • 末尾触发最后数字结算，返回时再补入最后一条链。

易错点总结

[!yellow]

  • 读到一个运算符就用它处理前面的数字，混淆了旧运算符与下一运算符的作用。
  • 每处理一个数字就直接累加总和，后续乘除无法再与前项结合，破坏优先级。
  • 减法分支没有把新链取负，后面合并总和时就会把它误当加法。
  • 只在运算符位置结算，会漏掉字符串最后一个数字，末尾空格也需要触发收尾。
  • 返回时遗漏 last，最后一条链尚未加入 answer，结果会少一段。
  • 用向下取整代替向零截断，负链执行除法时会得到不同结果。

相似题目

题目 难度 关联与区别
224. 基本计算器 困难 原题支持括号与加减，本题增加乘除优先级，遇乘除时需先合并。
772. 基本计算器 III 困难 在本题四则运算基础上加入括号嵌套，可用递归或额外状态栈处理。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/70406468
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！