描述

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

分析

逆波兰式求值，比较简单，注意代码里除法int(float(a) / b))是因为Python 2有一个奇葩的设置就是除法结果是负数的时候是向下取整的（我们需要向0取整）。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class (object):
    def eval(self, op, a, b):
        if op == '+':
            return a + b
        elif op == '-':
            return a - b
        elif op == '*':
            return a * b
        elif op == '/':
            return int(float(a) / b)

    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        ss = []
        for t in tokens:
            if t in '+-*/':
                b = ss.pop()
                a = ss.pop()
                ss.append(self.eval(t, a, b))
            else:
                ss.append(int(t))
        return ss[-1]