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

# 772. Basic Calculator III

[772\. Basic Calculator III](https://leetcode.com/problems/basic-calculator-iii/)

`+ - * /` 加上括號 —— [227](/interview/coding/227-basic-calculator-ii) 和 [224](/interview/coding/224-basic-calculator) 的聯集。

## 思路

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

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

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

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

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

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

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

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

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

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

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

### 那個 bug：`)` 也是結算點

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

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

```python
"(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)`：

```text
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」的遞迴，離開之前都要先問一句「手上還有沒有沒結算完的東西？」

## 解題方向

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

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

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

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

## 補充

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

| 題目 | 會用到的部分 | 用不到的部分 |
|---|---|---|
| [227](/interview/coding/227-basic-calculator-ii) | 乘除分支、`sign` 延遲結算 | `c == '('` 的遞迴 |
| [224](/interview/coding/224-basic-calculator) | 遞迴、`sign` 延遲結算 | `*` `/` 兩個分支 |
| 772 | 全部 | —— |

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

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

## 複雜度

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

其中 $n$ 是字串長度。