224. Basic Calculator

# Hard

Key idea: stack, which can skip space

Take 5+ (1+5 - (4+ 5- 2) - 3+2) - 7 as example:

= 5+(6-(4+5-2)-3+2)) - 7

= 5+(6-7-3+2)-7

= 5-2-7

= -4

思路：遇到“（”，将前面的计算结果和括号前的符号压入栈；遇到“）”说明这一个最小单元的括号计算完毕，则与这个（）前面的结果相加；遇到“+”则说明前面一个数字很完整了，加上，但下一个数字的符号是“+”；遇到“-”则说明前面一个数字很完整了，加上，但下一个数字的符号是“-”。

class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        sign = 1   # 1 means positve, -1 means negative
        res = 0   
        num = 0  # the complete number
        
        for ch in s:
            if ch.isdigit():
                num = num*10 + int(ch)
            elif ch == '+':
                res += sign * num
                sign = 1
                num = 0
            elif ch == '-':
                res += sign * num
                sign = -1
                num = 0
            elif ch == '(':
                stack.append(res)
                stack.append(sign)
                sign = 1
                res = 0
            elif ch == ')':
                res += sign*num
                res = res*stack.pop()
                res += stack.pop()
                num = 0
                
        return res + sign * num