772. Basic Calculator III

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

772. Basic Calculator III

+ - * / 加上括號 —— 227 和 224 的聯集。

思路

前面兩題解完，這題題目有變化，骨架沒變化：

• 乘除的優先權 → 用 stack，+ - 先推進去、* / 當場算掉棧頂（來自 227）
• 括號 → 遇到 ( 就遞迴，回傳值當成一個運算元（來自 224）

所以直接沿用 224 的程式碼就好。而且不只是「差不多」—— 這份 helper 一字不改就能解掉整個題組的三題，因為它涵蓋的是三題的聯集：有乘除的分支、有括號的遞迴，而 227 沒有括號、224 沒有乘除，各自只是用不到其中一部分而已。

結算的條件要用排除法，不要用列舉法

這是這題唯一需要想清楚的地方。什麼時候該結算手上那筆帳？

if not c.isdigit() and not c.isspace() or len(s) == 0:

（and 比 or 優先，讀作「不是數字也不是空白」或「字串走完了」。）

意思是：只要碰到任何一個「不是數字、也不是空白」的字元，就代表當前的運算元讀完了，該結算了。 +、-、*、/、(、) 全部落在這個範圍裡，一個都跑不掉。

我原本想「簡化」成直接列舉運算符：

if c in '+-*/' or len(s) == 0:      # ❌ 少了 ')'

結果就出事了 —— 下面那一段是這個 bug 的完整分析，很值得留著。

那個 bug：) 也是結算點

) 不在 '+-*/' 裡面。所以走到 ) 的時候，手上累積的 num 沒有被結算就直接 break 了 —— 除非這個 ) 剛好是整個字串的最後一個字元，被 len(s) == 0 救回來。

這讓 bug 變得很陰險，因為括號單獨拿出來算是對的：

"(5+5*2)"              → 15   ✅   ) 是最後一個字元，len(s) == 0 觸發結算
"2*(5+5*2)/3"          → 6    ❌   正解 10
"2*(5+5*2)/3+(6/2+8)"  → 17   ❌   正解 21

拆開來看第二個例子，內層 helper 處理 5+5*2)：

c = '5'  → num = 5
c = '+'  → 結算，推入 5          stack = [5],  sign = '+'
c = '5'  → num = 5
c = '*'  → 結算，推入 5          stack = [5, 5],  sign = '*'
c = '2'  → num = 2
c = ')'  → 不在 '+-*/' 裡，而且後面還有 "/3"，所以 len(s) != 0
           → 什麼都沒做就 break
           → 那筆欠著的 5 * 2 從此消失

return sum([5, 5]) = 10        正解是 5 + 5*2 = 15

用排除法就不會有這個問題，因為 ) 本來就不是數字也不是空白。列舉法要求你把所有分隔符都記全，漏一個就錯；排除法只要求你說清楚「什麼東西不是分隔符」，而那只有兩種：數字和空白。

真正的教訓不在 ) 這個字元，而在：遞迴的邊界字元同時也是結算觸發點。 只要是「掃到某個字元就 return」的遞迴，離開之前都要先問一句「手上還有沒有沒結算完的東西？」

解題方向

class Solution:
    def calculate(self, s: str) -> int:
        def helper(s):
            num = 0
            stack = []
            sign = '+'
            while s:
                c = s.popleft()
                if c.isdigit():
                    num = 10 * num + int(c)
                if c == '(':
                    num = helper(s)
                if not c.isdigit() and not c.isspace() or len(s) == 0:
                    if sign == '+':
                        stack.append(num)
                    elif sign == '-':
                        stack.append(-num)
                    elif sign == '*':
                        stack.append(stack.pop() * num)
                    elif sign == '/':
                        stack.append(int(stack.pop() / num))
                    sign = c
                    num = 0
                if c == ')': break
            return sum(stack)
        return helper(deque(list(s)))

有一件事一開始看會覺得怪：sign 可能被設成 '(' 或 ')' 這種根本不是運算符的值。

沒關係 —— 那種時候 num 一定是 0，四個 elif 全都不成立，整個結算等於什麼都沒做。這份程式碼能容忍「多結算幾次」，但不能容忍「少結算一次」，所以判斷條件寧可放寬也不要收緊。用排除法正好符合這個方向。

其餘細節（為什麼用 deque、為什麼除法要用 int(a / b) 而不是 //、為什麼 break 要放最後）跟 224 和 227 完全一樣。

補充

一份 helper 解三題。 上面這份程式碼原封不動丟給 227 和 224 也會過：

題目	會用到的部分	用不到的部分
227	乘除分支、sign 延遲結算	c == '(' 的遞迴
224	遞迴、sign 延遲結算	* / 兩個分支
772	全部	——

所以整個題組真正要記的只有一個骨架，而不是三個。227 那篇還是保留了不含遞迴的精簡版 —— 沒有括號的時候用索引掃就夠了，不必轉成 deque。

題組關係見 227 的補充。

複雜度

• 時間 $O(n)$ — 每個字元被 popleft 一次，遞迴不會重複走同一個字元
• 空間 $O(n)$ — deque 佔 $O(n)$，遞迴深度和 stack 最壞也是 $O(n)$

其中 $n$ 是字串長度。