1 题目
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
提示：
1 <= s.length <= 3 * 105
s 由数字、‘+’、‘-’、‘(’、‘)’、和 ’ ’ 组成
s 表示一个有效的表达式
‘+’ 不能用作一元运算(例如， “+1” 和 “+(2 + 3)” 无效)
‘-’ 可以用作一元运算(即 “-1” 和 “-(2 + 3)” 是有效的)
输入中不存在两个连续的操作符
每个数字和运行的计算将适合于一个有符号的 32位 整数
2 解析
代码里面:
res 表示左边表达式除去栈内保存元素的计算结果；
sign 表示运算符，在此代码中仅表示正负；
num 表示当前遇到的数字，会更新到 res 中；
用栈保存遇到左括号时前面计算好了的结果和运算符。
操作的步骤是：
- 如果当前是数字，那么更新计算当前数字；
- 如果当前是操作符+或者-，那么需要更新计算当前计算的结果 res，并把+ 当前数字 num 设为 0，sign 设为正负，重新开始；
- 如果当前是 ( ，那么说明遇到了右边的表达式，而后面的小括号里的内容需要优先计算，所以要把 res，sign 进栈，更新 res 和 sign 为新的开始；
- 如果当前是 ) ，那么说明右边的表达式结束，即当前括号里的内容已经计算完毕，所以要把之前的结果出栈，然后计算整个式子的结果；
- 最后，当所有数字结束的时候，需要把最后的一个 num 也更新到 res 中。
3 Python实现
class Solution: def calculate(self, s: str) -> int: num,res,sign = 0,0,1 stack = [] for c in s: if c.isdigit(): # 两个个位数同时出现时，就是一个多位数的值 num = num*10+int(c) elif c=='+'or c=='-': res +=sign*num num = 0 sign =1 if c=='+' else -1 elif c=='(': # 数值进栈 stack.append(res) # 符号进栈 stack.append(sign) res = 0 sign = 1 elif c==')': res +=sign*num num = 0 # 符号出栈 sign_tmp = stack.pop() # 数值出栈 res_tmp = stack.pop() res *=sign_tmp res += res_tmp # 最后一步，别忘了 res += sign*num return res
