首页 > 代码库 > Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation

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

原题链接: https://oj.leetcode.com/problems/evaluate-reverse-polish-notation/

题目大意: 逆波兰表达式

思路: 利用栈实现, 注意+, -单目运算符; 另外目前leetcode使用的python为2.7.5, 除法不是精确的除法, 两个整数相除是地板除, 浮点数除是精确的除法; 注意负数的判断, 使用isdigit是判断不了的;

 1 class Solution: 2     # @param tokens, a list of string 3     # @return an integer 4     def evalRPN(self, tokens): 5         stack = list() 6  7         for token in tokens: 8             try: 9                 tmp = int(token)10             except ValueError: #operator11                 if token == +: #may be a unary operator12                     if len(stack) > 1:13                         o1 = stack.pop()14                         o2 = stack.pop()15 16                         stack.append(o2 + o1)17                 elif token == -:18                     if len(stack) > 1:19                         o1 = stack.pop()20                         o2 = stack.pop()21 22                         stack.append(o2 - o1)23                     else:24                         o1 = stack.pop()25                         stack.append(-o1)26 27                 elif token == *:28                     o1 = stack.pop()29                     o2 = stack.pop()30 31                     stack.append(o2 * o1)32                 else:33                     o1 = stack.pop()34                     o2 = stack.pop()35 36                     stack.append(int(float(o2) / o1))37 38             else: #number39                 stack.append(tmp)40 41             42         return stack[0]