Evaluate Reverse Polish Notation

题目描述

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

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

解题方法

这一题的基本思路就是用stack，每次遇到operator的时候pop出最后的两个， 计算后再加入到stack上。

用python解题需要注意的是，python的负数出发运算与java存在差异。

在java中，6/-132 = 0, java使用的是截断。 而在python中，6/-132 = -1, python使用的是floor。

Solution

class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        if not tokens:
            return 0

        stack = []
        for token in tokens:
            if token not in ["+", "-", "*", "/"]:
                stack.append(float(token))
            else:
                second = stack.pop()
                first = stack.pop()
                if token == "+":
                    r = first + second
                elif token == "-":
                    r = first - second
                elif token == "*":
                    r = first * second
                elif token == "/":
                    r = int(first / second)
                stack.append(r)

        return int(stack[0])

Reference