150. Evaluate Reverse Polish Notation

# Medium

Not hard if know the principle behind and coding as the process of human solving

Key idea: when see notation, compute the two numbers before it.

stack is perfect to this problem

Solution:

1. traversal all elements of the list

2. if it's a number, push to stack

3. if it's a notation, pop two numbers and compute, then push back to stack

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:      
        i = 0
        stack = []
        while i < len(tokens):
            st = tokens[i]
            if st != '+' and st != '-' and st != '*' and st != '/':
                stack.append(st)
            else:
                num2 = int(stack.pop())
                num1 = int(stack.pop())
                if st == '+':
                    res = num1 + num2
                elif st == '-':
                    res = num1 - num2
                elif st == '*':
                    res = num1 * num2
                else:
                    if num1*num2 < 0:
                        res = num1*(-1)//num2 * (-1)
                    else:
                        res = num1//num2
                stack.append(res)
            i += 1
        
        return stack.pop()

如果用python则不能用recursive来做，因为python不能传递reference，意味着函数的参数无法成为全局变量，而导致一直在变

Time = $o(n)$ , space = $O(n)$