動機

就是算數，但不要被資料結構的postfix誤導，堅持都用stack的方式去iterate所有數字

Problem

Given a string s which represents an expression, evaluate this expression and return its value. 

The integer division should truncate toward zero.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

 

Example 1:

Input: s = 3+2*2Output: 7

Example 2:

Input: s =  3/2 Output: 1

Example 3:

Input: s =  3+5 / 2 Output: 5

 

Constraints:

  • 1 <= s.length <= 3 * 105
  • s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
  • s represents a valid expression.
  • All the integers in the expression are non-negative integers in the range [0, 231 - 1].
  • The answer is guaranteed to fit in a 32-bit integer.

Sol

當初是先想到stack，因為當初在資料結構就是用stack處理的

會需要stack是因為要在有優先序不同的情況下先算其他高的運算

但在遇到同樣高的運算時不能先放在stack之後再一起算，要當場直接算 還有如果stack中優先序比讀到的運算優先序還要高，也要當場直接算

def level(a):
    return 1 if (a in ["+","-"]) else 2
def applyOP(a,b,t):
    if t == '+':
        return a + b
    elif t == '*':
        return a * b
    elif t == '-':
        return a - b
    else:
        return a // b
def calc(arr):
    stk = []
    stk2 = []

    for t in arr:
        if t in ["+","-","*","/"]:
            if not stk:
                stk.append(t)
            else:
                if (level(stk[-1]) == 2 and level(t) == 2) or (level(stk[-1]) == 2 and level(t) == 1): # !!
                    rhs = stk2.pop()
                    lhs = stk2.pop()
                    op = stk.pop()
                    stk2.append(applyOP(lhs,rhs,op))
                stk.append(t)
        else:
            stk2.append(int(t))
    if stk and stk[-1] in ["*","/"]:
        op = stk.pop()
        rhs = stk2.pop()
        lhs = stk2.pop()
        stk2.append(applyOP(lhs,rhs,op))

    ans = stk2[0]
    i = 1
    #print(stk)
    #print(stk2)
    for op in stk: # 由左至右，不能用pop去算，不然會變成由右至左
        lhs = stk2[i]
        ans = applyOP(ans,lhs,op)
        i += 1
    return ans
def parse(s):
    ret = []
    tmp = ""
    for c in s:
        if c.isdigit():
            tmp += c
        else:
            if tmp:
                ret.append(tmp)
                tmp = ""
            if c in ["+","-","*","/"]:
                ret.append(c)
            elif c == " ":
                continue
    if tmp:
        ret.append(tmp)
    return ret

class Solution:
    def calculate(self, s: str) -> int:
        return calc(parse(s))