【leetcode】：Evaluate Reverse Polish Notation （python）
浏览数：24 /
时间：2015年06月08日
逆波兰式的求解，建立一个类栈容器，遍历给定的逆波兰表达式，遇到数字就push， 遇到操作符就进行出栈，连续出两次，因为给定的四则运算符都是双目的，这里注意下这两个操作数的先后顺序，因为对于加法和乘法没关系，但是对于减法和除法是有先后关系的。然后进行相应的运算，将结果push进栈中。
这里附带说明下python中进行除法运算与c，java系列中的除法的不同，就是向下取整的问题。这种不同表现在两个操作数符号不同时的情况。
在c 中 3 / -5 = 0，但是在python中， 结果却为 - 1。这种不同是什么原因呢？或者python为何做这样的调整呢？
我们把这种表达形式抽象一下， a / b = q, 余数为 r 。
a = ( b * q ) + r
但是我们发现在上例中，c 得到的结果会是 ( 0 * (-5) ) + ( - 2 ) = -2 是不等于 -5的，但是在python中， （ -1 * （-5）） + （ -2 ) = 5 - 2 = 3。
也就是python中的处理更符合数学的美感，（姑且这么讲吧)
class Solution:
def isOp(self, s):
return s == "+" or s == "-" or s == "*" or s == "/"
def add( self, op1, op2 ):
return op1 + op2
def sub( self, op1, op2 ):
return op1 - op2
def mul( self, op1, op2 ):
return op1 * op2
def div( self, op1, op2 ):
if op1 * op2 < 0:
return -((-op1) / op2 )
return op1 / op2
#mapping from op to func
operator = { "+": add, "-": sub, "*": mul, "/": div }
def evalRPN( self, tokens ):
nums = []
for s in tokens:
if self.isOp( s ):
op2 = nums.pop()
op1 = nums.pop()
re = self.operator.get( s )(self, op1, op2 )
nums.append( re )
else:
nums.append( int( s ) )
return nums[ 0 ]
【leetcode】：Evaluate Reverse Polish Notation （python）,古老的榕树,5-wow.com
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
