LeetCode 面试题 16.26. 计算器

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

题目描述

✅ 面试题 16.26. 计算器

题意分析

给一个字符串形式的表达式，里面只有非负整数、+ - * / 四种运算符和空格，求它的值。除法是整数除法，直接截断小数部分。

「没有括号」是最重要的约束。没有括号意味着表达式不存在嵌套结构，不需要递归下降，也不需要为括号维护一层层的上下文；剩下的全部难点只有一个——乘除优先于加减。

「有空格」和「数字可能是多位」这两条合在一起说明：不能把字符直接当数字用，必须一位位攒出完整的数，而且只有在遇到下一个运算符或者走到字符串末尾时，才能确认这个数已经读完。

「结果保证在 int 范围内」则说明不用操心大数，可以专心处理优先级。

边界：只有一个数字（"42"）；开头、中间、结尾都可能有空格；表达式的最后一个字符必然是数字，扫描必须在越界前把它结算掉；除法截断要向零取整，比如 "14-3/2" 的答案是 13 而不是 12。

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

核心思路

暴力做法是两趟：第一趟把字符串切成数字与运算符的序列，把所有 * 和 / 就地算掉并把结果替换回序列；第二趟把剩下的加减从左到右求和。这个思路是对的，但要额外建一个可删除元素的序列，而且第二趟其实只是简单求和，完全没必要把整段留到最后。

观察运算符在扫描过程中扮演的角色：读到 + 或 -，说明它左边那一串连乘连除已经彻底定型，再也不会被后面的东西改变；读到 * 或 /，说明前面那个数还得继续参与运算。也就是说，加减是「结算」信号，乘除是「继续」信号。

顺着这个区分，把答案拆成两部分：answer 保存已经彻底结算完、不可能再被后续运算影响的部分；last 保存当前这条乘除链的值（带符号）。读到加减就把 last 并入 answer，然后让 last 变成新读到的数；读到乘除就直接把 last 与新数运算，链继续生长。

循环不变量是：每处理完位置 i 上的运算符后，answer + last 恰好等于前缀 s[0..i) 的值，且 last 是这段前缀里最后一条连续乘除链的值。扫描结束时整个串就是一个前缀，返回 answer + last 即可。

这其实就是栈解法的 $O(1)$ 空间版本：用栈时，栈顶保存的正是当前乘除链，栈里其余元素只等着最后求和，既然如此不如直接用一个变量把它们边加边扔。

还需要两个辅助变量：num 是正在攒的数字，op 是上一个运算符。结算动作永远滞后一步——不是读到运算符就用它来算，而是用它之前记下的那个 op 来结算刚攒好的 num，因为只有到这一刻 num 才读完整。op 初始化成 '+'，让第一个数走「并入」分支，天然成为第一条链的起点。

解题步骤

  • 初始化 answer = 0、last = 0、num = 0、op = '+'：op 的初值不能省。第一个数前面没有真实的运算符，假装有个 + 才能让它落进 last = num 这条分支。
  • 数字位就累积：num = num * 10 + (c - '0')，多位数靠这一行拼出来，一位一位地攒，攒到确认读完为止。
  • 结算时机是「当前字符是运算符」或「已经到最后一个字符」：两者用 || 连起来。后半个条件不可省——表达式以数字结尾，如果只在遇到运算符时结算，最后一个数永远进不了 answer。
  • 空格必须排除在触发条件之外：条件里的 c != ' ' 保证空格既不累积数字也不触发结算，只是被跳过。少了它，一个空格就会用错误的 op 提前结算一次，并把 op 污染成 ' '。
  • 按 op 分四路结算：+ 时 answer += last; last = num，- 时 answer += last; last = -num——减法通过给 last 取负内化成加法，后续所有并入操作就都只是加；* 和 / 时直接 last = last * num 或 last = last / num，answer 不动，因为这条链还没定型。
  • 结算后记录 op = c 并清空 num：清空是必须的，否则下一个数会拼在这个数后面。当 i 是最后一个字符时 c 是数字，op 会被赋成一个数字字符，但循环随即结束，这个值不会再被读到。
  • 返回 answer + last：最后一条乘除链还留在 last 里，必须补上。

以 "3+2*2-6/4" 走一遍（正确答案是 3 + 4 - 1 = 6）：

  • 初始：answer = 0，last = 0，num = 0，op = '+'
  • i = 0，'3' → num = 3
  • i = 1，'+' → 按 op = '+' 结算：answer += last 仍为 0，last = 3；记 op = '+'，num = 0
  • i = 2，'2' → num = 2
  • i = 3，'*' → 按 op = '+' 结算：answer += 3 得 3，last = 2；记 op = '*'，num = 0
  • i = 4，'2' → num = 2
  • i = 5，'-' → 按 op = '*' 结算：last = 2 * 2 = 4，answer 保持 3（这条乘法链还没并入）；记 op = '-'，num = 0
  • i = 6，'6' → num = 6
  • i = 7，'/' → 按 op = '-' 结算：answer += 4 得 7，last = -6；记 op = '/'，num = 0
  • i = 8，'4' → num = 4，同时 i 已是最后一个下标，触发结算：按 op = '/' 得 last = -6 / 4 = -1
  • 返回 answer + last = 7 - 1 = 6

留意 i = 7 那一步：answer 并入的是上一条链的值 4，而不是刚读到的 6，这正是「滞后一步结算」的意义。也留意最后一步，last 是负数，-6 / 4 在 Java 和 Go 里都向零取整得 -1，与「先算 6 / 4 = 1 再取负」结果一致，所以把减法转成负数不会破坏截断语义。

代码实现

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)$，全程只用 answer、last、num、op 四个标量。显式用栈的写法要把每条乘除链的结果压进栈里最后统一求和，那才是 $O(n)$；这里把「等待求和的那些元素」提前加进了 answer，栈就退化成了一个变量。

关键点总结

  • 「已结算的 answer + 待结算的 last」这个二分拆解，是无括号表达式求值的通用模板。能把不变量 answer + last = 当前前缀的值 说清楚，这题在面试里基本就过了。
  • 结算必须滞后一步：用上一个运算符去结算刚读完的数字。多位数只有在遇到下一个运算符或走到末尾时才算读完，提前结算必然把数字截断。
  • 末尾条件 i == n - 1 与运算符条件是并列的触发源，两者缺一个，最后一个数或中间某个数就会被漏掉。
  • 减法通过 last = -num 内化成加法，四个分支里只有加减推进 answer，乘除只改 last——这个不对称正是优先级的体现。
  • last 可能为负，代码依赖的是「整数除法向零取整」这一语言特性。Java 和 Go 都满足，但在 Python 这类向下取整的语言里必须改写成先取绝对值算完再补符号。
  • 面试时的稳妥表达顺序是：先给出栈版本证明思路正确，再指出栈底元素只用来求和、可以用一个累加变量替代，把空间优化到 $O(1)$。主动做这一步优化通常是加分项。

易错点总结

  • 只在遇到运算符时结算，漏掉 i == n - 1：输入 "1+2" 时末尾的 2 从未被结算，返回 1。
  • 数字按单字符处理（num = c - '0'）：输入 "12+3" 会被拆成 1 和 2 两个数，返回 5 而不是 15。
  • 触发条件忘记排除空格：输入 "3 + 2" 时 i = 1 的空格会用 op = '+' 提前结算，并把 op 污染成 ' '，后续所有分支都命中不了，最终返回 3 而不是 5。
  • 结算后忘记 num = 0：输入 "1+2+3" 时第二个数会拼成 12、第三个拼成 123，结果彻底跑偏。
  • 不记录 op，一律按加法结算：输入 "2*3" 返回 5 而不是 6。
  • op 初值不设成 '+'：输入 "42" 时第一个数落不进任何分支，last 始终为 0，返回 0。
  • 减法时压入 num 而不是 -num：输入 "1-2*3" 会把 2*3 当成正的并入，返回 7 而不是 -5。
  • 返回 answer 而忘了加 last：输入 "1+2" 时 2 还留在 last 里，返回 1。
  • 除法用浮点或四舍五入：输入 "14-3/2" 时 3/2 被算成 2，返回 12，正确答案是 13。
  • 先按运算符 split 再从左到右依次计算：输入 "2+3*4" 会按顺序算成 (2+3)*4 = 20，正确答案是 14——优先级不处理，整题就没做。

相似题目

题目 难度 考察点
227. 基本计算器 II 中等 与本题同型的官方版本，输入同样无括号，可原样套用这份代码
150. 逆波兰表达式求值 中等 输入已是后缀式，优先级由顺序编码好了，只需一个数栈，无需 last
224. 基本计算器 困难 有括号但没有乘除，难点转成用栈保存括号外的符号与部分和
772. 基本计算器 III 困难 括号与乘除同时存在，需要递归下降或双栈，本题的四变量写法不够用
1006. 笨阶乘 中等 运算符按固定周期出现，同样靠「累加已结算 + 保留当前乘除链」求解
LCR 036. 逆波兰表达式求值 中等 与 150 同题，可直接套用