链接： 基本计算器
字符串计算器，一种方法是将字符串转换为逆波兰式（其实是计算树的后续遍历序列），然后直接遍历计算。另一种方法是使用两个栈，分别存储操作数和操作符。
- 遇到(、+、-直接压入操作符栈
- 遇到数字，通过遍历，识别出数字，压入操作数栈
- 遇到)，弹出操作符、操作数，进行计算，直到操作符栈为空或者操作符栈顶是“(”（这种情况需要把栈顶的“(”出栈）。
减号、负号的判断，如果-是第一个字符，或者-的前一个字符是)，则这个-是负号，否则就是减号。
“+”、“-”在操作符入栈前，先把现有栈内能计算的都算了。
class Solution:
def calculate(self, s: str) -> int:
s = s.replace(" ", "")
ops = []
nums = []
index = 0
while index < len(s):
c = s[index]
if c == ")": #遇到)则开始计算，直到操作符栈里遇到(，并将(出栈
while ops:
if ops[-1] != '(':
op = ops.pop()
a = nums.pop()
b = nums.pop()
if op == '+':
nums.append(a+b)
else:
nums.append(b-a)
else:
ops.pop()
break
elif c == "(":
ops.append("(")
elif c == '+': #将一个普通运算符入操作栈之前，先把能计算的的都算了
self.calc(nums, ops)
ops.append("+")
elif c == "-":
if index <= 0 or s[index-1] == "(": #这个-是负号，通过添加一个操作数0将负号转换成减号
ops.append("-")
nums.append(0)
else: #将一个普通运算符入操作栈之前，先把能计算的的都算了
self.calc(nums, ops)
ops.append("-")
else:
u = 0
j = index
while j < len(s) and self.is_num(s[j]):
u *= 10
u += ord(s[j]) - ord('0')
j += 1
nums.append(u)
index = j - 1
# print("index:{}, char:{}, ops:{}, nums:{}".format(index, s[index], ops, nums))
index += 1
# 将未计算的操作符和操作数进行计算，得到最终结果
self.calc(nums, ops)
return nums[-1]
def is_num(self, c):
if ord('0') <= ord(c) <= ord('9'):
return True
def calc(self, nums, ops):
while len(nums) >= 2 and len(ops) >= 1 and ops[-1] in ("+", "-"):
op = ops.pop()
a = nums.pop()
b = nums.pop()
if op == '+':
nums.append(a+b)
else:
nums.append(b-a)
