实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
示例 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 表示一个有效的表达式
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/basic-calculator
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
借助栈的思维去处理该问题:
class Solution:
def calculate(self, s: str) -> int:
n = len(s)
stk = list()
res, sign, i = 0, 1, 0
stk.append(sign)
while i < n:
if s[i] == ' ':
i += 1
elif s[i] == '+':
sign = stk[-1]
i += 1
elif s[i] == '-':
sign = -stk[-1];
i += 1
elif s[i] == '(':
stk.append(sign)
i += 1
elif s[i] == ')':
stk.pop()
i += 1
else:
num = 0
while i < n and s[i].isdigit():
num = num * 10 + int(s[i])
i += 1
res += sign * num
return res
int calculate(char * s){
int len = strlen(s);
int *stk = (int *)malloc(sizeof(int) * len);
int top = 0, sign = 1;
int res = 0;
int i = 0;
memset(stk, 0, sizeof(int) * len);
stk[top++] = sign;
while (i < len) {
if (s[i] == ' ') {
i++;
}
else if (s[i] == '+') {
sign = stk[top - 1];
i++;
}
else if (s[i] == '-') {
sign = -stk[top - 1];
i++;
}
else if (s[i] == '(') {
stk[top++] = sign;
i++;
}
else if (s[i] == ')') {
top--;
i++;
}
else {
long num = 0;
while (i < len && s[i] >= '0' && s[i] <= '9') {
num = num * 10 + s[i] - '0';
i++;
}
res += sign * num;
}
}
free (stk);
return res;
}