1. 題目
實作一個基本的電腦來計算一個簡單的字元串表達式的值。
字元串表達式可以包含左括号
(
，右括号
)
，加号
+
，減号
-
，非負整數和
空格
。
示例 1:
輸入: "1 + 1"
輸出: 2
示例 2:
輸入: " 2-1 + 2 "
輸出: 3
示例 3:
輸入: "(1+(4+5+2)-3)+(6+8)"
輸出: 23
說明：
你可以假設所給定的表達式都是有效的。
請不要使用内置的庫函數 eval。 複制
來源：力扣（LeetCode） 連結：https://leetcode-cn.com/problems/basic-calculator
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
2. 解題
class Solution { //C++
public:
int calculate(string s) {
stack<int> stk;
int sign = 1;
long num = 0, sum = 0;
for(int i = 0; i < s.size(); ++i)
{
if(s[i] =='(')
{ //遇見左括号，把括号外面的結果入棧，外面的符号入棧
stk.push(sum);
stk.push(sign);
sign = 1;//下次的符号初始值
sum = 0;
num = 0;
}
else if(s[i] =='+')
{
sum += sign*num;//和
sign = 1;//目前符号
num = 0;
}
else if(s[i] =='-')
{
sum += sign*num;
sign = -1;
num = 0;
}
else if(s[i] ==')')
{ //遇到右括号
sum += sign*num;//括号内的和加起來
sign = stk.top();//括号外的符号
stk.pop();//符号出棧
sum = sign*sum + stk.top();//和*符号+外面的和
stk.pop();//外面的和出棧
num = 0;
}
else if(isdigit(s[i]))
num = num*10+s[i]-'0';
}
return sum+sign*num;
}
}; 複制
12 ms 8.2 MB
class Solution:# py3
def calculate(self, s: str) -> int:
sum, sign, num = 0, 1, 0
stk = []
for c in s:
if c ==' ':
continue
if c =='+':
sum += sign*num
sign = 1
num = 0
elif c =='-':
sum += sign*num
sign = -1
num = 0
elif c =='(':
stk.append(sum)
stk.append(sign)
sum, num = 0, 0
sign = 1
elif c ==')':
sum += sign*num
sum = sum*stk.pop()+stk.pop()
num = 0
else:
num = num*10+int(c)
return sum+sign*num 複制
92 ms 13.6 MB