📘 題目敘述
給你一個字串 s，表示一個合法的算式，請實作一個基本計算機來計算它的值，並回傳結果。
注意：你不能使用任何內建可以直接把字串當成數學表達式計算的函式，例如 eval()。
條件限制
1 <= s.length <= 3 * 10^5s由數字、'+'、'-'、'('、')'和空白' '組成s表示一個合法的表達式'+'不會作為 unary operation 使用，也就是"+1"和"+(2 + 3)"都是非法的'-'可以作為 unary operation 使用，也就是"-1"和"-(2 + 3)"都是合法的- 輸入中不會出現兩個連續運算子
- 每個數字與中途計算結果都保證能放進 signed 32-bit integer
🧠 解題思路
這題我的做法是用遞迴去處理括號。
因為括號的本質就是：
- 遇到
'('時，開始計算一個新的子表達式 - 遇到
')'時，這一層子表達式結束，把結果回傳給上一層
所以我寫了一個 calc(string& s)，專門負責：
從目前
pos這個位置開始，算到這一層表達式結束為止，並回傳這一段的值。
這份程式裡，我沒有另外真的切 substring，而是用一個全域索引 pos 一路往後掃。
這樣每個字元只會被讀一次，效率會比較好。
在一層表達式裡，我維護三個主要東西：
sum：目前已經確定累加進去的總和now：目前正在讀的那個數字，或是剛算完的一段括號結果sign：這個now之後要乘上的正負號，只有1或-1
例如在看到：
- 數字時，就一直把它拼進
now - 看到
'+'或'-'時，表示前一個now已經結束了，就把now * sign加進sum - 看到
'('時，就遞迴進去算括號裡那段，把結果放進now - 看到
')'時，表示這一層結束了，就把最後這個now * sign加進sum後回傳
這樣就可以自然處理：
- 一般加減
- 多位數
- 巢狀括號
- unary minus
也就是說，這題的核心就是：
用
pos一路掃字串，配合遞迴把每一層括號當成一個新的子計算區間，並用sum + sign * now的方式完成每一層的加減計算。
所有變數
pos：目前掃到字串s的哪個位置sum：目前這一層表達式已經累加完成的總和now：目前正在組的數字，或剛從括號遞迴回來的值sign：目前now前面的正負號，1代表正，-1代表負c：目前pos指到的字元
🪜 主要流程步驟
1. 在 calculate 裡先初始化整體掃描位置
pos = 0;
n = s.size();
return calc(s);
這裡的意思是：
- 一開始從字串第
0個位置開始掃 n記住整個字串長度- 然後直接呼叫
calc(s)去計算整段表達式
因為 calc 會透過全域的 pos 一路往後走，所以不需要切字串，也不需要傳左右邊界。
2. 在每一層 calc 裡，先準備 sum、now、sign
long long sum = 0;
long long now = 0;
int sign = 1;
這三個變數是這一層表達式的核心。
sum- 存目前已經確定累加好的部分
now- 存目前正在讀的數字
- 或是剛從括號遞迴算回來的值
sign- 記這個
now應該加進去還是減進去
- 記這個
例如如果目前讀到：
12- 那
now = 12
- 那
- 如果它前面是
-- 那之後要加進
sum時就是sum += -12
- 那之後要加進
3. 一路掃字串，直到這一層結束
while (pos < n) {
char c = s[pos];
這裡每次都看目前位置的字元 c 是什麼，再決定怎麼處理。
這份寫法的特點是：
- 不額外開 stack
- 不額外切 substring
- 而是用同一個
pos直接往後掃
所以每個字元只會被讀一次。
4. 如果是空白，就直接跳過
題目字串裡可能有空白，但空白不影響運算。
所以這裡直接略過，繼續看下一個字元就好。
5. 如果是數字，就把它接到 now 後面
if (c >= '0' && c <= '9') {
now = now * 10 + (c - '0');
}
這一步是在處理多位數。
例如原本 now = 12，下一個字元是 '3'，那就變成：
now = 12 * 10 + 3 = 123
所以這段可以正確把：
123456
這種多位數一路拼出來。
6. 如果遇到 + 或 -，代表前一個 now 已經結束，先加進 sum
當看到 + 或 - 時，代表前面的數字或括號結果已經完整了，所以要先把它結算進 sum。
例如：
- 如果前面是
12，而且sign = 1- 就做
sum += 12
- 就做
- 如果前面是
7，而且sign = -1- 就做
sum += -7
- 就做
之後：
now = 0- 準備讀下一個數字或括號值
sign = 1或-1- 表示下一段的符號
7. 如果遇到 (，就遞迴去算括號裡那段
else if (c == '(') {
pos++;
now = calc(s);
}
這是整題最核心的地方。
當看到 '(' 時，表示：
- 一個新的子表達式開始了
所以這裡先把 pos++，跳到括號裡第一個字元，然後呼叫：
now = calc(s)
也就是把括號裡整段算完，並把結果當成一個普通數字放進 now。
例如：
1 + (4 + 5)- 算到
'('時，就先把(4 + 5)算成9 - 然後外層就變成在處理
1 + 9
8. 如果遇到 )，表示這一層表達式結束，回傳結果
else if (c == ')') {
sum += now * sign;
return sum;
}
看到 ')' 的意思是：
- 目前這一層括號到這裡結束了
所以在回傳前，要先把最後一個還沒結算的 now * sign 加進 sum，然後把這一層的總結果回傳。
例如：
- 如果括號裡是
4 + 5 - 2 - 走到
')'時，這一層就把結果7回傳給上一層
上一層會把它當成普通數字繼續運算。
9. 每次迴圈最後把 pos 往後移
pos++;
這裡表示目前這個字元已經處理完了，所以往下一格走。
要注意的是：
- 如果剛剛是
'('- 進入遞迴前有先
pos++
- 進入遞迴前有先
- 如果剛剛是
')'- 會直接
return
- 會直接
所以整個位置控制是靠這份程式自己配合遞迴完成的。
10. 如果一路掃到字串結尾，也要把最後一個 now 結算進去
sum += sign * now;
return sum;
如果沒有遇到 ')'，代表這一層就是最外層表達式，最後會自然走到字串結尾。
這時最後一個數字或括號結果還沒有被加進 sum，所以要補這一步，再回傳最終答案。
11. 為什麼這樣可以處理 unary minus
題目允許像：
-1-(2 + 3)
這份寫法也能處理。
例如 -1：
- 一開始
sum = 0,now = 0,sign = 1 - 讀到
'-'- 先做
sum += 0 * 1 - 再把
sign = -1
- 先做
- 接著讀到
1now = 1
- 最後結算時變成
sum + (-1) * 1 = -1
-(2+3) 也一樣，括號遞迴回來後那個值會放進 now，最後乘上 -1。
所以這種寫法自然就把 unary minus 吃掉了。
⏱️ 複雜度
設 n = s.length。
- 時間複雜度：
O(n)
每個字元都只會被掃描一次。 - 空間複雜度：
O(n)
最壞情況下如果括號巢狀很深，遞迴呼叫堆疊會到線性深度。
💻 程式碼實作
class Solution {
public:
int pos;
int n;
long long calc(string& s) {
long long sum = 0;
long long now = 0;
int sign = 1;
while (pos < n) {
char c = s[pos];
if (c == ' ') {
pos++;
continue;
}
if (c >= '0' && c <= '9') {
now = now * 10 + (c - '0');
} else if (c == '+') {
sum += now * sign;
now = 0;
sign = 1;
} else if (c == '-') {
sum += now * sign;
now = 0;
sign = -1;
} else if (c == '(') { //新計算開始
pos++;
now = calc(s);
} else if (c == ')') { //中途計算結束回傳
sum += now * sign;
return sum;
}
pos++;
}
sum += sign * now;
return sum;
}
int calculate(string s) {
pos = 0;
n = s.size();
return calc(s);
}
};
🔗 題目連結
https://leetcode.com/problems/basic-calculator/