---
title: "224. Basic Calculator"
url: "https://laigary.com/interview/coding/224-basic-calculator"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-27"
tags: ["String", "Stack", "Recursion", "Classic"]
---

# 224. Basic Calculator

[224. Basic Calculator](https://leetcode.com/problems/basic-calculator/)

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

> 先做 [227. Basic Calculator II](/interview/coding/227-basic-calculator-ii) 和 [394. Decode String](/interview/coding/394-decode-string)

## 思路

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

### 括號就是一個子問題

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

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

### 為什麼要用 deque

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

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

### 一元負號是免費的

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

```text
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 "+-*/"`，這題改成：

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

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

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

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

## 解題方向

```python
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](/interview/coding/227-basic-calculator-ii) 只是用不到遞迴。詳見 [772 的補充](/interview/coding/772-basic-calculator-iii)。

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

## 補充

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

**題組關係**見 [227 的補充](/interview/coding/227-basic-calculator-ii)。

## 複雜度

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

其中 $n$ 是字串長度。