Medium, Stack

Question

計(jì)算Reverse Polish Notation數(shù)值表達(dá)式的值. 有效的數(shù)值運(yùn)算符包括 +, -, *, /.

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

Notes

不會(huì)有空序列

Answer

利用stack LIFO的特點(diǎn)，每當(dāng)發(fā)現(xiàn)operater 的時(shí)候處理之前的兩個(gè)數(shù)，然后把處理結(jié)果推回堆棧。

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()