224. Basic Calculator.py

class Solution:
    """
    What's disibution of input string s?
    沒有乘號, 只有加號和減號!
    
    當只有加號和減號,沒有括號和乘號!
    1-1
      i
      num=1
      sign=-1
    res=1
    (1-1)+1
        i
    res=0
    sign=1 [(0,1)]
    遇到+/-號, 我們就可以計算當前result of the evaluation. 計算完, num要歸零因為之後要重新計算
    遇到(, 入棧當前res和sign, 然後把他們歸零
    遇到), 岀棧之前prev_res和prev_sign, 同時計算括號內的res
    不管入棧或是出棧，num和sign都要回歸到起始點!!
    """
    def calculate(self, s: str) -> int:
        n = len(s)
        i = 0
        num = 0
        #我們需要sign, 用來計算res判別現在是+/-號
        sign = 1
        res = 0
        stack = []
        while i < n:
            ch = s[i]
            if ch == " ":
                i+=1
                continue
            if ch.isdigit():
                num*=10
                num += ord(ch)-ord("0")
            elif ch =="+":
                res += sign*num
                num = 0
                sign = 1
            elif ch =="-":
                res += sign*num
                num = 0
                sign = -1
            elif ch =="(":
                # 把左括號左邊的res和sing放進stack, 然後把res和當前num歸0, sign 也回到1, 注意沒有leading negative, 所以可以放心把sign回到1
                stack.append((res, sign))
                res = 0
                num = 0
                sign = 1
            elif ch == ")":
                # 遇到又括號先初綻
                prev_res, prev_sign = stack.pop()
                #要先計算括號內的res
                res_inside = res+sign*num
                #再跟之前的res和sign做計算
                res = prev_res+prev_sign*(res_inside)
                #然後把sgin和num歸零
                num = 0
                sign = 1
            i+=1
        
        return res+sign*num