实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
输入：s = "1 + 1"
输出：2
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23
提示：
1 <= s.length <= 3 * 105
s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
s 表示一个有效的表达式
表达式求值这一类的题比较自然地会想到利用栈来求解。这里的难点是如何解决括号。基本思想如下：
维护一个栈，遍历字符串，
- 如果当前字符是空格，忽略
- 如果当前字符是
'+'，'-'或者'('，入栈 - 如果当前字符是数字，判断栈顶元素。如果栈顶元素是
'('，则入栈。如果栈顶元素是'+'，'-'，则将运算符出栈。如果此时栈顶元素是数字，则将其出栈，和当前数字做相应运算后将结果入栈。如果此时栈顶元素不是数字（比如说负数'-5'）。我们方便起见可以将左运算数设置为0，和当前数字运算后结果入栈。 - 如果当前字符是
')'，则栈顶元素必是数字，我们只需要出栈，然后忽略该数字前的'('。此时需要判断，如果栈顶是运算符，则需要做类似于3的操作。否则只需要将数字入栈。 - 循环结束后，栈里的剩余数字就是结果
WeChat Image_20210310222844.jpg
复杂度分析较为简单，时间空间都具有O(n)的复杂度。
class Solution:
'''
224. Basic Calculator
Stack
'''
def calculate(self, s: str) -> int:
evaluate_stack = list()
idx = 0
while idx < len(s):
if s[idx] == ' ':
# ignore all the space
idx += 1
continue
if s[idx] == '+' or s[idx] == '-' or s[idx] == '(':
# for parenthesis and operators,
# just push into stack
evaluate_stack.append(s[idx])
idx += 1
continue
if s[idx] >= '0' and s[idx] <= '9':
# get the number in case it has
# more than 1 digits
num_str = ''
while idx < len(s) and s[idx] >= '0' and s[idx] <= '9':
num_str += s[idx]
idx += 1
num = int(num_str)
if len(evaluate_stack) == 0 or evaluate_stack[-1] == '(':
# if stack empty or the top
# element is parenthesis, just
# push it into the stack
evaluate_stack.append(num)
else:
# otherwise, the top element in
# the stack must be an operator,
# then we get the operator and
# the operand, evaluate it and
# push the result back to the
# stack
operator = evaluate_stack.pop()
# this is to deal with negative number
left_operand = evaluate_stack.pop() if len(evaluate_stack) > 0 else 0
evaluate_stack.append((left_operand + num) if operator == '+' else (left_operand - num))
continue
if s[idx] == ')':
# when we see right parenthesis, the top
# element in the stack must be a number.
# we just remove the left parenthesis
# before that, before pushing the number
# back in, we need to check if the top
# element is now operator, to handle the
# case like '··+(1+2)'
num = evaluate_stack.pop()
evaluate_stack.pop()
if len(evaluate_stack) > 0 and evaluate_stack[-1] in ('+', '-'):
operator = evaluate_stack.pop()
left_operand = evaluate_stack.pop() if len(evaluate_stack) > 0 else 0
num = (left_operand + num) if operator == '+' else (left_operand - num)
evaluate_stack.append(num)
idx += 1
# with the assumption that the input string is
# an valid expression, the only number left in
# the stack should just be the result
return evaluate_stack[-1]
