基本计算器 II 图解题解

这道题到底在问什么

s

"3+2*2"

输出

7

为什么

2*2=4 先算,再 3+4=7

最优解：一步一步想明白

1. 3能做对,但要扫两遍、还要原地改写字符串,代码又长又容易错。有没有一遍搞定的办法?
2. 4关键招:加减是「记账,先存着」,乘除是「马上和栈顶结算」。最后把栈里所有数一加,就是答案——优先级被栈自动摆平了。
3. 5下面用 "3+2*2" 一个字符一个字符地演。上排是输入流,下面是栈。盯住 op(待执行的符号) 和栈怎么变。
4. 6栈空,num=0,op=+约定:把 op 初始设成 +,这样第一个数也能像「+num」一样被正常压栈。指针还没出发,栈是空的。
5. 7拼数字 num = 3第 1 个字符是数字 3,先把它攒进 num(num = 0×10+3 = 3)。数字只攒不结算,要等碰到符号才动手。
6. 8压 +3 → 栈 [3]碰到符号 +!先用上一个 op(还是初始的 +)结算 num:op 是 + → 把 +3 压栈。然后把 op 更新成这个 +,num 清零。
7. 9拼数字 num = 2第 3 个字符是数字 2,攒进 num。栈不动,还是 [3]。继续往后看符号。
8. 10op 是 + → 压 +2 → 栈 [3, 2]碰到 *!但要先用上一个 op(+)把刚攒的 num=2 结算掉:压 +2,栈变 [3, 2]。然后才把 op 更新成 *,num 清零。
9. 11拼数字 num = 2op 此刻挂着 *(待办:下一个数和栈顶相乘)。最后一个字符数字 2 攒进 num。走到末尾了——即使后面没符号,也要触发一次结算,否则这个 num 漏掉。
10. 12弹出 2,压 2*2=4 → 栈 [3, 4]op 是 *!不是直接压,而是先弹出栈顶 2,算 2 × 2 = 4,再把 4 压回去。栈变 [3, 4]——乘法就地把栈顶替换成了乘积。
11. 133 + 4 = 7 ✓字符串走完。栈里全是带符号、且乘除已算完的数,直接相加:3 + 4 = 7。先乘后加的优先级,全程没专门判断,被栈悄悄摆平了。
12. 14换 14-3/2 走一遍。这次专盯减号怎么变成压负数,以及除法对栈顶动手。
13. 15栈空,num=0,op=+同样把 op 初始设成 +。输入流是 1 4 − 3 / 2,栈空,准备开扫。
14. 16num = 0×10+1 = 1第 1 个字符 1,num = 0×10+1 = 1。栈还空着。下一位若还是数字,就要拼成多位数。
15. 17num = 1×10+4 = 14第 2 个还是数字 4:num = 1×10+4 = 14。这就是多位数的拼法——每来一位就把已有的 ×10 再加上新位。
16. 18op 是 + → 压 +14 → 栈 [14]碰到 −:先用上一个 op(+)结算 num=14 → 压 +14。然后把 op 更新成 −。注意 − 本身不立刻减,它只是「挂起」,作用在下一个数上。
17. 19num = 3数字 3 攒进 num。此刻 op 挂着 −:意味着这个 3 将来要以负数身份进栈。栈暂时还是 [14]。
18. 20op 是 − → 压 −3 → 栈 [14, -3]碰到 /:先用上一个 op(−)结算 num=3 → 压 −3,栈变 [14, −3]。减法就是「压一个负数」,这样最后求和时它自然被减掉。然后 op 更新成 /。
19. 21num = 2,到末尾op 此刻挂着 /,栈顶是带符号的 −3(影响取整方向)。最后字符 2 攒进 num,到末尾了,要触发末尾结算——别漏掉这个 2。
20. 22弹出 −3,压 (−3)/2 = −1 → 栈 [14, -1]op 是 /:弹出栈顶 −3,算 (−3) / 2。题目要求向零取整:−1.5 朝 0 取整 = −1(不是 −2!),压回去。栈变 [14, −1]。
21. 2314 + (−1) = 13 ✓走完了!栈里 [14, −1] 直接相加 = 13。减号变负数、除法就地结算栈顶,加减乘除四则混合一遍扫完。
22. 24op=+ 压 +2 → 栈 [2],op 转 *再快走一遍乘法当头的 2*3+4:2 攒着→遇 * 先用初始 + 压 +2,栈 [2],op 转成 *。
23. 25pop 2,压 2×3=6 → 栈 [6]3 攒着→遇 +:先用挂着的 * 结算——pop 2,压 2×3=6,栈 [6]。乘法又一次就地把栈顶替换成乘积。op 转 +。
24. 26压 +4 → [6,4],和 = 104 攒着→末尾用 + 压 +4,栈 [6, 4],求和 = 10。三个例子都印证:加减记账、乘除即时改栈顶。
25. 27整条式子从左到右只走了一遍,优先级靠「加减压栈、乘除即时结算栈顶」自动处理,没有任何回头或重写——这就是栈的威力。
26. 30想透这点这题就通了:加减是「我先存着,回头一起算」,乘除是「我级别高,马上把栈顶改掉」。这套「延迟低优先、即时高优先」是表达式求值的通用骨架。
27. 32扫到末尾不补刀 → num=2 漏算若只在「碰到符号」时结算,最后那个 2 后面没符号,就永远不会触发结算:栈停在 [3,2],错算成 5(正解 7)。所以条件里必须带上 i == 末尾。
28. 33末尾触发 * 结算 → [3, 4]把 i == 末尾 写进条件,末尾这个 2 就能触发一次 * 结算:弹 2、压 2×2=4,栈成 [3,4],求和 = 7,正确。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def calculate(self, s):
        stack = []
        num, op = 0, '+'              # op: 上一个运算符,初始 +
        for i, ch in enumerate(s):
            if ch.isdigit():
                num = num * 10 + int(ch)   # 拼多位数
            if (not ch.isdigit() and ch != ' ') or i == len(s) - 1:
                if op == '+':   stack.append(num)
                elif op == '-': stack.append(-num)
                elif op == '*': stack.append(stack.pop() * num)
                elif op == '/': stack.append(int(stack.pop() / num))
                op, num = ch, 0           # 更新 op,清零 num
        return sum(stack)

class Solution {
public:
    int calculate(string s) {
        vector<int> stk;
        int num = 0, n = s.size(); char op = '+';
        for (int i = 0; i < n; i++) {
            char ch = s[i];
            if (isdigit(ch)) num = num * 10 + (ch - '0');
            if ((!isdigit(ch) && ch != ' ') || i == n - 1) {
                if (op == '+') stk.push_back(num);
                else if (op == '-') stk.push_back(-num);
                else if (op == '*') { int t = stk.back(); stk.pop_back(); stk.push_back(t * num); }
                else if (op == '/') { int t = stk.back(); stk.pop_back(); stk.push_back(t / num); }
                op = ch; num = 0;
            }
        }
        int sum = 0; for (int v : stk) sum += v; return sum;
    }
};

class Solution {
    public int calculate(String s) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
        int num = 0, n = s.length(); char op = '+';
        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) num = num * 10 + (ch - '0');
            if ((!Character.isDigit(ch) && ch != ' ') || i == n - 1) {
                if (op == '+') stack.push(num);
                else if (op == '-') stack.push(-num);
                else if (op == '*') stack.push(stack.pop() * num);
                else if (op == '/') stack.push(stack.pop() / num);
                op = ch; num = 0;
            }
        }
        int sum = 0; for (int v : stack) sum += v; return sum;
    }
}

复杂度

面试官可能追问