題目描述:給定一個合法的數學運算式字串 s,其中包含非負整數、+、-、( 和 ),以及可能出現的空格。實作一個基本計算機,不使用任何內建的 eval 函式,回傳計算結果。注意本題只有加減法,沒有乘除法,因此不需要考慮運算優先級。
解題思路:使用 stack 來處理括號帶來的「符號上下文」問題。維護三個關鍵變數:result(當前計算結果)、num(當前正在讀取的數字)、sign(當前運算符號,+1 或 -1)。逐字元掃描:若為數字,累積到 num;若為 + 或 -,先將 sign * num 加入 result,然後更新 sign,重置 num;若為 (,將當前的 result 和 sign 推入堆疊,然後重置 result 和 sign(開始計算括號內的子表達式);若為 ),先將最後一個數字加入 result,然後從堆疊彈出 sign 和先前的 result,組合為 result = prev_result + sign * result。最後將剩餘的 sign * num 加入 result 並回傳。
時間複雜度:O(n) — 只需對字串進行一次線性掃描,每個字元的處理(含堆疊操作)均為 O(1),因此整體時間與字串長度成正比。
空間複雜度:O(n) — 堆疊的深度與括號嵌套層數成正比。最壞情況下(如 ((((...))))) 這類深度嵌套),堆疊大小為 O(n)。
1. Initialize result = 0, num = 0, sign = 1, and an empty stack.
2. For each character c in s:
a. If c is a digit: num = num * 10 + digit_value(c).
b. If c == '+': result += sign * num; num = 0; sign = +1.
c. If c == '-': result += sign * num; num = 0; sign = -1.
d. If c == '(': push result and sign onto stack; reset result = 0, sign = 1.
e. If c == ')': result += sign * num; num = 0;
savedSign = stack.pop(); savedResult = stack.pop();
result = savedResult + savedSign * result.
f. If c == ' ': skip.
3. After the loop: result += sign * num.
4. Return result.方法一:遞迴下降解析(Recursive Descent Parsing)
用遞迴函式處理每一對括號,每次遇到 ( 就遞迴調用,遇到 ) 就返回。自然地對應括號的嵌套結構,程式碼邏輯清晰。時間複雜度 O(n),空間複雜度 O(n)(遞迴棧的深度等於括號嵌套深度)。缺點是深度嵌套時可能導致棧溢出(Stack Overflow)。
方法二:轉換為逆波蘭表示式(Reverse Polish Notation, RPN) 先用 Shunting-yard 算法將中綴表示式轉換為後綴表示式(RPN),再用另一個堆疊計算 RPN 的值。這是通用的表達式求值框架,可以輕鬆擴展支援乘除法和更多運算符。時間複雜度 O(n),空間複雜度 O(n)。相對於本題的單次掃描解法,此方法需要兩次遍歷,實作較繁瑣,但擴展性極佳。
"(-3+2)"),現有的解法需要做哪些修改才能正確處理一元負號(unary minus)?