链接： 基本计算器

字符串计算器，一种方法是将字符串转换为逆波兰式（其实是计算树的后续遍历序列），然后直接遍历计算。另一种方法是使用两个栈，分别存储操作数和操作符。

1. 遇到(、+、-直接压入操作符栈
2. 遇到数字，通过遍历，识别出数字，压入操作数栈
3. 遇到)，弹出操作符、操作数，进行计算，直到操作符栈为空或者操作符栈顶是“(”（这种情况需要把栈顶的“(”出栈）。

减号、负号的判断，如果-是第一个字符，或者-的前一个字符是)，则这个-是负号，否则就是减号。

“+”、“-”在操作符入栈前，先把现有栈内能计算的都算了。

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)