224. Basic Calculator

題目 / Problem

中文 給你一個字串 s，代表一個合法的數學運算式。請實作一個基本計算機來計算它的結果，並回傳這個結果。

注意：不能使用任何會把字串當成數學式來計算的內建函式（例如 eval()）。

運算式中只會出現：數字、+、-、(、) 和空白。其中 + 一定是「二元運算子」（不會出現像 +1 這種寫法），但 - 可以是「一元負號」（像 -1 或 -(2 + 3) 都是合法的）。輸入保證合法，且不會出現連續兩個運算子。

English Given a string s representing a valid mathematical expression, implement a basic calculator to evaluate it and return the result. You may not use eval() or any function that evaluates strings as math.

The expression contains only digits, +, -, (, ), and spaces. + is always a binary operator (no +1), but - may be a unary minus (-1 and -(2 + 3) are valid). The input is guaranteed valid with no two consecutive operators.

Constraints - 1 <= s.length <= 3 * 10^5 - s consists of digits, +, -, (, ), and ' '. - s represents a valid expression. - Every number and running calculation fits in a signed 32-bit integer.

Worked example

Input:  s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

Because (1 + (4+5+2) - 3) + (6+8) = (1 + 11 - 3) + 14 = 9 + 14 = 23.

名詞解釋 / Glossary

• 括號 / parentheses — 成對的 ( 和 )。括號內的運算要先算完，再把結果交給外層。 Parentheses group a sub-expression that must be evaluated first, then handed back to the surrounding expression.
• 堆疊 / stack — 一種「後進先出」(LIFO) 的資料結構，只能從頂端推入 (push) 或彈出 (pop)。我們用它來「記住」遇到 ( 之前外層累積的結果與符號，等 ) 出現時再取回。 A LIFO structure where you push/pop only at the top; we use it to remember the outer running total and sign before entering a (, and restore them at the ).
• 一元負號 / unary minus — 出現在數字或括號前面、表示「負」的 -，例如 -5 或 -(2+3)。它和「減法」共用同一個字元，需要靠上下文判斷。 A - that means "negative of" rather than subtraction; same character, distinguished by context.
• 符號 / sign (+1 or -1) — 我們用一個整數變數記住「下一個數字要加還是要減」，+1 代表加、-1 代表減。 An integer that records whether the next number should be added (+1) or subtracted (-1).
• 進位累積數字 / building a multi-digit number — 字串裡 123 是三個字元，要靠 num = num * 10 + digit 一位一位拼成整數 123。 Digits arrive one char at a time; num = num*10 + d assembles them into the full integer.
• 原地掃描 / single pass — 從左到右把字串看一遍就得到答案，不需要先轉成其他結構。 Reading the string left-to-right exactly once to produce the answer.

思路

中文：最直覺的「暴力法」是先把字串解析成一棵運算式樹，或先處理括號再算加減——但對 hard 題來說這既麻煩又容易出錯。關鍵觀察是：這題只有加減和括號，沒有乘除，所以不需要考慮運算子優先級，純粹是「由左到右一路加減」。唯一會打斷這個流程的就是括號：遇到 ( 時，我們要先把括號內整段算完，再把它當成一個數字併回外層。

怎麼用一次掃描就做到？我們維護三個東西：result（目前累積的總和）、sign（下一個數字的正負，+1 或 -1）、以及一個 stack。掃描時：碰到數字就用 num = num*10 + d 把完整數字拼出來，遇到非數字時就把 sign * num 加進 result。碰到 + 把 sign 設成 +1，碰到 - 設成 -1（注意 - 同時涵蓋「減法」和「一元負號」，因為兩者效果一樣：把後面那個數字變負再加進去）。

括號是精髓。遇到 ( 時，外層的 result 和它前面的 sign 還沒用完，但我們要先進去算括號裡的東西。於是我們把目前的 result 和 sign 推入堆疊保存，然後把 result 歸零、sign 重設為 +1，彷彿在一張新白紙上算括號內的子運算式。當遇到對應的 ) 時，括號內的結果已經算在 result 裡，我們從堆疊彈出剛才存的 sign（這是括號整體的正負）和舊的 result（外層累積），用 result = oldResult + poppedSign * result 把括號結果併回外層。因為堆疊是後進先出，巢狀括號會自動正確配對。整個過程只掃一遍，時間與字串長度成正比。

English: The brute-force instinct is to build an expression tree or resolve parentheses recursively, but that is heavy and bug-prone for a hard problem. The key insight: this expression has only +, -, and parentheses — no * or / — so there is no operator precedence to worry about. It is just a left-to-right running sum of signed numbers. The only thing that interrupts that flow is a parenthesis: at ( we must finish the inner sub-expression first, then fold its value back as a single number.

To do it in one pass, keep three things: result (running total), sign (+1/-1 for the next number), and a stack. While scanning: digits build up via num = num*10 + d; when a non-digit is hit, add sign * num into result. A + sets sign = +1; a - sets sign = -1 (the same code handles both subtraction and unary minus, because both simply mean "make the following value negative before adding").

Parentheses are the heart of it. At (, the outer result and the sign sitting in front of the ( are not finished, but we must compute the inside first. So we push the current result and sign onto the stack, reset result = 0 and sign = +1, and evaluate the inner sub-expression on a fresh slate. At the matching ), the inner total is in result; we pop the saved sign (the sign of the whole parenthesized group) and the saved outer result, and fold back with result = outerResult + poppedSign * result. Because a stack is LIFO, nested parentheses pair up automatically. One pass, time linear in the string length.

逐步走查 / Walkthrough

我們追蹤 s = "(1+(4+5+2)-3)+(6+8)"，但為了讓表格不過長且清楚，先用第三個範例的較短前段思路示範一遍完整機制。逐字元追蹤如下（num 為正在拼的數字，sign 為下一數字符號，res 為當前層累積，stk 為堆疊；空白略過）:

Tracing s = "(1+(4+5+2)-3)+(6+8)". Columns: c = current char, then state after processing it.

等等——步驟 10 要小心順序。先把尚未加入的 num 結算，再做 pop。修正後：

Careful at ): first settle the pending num, then pop. Corrected continuation:

最終 res = 23，正確。Final res = 23. ✅

Solution — C

// 演算法 / Algorithm:
// 由左到右掃描一次。用 sign(+1/-1) 記下一個數字正負，res 累積當前層總和。
// 遇到 '(' 把外層 res 與 sign 推入堆疊並重置；遇到 ')' 先結算待加數字，
// 再彈出折回外層。只有加減與括號，無需運算子優先級。
// Single left-to-right pass; stack saves the outer (res, sign) at '(' and
// restores/folds them at ')'. No precedence needed (only + - and parens).

#include <stdlib.h>   // 提供 malloc / free（手動配置堆疊記憶體）/ for malloc & free

int calculate(char* s) {
    int n = 0;                      // 算字串長度 / measure length of s
    while (s[n] != '') n++;       // 逐字元直到結尾 '' / scan until null terminator

    // 堆疊：最壞情況每個字元都是 '('，每次 push 兩個 int（res 與 sign）。
    // The stack: worst case every char is '(', each push stores 2 ints (res, sign).
    int* stack = (int*)malloc(sizeof(int) * (size_t)(2 * n + 2));
    int top = 0;                    // 堆疊頂端索引，指向下一個空位 / next free slot

    int res = 0;                    // 當前層累積結果 / running total of current level
    int sign = 1;                   // 下一個數字的正負，+1 或 -1 / sign of next number
    int num = 0;                    // 正在拼接的多位數字 / the multi-digit number being built

    for (int i = 0; i < n; i++) {   // 逐字元處理 / process each character
        char c = s[i];

        if (c >= '0' && c <= '9') {            // 是數字字元嗎 / is it a digit?
            num = num * 10 + (c - '0');        // 一位一位拼成整數，'c-0' 把字元轉成數值 / build number; (c-'0') char→int
        } else if (c == '+') {                 // 加號 / plus
            res += sign * num;                 // 先把前一個數字結算進 res / settle previous number
            num = 0;                           // 清空以拼下一個數字 / reset for next number
            sign = 1;                          // 下一個數字為正 / next number is positive
        } else if (c == '-') {                 // 減號或一元負號 / minus (binary or unary)
            res += sign * num;                 // 結算前一個數字 / settle previous number
            num = 0;                           // 重置 / reset
            sign = -1;                         // 下一個數字為負 / next number is negative
        } else if (c == '(') {                 // 左括號：進入新子運算式 / open: enter sub-expression
            stack[top++] = res;                // 保存外層累積 / save outer running total
            stack[top++] = sign;               // 保存括號整體的正負 / save sign in front of '('
            res = 0;                           // 在「白紙」上重新算 / fresh slate for inner
            sign = 1;                          // 內層第一個數字預設為正 / inner starts positive
        } else if (c == ')') {                 // 右括號：結束子運算式 / close: finish sub-expression
            res += sign * num;                 // 先結算括號內最後一個數字 / settle last inner number
            num = 0;                           // 重置 / reset
            int savedSign = stack[--top];      // 彈出括號整體正負（後進先出）/ pop the group's sign (LIFO)
            int savedRes  = stack[--top];      // 彈出外層累積 / pop outer total
            res = savedRes + savedSign * res;  // 把括號結果折回外層 / fold inner result back
        }
        // 空白字元落到這裡，什麼都不做、直接略過 / spaces fall through and are skipped
    }

    res += sign * num;   // 迴圈結束後結算最後一個未加入的數字 / settle the final pending number
    free(stack);         // 釋放手動配置的記憶體，避免洩漏 / free heap memory to avoid leak
    return res;          // 回傳答案 / return result
}

Solution — C++

// 演算法 / Algorithm:
// 與 C 版相同：單次掃描，sign 記正負，res 累積當前層；'(' 時把 (res, sign)
// 推入堆疊並重置，')' 時結算並折回外層。只有加減與括號，無優先級問題。
// Same as the C version: one pass; push (res, sign) at '(', pop & fold at ')'.

#include <string>   // std::string
#include <stack>    // std::stack（封裝好的後進先出容器）/ ready-made LIFO container
#include <utility>  // std::pair（一次存兩個值）/ to store two values together

class Solution {
public:
    int calculate(std::string s) {
        // stack 存放 pair<外層res, 括號的sign>，遇到 '(' push、')' pop。
        // Stack of pair<outer res, group sign>; pushed at '(', popped at ')'.
        std::stack<std::pair<int,int>> st;

        long long res = 0;   // 當前層累積；用 long long 多一層保險避免中途溢位 / running total (extra-wide for safety)
        int sign = 1;        // 下一個數字的正負 / sign of next number
        long long num = 0;   // 正在拼接的數字 / number being built

        for (char c : s) {            // range-for：依序取出每個字元 / range-based for over each char
            if (std::isdigit(static_cast<unsigned char>(c))) {  // 是數字嗎 / is digit? (cast 避免負值 UB / safe cast)
                num = num * 10 + (c - '0');   // 一位一位拼成整數 / build multi-digit number
            } else if (c == '+') {            // 加號 / plus
                res += sign * num;            // 結算前一數字 / settle previous number
                num = 0;                      // 重置 / reset
                sign = 1;                     // 下一個為正 / next positive
            } else if (c == '-') {            // 減號或一元負號 / minus (binary or unary)
                res += sign * num;            // 結算 / settle
                num = 0;                      // 重置 / reset
                sign = -1;                    // 下一個為負 / next negative
            } else if (c == '(') {            // 左括號 / open paren
                st.emplace(static_cast<int>(res), sign); // 把 (res, sign) 直接就地建構入堆疊 / push pair in place
                res = 0;                      // 內層重新累積 / fresh slate
                sign = 1;                     // 內層預設正 / inner starts positive
            } else if (c == ')') {            // 右括號 / close paren
                res += sign * num;            // 結算括號內最後一個數字 / settle last inner number
                num = 0;                      // 重置 / reset
                auto [outerRes, groupSign] = st.top();  // 結構化綁定一次取出兩個值 / structured binding
                st.pop();                     // 彈出 / pop the saved pair
                res = outerRes + groupSign * res;       // 折回外層 / fold inner back into outer
            }
            // 空白被以上條件略過 / spaces are ignored by all branches
        }

        res += sign * num;                    // 結算最後一個未加入的數字 / settle final pending number
        return static_cast<int>(res);         // 題目保證結果落在 32-bit / answer fits in int
    }
};

複雜度 / Complexity

• Time: O(n) — n 是字串長度。每個字元只被看一次，每次做的都是常數時間操作（比較、加法、push/pop）。括號的 push/pop 攤平後仍是常數成本。 Each character is visited exactly once; every per-char operation (compare, add, push/pop) is O(1), so total is linear in the string length.
• Space: O(n) — 最壞情況是大量巢狀括號（如 ((((...))))），堆疊深度與括號層數成正比，可達 O(n)。若沒有括號則只用常數額外空間。 Worst case is deeply nested parentheses; stack depth grows with nesting and can reach O(n). With no parentheses it is O(1) extra.

Pitfalls & Edge Cases

• - 既是減法也是一元負號 / - is both subtraction and unary minus — 因為我們把每個數字都當成「帶符號後加進 res」，5-3 和 -3 走同一段邏輯都正確，不需特別區分。 Treating every number as "signed, then added" makes both cases fall out of the same code; no special-casing needed.
• 迴圈結束後別忘了最後一個數字 / don't forget the final number — 數字只有在遇到下一個運算子或 ) 時才會被加入 res。若字串以數字結尾（如 "1+1"），必須在迴圈外再做一次 res += sign * num，否則最後一個數字會遺失。 The last number is only settled when an operator/) follows it; a trailing number needs the final settle after the loop.
• ) 的結算順序 / order of operations at ) — 一定要先 res += sign * num（結算括號內最後一個數字）再 pop。順序反了會把舊的外層值誤用。 Settle the pending inner number before popping; reversing the order corrupts the fold.
• 空白要略過而非報錯 / skip spaces, don't choke on them — 輸入含大量空白（如 " 2-1 + 2 "）。我們的 if-else 沒有任何分支匹配空白，於是它自然被忽略。 Spaces match no branch and are silently skipped.
• 多位數字 / multi-digit numbers — num = num*10 + d 是把字元逐位組成整數的標準寫法；忘了它會把 123 誤當成數字 3。 Forgetting the *10 accumulation would misread 123 as just 3.
• 溢位保險 / overflow safety — 題目保證結果在 32-bit 內，但 C++ 版用 long long 作中途累積多一層保險；C 版用 int 也能通過，因為「每一步」都保證合法。 The problem guarantees 32-bit results; the C++ version uses long long mid-computation as a safety margin, while the C int version is fine because every running value is guaranteed valid.