题目描述

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

题目大意

后缀表达式（逆波兰表达式）求值

解题思路

采用后缀表达式的标准解法即可，但使用Python解题时需要注意：

Python的负数除法运算与Java存在差异，而Leetcode此题的标准答案以Java程序的运算结果为准。

例如，在Java中，6 / (-132) == 0（Java使用的是截断），而在Python中，6 / (-132) == -1（Python使用的是floor）。

因此对除法的处理可以采用：int(float(x) / y)，即可与Java的结果保持一致。

Python代码如下：

class Solution:
	# @param tokens, a list of string
	# @return an integer
	def evalRPN(self, tokens):
		operators = ["+", "-", "*", "/"]
		operand_list = []
		for token in tokens:
			if token in operators:
				y, x = operand_list.pop(), operand_list.pop()
				operand_list.append(self.getVal(x, y, token))
			else:
				operand_list.append(int(token))
		return operand_list[0]
	
	def getVal(self, x, y, operator):
		return {
			'+': lambda x, y: x + y,
			'-': lambda x, y: x - y,
			'*': lambda x, y: x * y,
			'/': lambda x, y: int(float(x) / y),
		}[operator](x, y)

 

本文链接：http://bookshadow.com/weblog/2014/10/16/leetcode-evaluate-reverse-polish-notation/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码