227. Basic Calculator II

──────────────────────────────────────────────────────────────────────

實作一個只有 + - * / 的計算機，沒有括號，除法往零取整。

Calculator 的題組有

但是難度不是按照順序遞增的，這一題才是題組的基礎功 —— 224 和 772 都是在這個骨架上加東西。

思路

跟 394. Decode String 一樣，看到「從左到右掃一遍字串、而且有巢狀或優先權」就該想到 stack。但兩題 pop 的時機完全不同，這裡要先搞清楚一件事。

什麼時候才能動手算

掃描 "2 + 3"，走到 + 的時候能不能算？不行，右邊的運算元還沒讀完。

那什麼時候才知道 3 讀完了？看到下一個運算符，或是走到字串結尾。

所以整個掃描是延遲一拍的 —— 每次遇到運算符，結算的是上一個運算符欠下的那筆帳。這就是 sign 這個變數存在的理由：它記住「還欠著沒算的那個運算符」。

看 "2 - 3 + 1"：走到 + 的時候，手上的 num 是 3，但該套用的是前面那個 -。如果拿當下的 + 去算，就變成 2 + 3 了。所以流程固定是「先用舊的 sign 結算，再把 sign 換成當下這個」。

sign 初始化成 '+'，是因為第一個數字前面沒有運算符，把它當成 0 + 第一個數 就統一了。題目保證 - 只會當運算符、不會當正負號，所以第一個數一定是正的。

乘除的優先權才是真正的難點

這也是 stack 存在的理由。規則只有兩條：

遇到 + / - —— 先不算，把 +num 或 -num 推進 stack
遇到 * / / —— 立刻算，把棧頂拿出來跟 num 運算，結果推回去

"2 - 3 * 4 + 5"

+2   →  [2]
-3   →  [2, -3]
*4   →  [2, -12]      ← 立刻算掉，取代棧頂
+5   →  [2, -12, 5]
                       sum = -5

掃完之後，stack 裡每一項都是「乘除已經消化完的項」，項與項之間只剩加法 —— 所以最後一行 sum(stack) 就結束了。

一句話：stack 把「先乘除後加減」轉成「乘除當場算掉，加減留到最後一起加」。 這樣就不必真的去寫運算子優先權的解析。

解題方向

class Solution:
    def calculate(self, s: str) -> int:
        num, stack, sign = 0, [], "+"
        for i in range(len(s)):
            if s[i].isdigit():
                num = num * 10 + int(s[i])
            if s[i] in "+-*/" or i == len(s) - 1:
                if sign == "+":
                    stack.append(num)
                elif sign == "-":
                    stack.append(-num)
                elif sign == "*":
                    stack.append(stack.pop()*num)
                else:
                    stack.append(int(stack.pop()/num))
                num = 0
                sign = s[i]
        return sum(stack)

三個地方值得單獨拿出來看。

兩個 if 是平行的，不是 elif。 最後一個字元如果是數字，它要先被累加進 num，然後同一輪馬上被 i == len(s) - 1 觸發結算。寫成 elif 就會漏掉最後一個數字。

空白不用特別處理。 空白既不是數字也不在 "+-*/" 裡，兩個 if 都不會進去，自然被跳過。而如果字串結尾是空白，i == len(s) - 1 一樣會觸發結算，此時 num 早就累積完了。

除法要用 int(a / b) 而不是 a // b。 題目要求往零取整，而 Python 的 // 是往下取整，兩者遇到負數會不一樣：

"1-6/4"

# 走到 '/' 時 sign 是 '-'，所以推進 stack 的是 -6
# 結算：int(-6 / 4) = -1     ✅  → 1 + (-1) = 0
#      -6 // 4     = -2     ❌  → 1 + (-2) = -1

負數是怎麼跑出來的？因為這個做法把減號折進了數字本身（- 就是推 -num），所以除法的被除數可能是負的 —— 就算題目的輸入全是正整數也一樣。

補充

整個題組的關係：

題目	運算子	括號	相對這題多了什麼
227	`+ - * /`	無	—— 基礎骨架
224	`+ -`（`-` 也可當負號）	有	遞迴處理括號
772	`+ - * /`	有	前兩題的聯集
394	重複字串	有	同骨架，運算元換成字串

先把這題寫熟，後面三題都只是加東西。

反過來也成立：772 那份帶遞迴的 helper 一字不改就能解 227 和 224，因為它是三題的聯集。這裡保留不含遞迴的版本，是因為沒有括號的時候用索引掃就夠了，不必轉成 deque。

更多 Stack 的題目 → #Stack，模板見單調棧模板（那篇講的是另一種用法，但「什麼時候該 pop」的思路是相通的）。

複雜度

時間 $O (n)$ — 每個字元只看一次，stack 的每一項也只被推入和取出各一次
空間 $O (n)$ — 全部都是加減時，stack 會裝下每一個數字

其中 $n$ 是字串長度。