227. Basic Calculator II.py

class Solution:
    """
    1.有加號, 減號, 乘號, 除號!沒有括號
    2.All the integers in the expression are non-negative integers, which means there's no leading negative sign and no 3*-5
    10+3-2
          i
        
    3+5
     i
    1.遇到+/-號, 我們就可以parse下一個num, 然後根據sign把num放進stack
    2.遇到*和/, 就要岀棧把最左邊的num出棧來做運算, 但遇到除號要注意負數的//要先取正號, 除完再放負號把結果放回stack
    3. parse下一個num要注意有space在裡面要處理
    4 最後再把所有結果從stack倒出來相加.
    """
    def calculate(self, s: str) -> int:
        def parse_next_num(i, s, n):
            num = 0
            while i < n:
                ch = s[i]
                if ch.isdigit():
                    num *= 10
                    num += ord(ch) - ord("0")
                    i+=1
                elif ch == " ":
                    i+=1
                else:
                    break
            return num, i
        
        n = len(s)
        i = 0
        stack = []
        while i < n:
            ch = s[i]
            if ch == " ":
                i+=1
                continue
            if ch.isdigit():
                num, i = parse_next_num(i, s, n)
                stack.append(num)
            elif ch == "+":
                num, i = parse_next_num(i+1, s, n)
                stack.append(num)
            elif ch == "-":
                num, i = parse_next_num(i+1, s, n)
                stack.append(-num)
            elif ch == "*":
                leftmost_num = stack.pop()
                num, i = parse_next_num(i+1, s, n)
                stack.append(leftmost_num*num)
            elif ch == "/":
                leftmost_num = stack.pop()
                num, i = parse_next_num(i+1, s, n)
                stack.append(int(leftmost_num/num))
                # if leftmost_num > 0:
                #     stack.append(leftmost_num//num)
                # else:
                #     leftmost_num = abs(leftmost_num)
                #     tmp = leftmost_num//num
                #     stack.append(-tmp)
        res = 0
        while stack:
            res+=stack.pop()
        return res
    
    def calculate(self, s: str) -> int:
        def cal_update(op, num, stack):
            if op == "+":
                stack.append(num)
            elif op == "-":
                stack.append(-num)
            elif op == "*":
                stack.append(stack.pop()*num)
            elif op == "/":
                stack.append(int(stack.pop()/num))
        s = s + "+" # 最後補個+是為了要根據之前的op和num做運算並更新stack, 最後這個+不會對結果有任何實質的影響
        n = len(s)
        i = 0
        stack = []
        op = "+" # I assume no leading negative integeters. For example, "-3+2"
        num = 0
        while i < n:
            ch = s[i]
            if ch in set("+-*/"):
                # 根據之前的op和num做運算並更新stack
                cal_update(op, num, stack)
                num = 0
                op = ch
            elif ch.isdigit():
                num*=10
                num+=ord(ch)-ord("0")
            i+=1
        #print(stack)
        return sum(stack)