224. Basic Calculator

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

只有 +、- 和括號的計算機。- 可以是減號，也可以是一元負號（"-2+1"、"-(3+4)" 都是合法輸入）。

先做 227. Basic Calculator II 和 394. Decode String

思路

骨架完全沿用 227：用 sign 記住欠著沒算的運算符，延遲一拍結算，最後 sum(stack)。這題只多一件事 —— 括號。

括號就是一個子問題

括號裡面算完之後，對外就只是一個數字。 1+(2+3) 跟 1+5 對外層來說完全一樣。

所以遇到 ( 就遞迴進去算，把回傳值當成一個運算元塞回 num，外層繼續照原本的流程走。遞迴幫我們保管的是進括號前的 stack / sign / num —— 它們被壓在呼叫堆疊上，出括號時自動還原。

為什麼要用 deque

遞迴的每一層都在消耗同一份字串。如果用索引，就得把游標的位置回傳出來（或用 nonlocal）；改成 deque 從左邊 popleft()，所有層看到的都是同一份「還沒處理的剩餘字串」，位置自然是共用的。

代價是要先把字串轉成 deque，多花 $O (n)$ 空間。

一元負號是免費的

這段程式碼沒有為負號寫任何特別處理，但 "-2+1" 會自己算對：

c = '-'   → 用 sign='+' 結算 num=0，推入 0    stack = [0]
            sign 換成 '-'
c = '2'   → num = 2
c = '+'   → 用 sign='-' 結算，推入 -2         stack = [0, -2]
c = '1'   → num = 1，字串結束，推入 1          stack = [0, -2, 1]
                                              sum = -1  ✅

關鍵是 sign 從 '+'、num 從 0 開始 —— 開頭的 - 會先結算出一個多餘的 0 推進 stack，而 0 對加總沒有任何影響。同樣的道理，"-(3+4)" 也直接就對了。

那個判斷式為什麼變長了

227 用的是 s[i] in "+-*/"，這題改成：

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

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

它涵蓋的是所有不是數字也不是空白的字元 —— +、-、(、) 全部都算「該結算了」。其中 ) 必須被涵蓋進來，否則括號內最後一個數字會在 break 之前被丟掉。

這個「排除法」的寫法比列舉 c in '+-*/' 更安全 —— 列舉要記得把 ) 放進去，漏一個就錯。我在 772 一度想簡化成列舉，結果就漏掉了 )，那篇留了完整的 bug 分析。

解題方向

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)))

* 和 / 那兩個分支在 224 用不到（題目沒有乘除），留著是有理由的 —— 這份 helper 一字不改就能解掉整個題組的三題，224 只是用不到乘除、227 只是用不到遞迴。詳見 772 的補充。

if c == ')': break 放在最後，順序不能調 —— 必須先讓上面的結算把括號內最後一個數字推進 stack，才能離開這一層。

補充

也可以寫成迭代版：進括號時把當前的 stack 和 sign 存進一個外層的 stack，出括號時取回來 —— 就是 394 迭代解法在做的事。遞迴版和迭代版的差別只在「狀態存在呼叫堆疊上，還是存在自己開的 stack 上」。我這題寫的是遞迴版，394 那篇兩種都有。

題組關係見 227 的補充。

複雜度

時間 $O (n)$ — 每個字元被 popleft 一次，遞迴不會重複走同一個字元
空間 $O (n)$ — deque 佔 $O (n)$ ；遞迴深度和 stack 的大小最壞也都是 $O (n)$ （例如 "((((1))))" 或全是加減的長式子）

其中 $n$ 是字串長度。