描述：计算逆波兰表达法的结果
Sample：
["", "", "+", "", "*"] -> ((2 + 1) * 3) -> 9
["", "", "", "/", "+"] -> (4 + (13 / 5)) -> 6
使用stack实现：
def is_op(c):
return c in ['+', '-', '*', '/'] def divide(x, y):
if (x * y) < 0:
return -1 * ((-x)/y)
return x/y class Solution:
# @param tokens, a list of string
# @return an integer
def evalRPN(self, tokens):
opDict = {'+': lambda x,y: x+y,
'-': lambda x,y: x-y,
'*': lambda x,y: x*y,
'/': divide}
record = [] for item in tokens:
if is_op(item):
second = record.pop()
first = record.pop()
record.append(opDict[item](first, second))
else:
record.append(int(item))
return record[0]
使用树实现：
def is_op(c):
return c in ['+', '-', '*', '/'] def divide(x, y):
if (x * y) < 0:
return -1 * ((-x)/y)
return x/y class Tree:
def __init__(self, data):
self.data = data
self.parent = None
self.left = None
self.right = None class Solution:
# @param tokens, a list of string
# @return an integer
def __init__(self):
self.opDict = {'+': lambda x,y: x+y,
'-': lambda x,y: x-y,
'*': lambda x,y: x*y,
'/': divide} def builtTree(self, tokens):
if not is_op(tokens[-1]):
return int(tokens[-1]) # if element is an operator
cur_tree = Tree(tokens[-1])
top_tree = cur_tree for item in tokens[-2::-1]:
if cur_tree.right is None:
if is_op(item):
cur_tree.right = Tree(item)
cur_tree.right.parent = cur_tree
cur_tree = cur_tree.right
else:
cur_tree.right = int(item) if cur_tree.right and cur_tree.left:
cur_tree = self.getUpperNode(cur_tree)
continue if cur_tree.left is None:
if is_op(item):
cur_tree.left = Tree(item)
cur_tree.left.parent = cur_tree
cur_tree = cur_tree.left
else:
cur_tree.left = int(item) if cur_tree.right is not None and cur_tree.left is not None:
cur_tree = self.getUpperNode(cur_tree) return top_tree # Move to upper node if cur node if full. If top_node return.
def getUpperNode(self, node):
while node.right is not None and node.left is not None:
if node.parent is None:
return node node = node.parent return node def getValue(self, node):
if type(node) is type(1):
return node
else:
return self.getResult(node) def getResult(self, treeNode):
leftValue = self.getValue(treeNode.left)
rightValue = self.getValue(treeNode.right) result = self.opDict[treeNode.data](leftValue, rightValue) return result def evalRPN(self, tokens):
topNode = self.builtTree(tokens) if type(topNode) is type(1):
return topNode
else:
resultNum = self.getResult(topNode)
return resultNum
备注-1：if cur_node.right is None 不能用 if cur_node.right 因为cur_node.right 如果是数字0的话会有问题 当然 不转成int的话直接存string等到运算时再转int应该就可以这样写了
备注-2：python的除法跟c++不太一样 3/-5 = -1
结论：
根据问题的具体特性，选择合适的数据结构解决问题会差别很大