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