LeetCode 224. Basic Calculator(Hard)#Stack
LeetCode 224 題的問題是實現一個基本計算器，可以處理加法、減法、括號和空格。
範例 1：
輸入： s = "1 + 1"
輸出： 2
範例 2：
輸入： s = " 2-1 + 2 "
輸出： 3
範例 3：
輸入： s = "(1+(4+5+2)-3)+(6+8)"
輸出： 23
這個問題可以通過使用棧(Stack)來處理。
棧是一種先進後出的數據結構，對於處理嵌套結構（比如括號）很有用。
可將遍歷輸入字元串並使用兩個棧：一個棧用於存儲操作數，另一個棧用於存儲操作符。
Step1.初始化變數和Stack。
Step2.遍歷字元串中的每個字元：
如果是數字字元，構建當前操作數。
如果是 '+' 或 '-'，更新當前操作符。
如果是 '('，將當前結果和操作符分別入棧，並重置結果和操作符。
如果是 ')'，計算括號內的結果，並從棧中取出之前存儲的結果和操作符。
Step3.計算最後一個操作數。
Step4.返回最終結果。
ans1.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | class Solution { public: int calculate(string s) { stack<int> nums; // 存儲操作數 stack<int> ops; // 存儲操作符 int num = 0; // 當前操作數 int result = 0; // 最終結果 int sign = 1; // 符號，默認為正 for (char c : s) { if (isdigit(c)) { num = num * 10 + (c - '0'); // 構建操作數 } else if (c == '+' || c == '-') { result += sign * num; // 計算結果 num = 0; // 重置當前操作數 sign = (c == '+') ? 1 : -1; // 更新操作符 } else if (c == '(') { nums.push(result); ops.push(sign); result = 0; sign = 1; } else if (c == ')') { result += sign * num; num = 0; result *= ops.top(); ops.pop(); result += nums.top(); nums.pop(); } } result += sign * num; // 處理最後一個操作數 return result; } }; |
Ref:
C++ isdigit()用法
LeetCode 224
留言
張貼留言