from mystack import Stack
from myTree import BinaryTree
import operator
def ParseTree(fp):
fplist = fp.split()
fpstack = Stack()
fptree = BinaryTree('')
fpstack.push(fptree)
cur_tree = fptree
for i in fplist:
if i == '(':
cur_tree.insertLeft('')
fpstack.push(cur_tree)
cur_tree = cur_tree.getLeftChild()
elif i not in '+-*/)':
cur_tree.setRootVal(int(i))
cur_tree = fpstack.pop()
elif i in '+-*/':
cur_tree.setRootVal(i)
cur_tree.insertRight('')
fpstack.push(cur_tree)
cur_tree = cur_tree.getRightChild()
elif i == ')':
cur_tree = fpstack.pop()
else:
raise ValueError(f'Unknown Character : {i}')
return fptree
def evaluate(fptree):
operator_dict = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}
leftchild = fptree.getLeftChild()
rightchild = fptree.getRightChild()
if leftchild and rightchild:
func = operator_dict[fptree.getRootVal()]
result = func(evaluate(leftchild), evaluate(rightchild))
return result
else:
return fptree.getRootVal()
def printexp(tree):
s = ''
if tree:
if tree.getLeftChild():
s = '(' + printexp(tree.getLeftChild())
else:
s = printexp(tree.getLeftChild())
s = s + str(tree.getRootVal())
if tree.getRightChild():
s = s + printexp(tree.getRightChild()) + ')'
else:
s = s + printexp(tree.getRightChild())
return s
if __name__ == '__main__':
tree = ParseTree('( 9 - ( 8 / 2 )')
result = evaluate(tree)
print(result)
print(printexp(tree))
输出:
5.0
(9-(8/2))