實現一個基本的計算器來計算一個簡單的字符串表達式 s 的值。

題目鏈接：https://leetcode-cn.com/problems/basic-calculator/

示例 1：

輸入：s = "1 + 1"
輸出：2
示例 2：

輸入：s = " 2-1 + 2 "
輸出：3
示例 3：

輸入：s = "(1+(4+5+2)-3)+(6+8)"
輸出：23
?

提示：

1 <= s.length <= 3?* 105
s 由數字、'+'、'-'、'('、')'、和 ' ' 組成
s 表示一個有效的表達式

解題報告：

? 巧妙利用了棧。

由于字符串除了數字與括號外，只有加號和減號兩種運算符。因此，如果展開表達式中所有的括號，則得到的新表達式中，數字本身不會發生變化，只是每個數字前面的符號會發生變化。

所以用一個{+1, -1}的符號棧，棧頂元素就代表當前括號內所有符號的一個“基礎符號”，也就是最終該符號后面的數字，到底是+還是-，是要看“基礎符號”和該符號，來共同決定的。搞明白這個棧的作用，這題就簡單了，右括號就出棧，左括號就入棧，實時維護當前sign就行了。

AC代碼：

class Solution { public:int calculate(string s) {stack<int> sk;sk.push(1);int i = 0,sign = 1;long long ans = 0;while(i < s.length()) {if(s[i] == '(') sk.push(sign);else if(s[i] == ')') sk.pop();else if(s[i] == '+') sign = (sk.top() == 1 ? 1 : -1);else if(s[i] == '-') sign = (sk.top() == 1 ? -1 : 1);else if(s[i] >= '0' && s[i] <= '9') {long long tmp = 0;while(i < s.length() && s[i]>='0'&&s[i]<='9') {tmp = tmp * 10 + s[i] - '0';i++;} i--;ans += sign * tmp;printf("%lld\n",ans);}i++;}return ans;} };

?

總結

以上是生活随笔為你收集整理的【LeetCode - 224】基本计算器（栈）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。