Evaluate Reverse Polish Notation

Medium, Stack

Question

计算Reverse Polish Notation数值表达式的值. 有效的数值运算符包括 +, -, *, /.

Examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9;
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Notes

不会有空序列

Answer

利用stack LIFO的特点，每当发现operater 的时候处理之前的两个数，然后把处理结果推回堆栈。

class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        operators = {
            '+': lambda x, y: x+y,
            '-': lambda x, y: x-y,
            '*': lambda x, y: x*y,
            '/': lambda x, y: int(float(x)/ y )
        }
            
        stack = []
        for token in tokens:
            if token in operators:
                y, x = stack.pop(), stack.pop()
                stack.append(operators[token](x,y))
            else:
                stack.append(int(token))
        return stack.pop()