''' 构造一棵解析树 需要调用之前写过的Stack文件和BinaryTree文件 ''' from Stack import Stack from BinaryTree import BinaryTree import operator # 构造解析树 def buildParseTree(fpexp): fplist = fpexp.split() pStack = Stack() eTree = BinaryTree('') pStack.push(eTree) currentTree = eTree for i in fplist: if i == '(': currentTree.insertLeft('') pStack.push(currentTree) currentTree = currentTree.getLeftChild() elif i not in ['+', '-', '*', '/', ')']: currentTree.setRootVal(int(i)) parent = pStack.pop() currentTree = parent elif i in ['+', '-', '*', '/']: currentTree.setRootVal(i) currentTree.insertRight('') pStack.push(currentTree) currentTree = currentTree.getRightChild() elif i == ')': currentTree = pStack.pop() else: raise ValueError return eTree # 递归实现两个叶结点的运算 def evaluate(parseTree): opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv} leftC = parseTree.getLeftChild() rightC = parseTree.getRightChild() if leftC and rightC: fn = opers[parseTree.getRootVal()] return fn(evaluate(leftC), evaluate(rightC)) else: return parseTree.getRootVal() # 递归实现树的后序遍历 def postorder(tree): if tree != None: postorder(tree.getLeftChild()) postorder(tree.getRightChild()) print(tree.getRootVal()) # 利用后序遍历实现两个叶结点的运算 def postordereval(tree): opers = {'+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.truediv} res1 = None res2 = None if tree: res1 = postordereval(tree.getLeftChild()) res2 = postordereval(tree.getRightChild()) if res1 and res2: return opers[tree.getRootVal()](res1, res2) else: return tree.getRootVal() # 递归实现中序遍历 def inorder(tree): if tree != None: inorder(tree.getLeftChild()) print(tree.getRootVal()) inorder(tree.getRightChild()) # 因为中序遍历会丢失括号信息, 因此尝试构造一个函数回复解析表达式 def printexp(tree): sVal = '' if tree: sVal = '(' + printexp(tree.getLeftChild()) sVal = sVal + str(tree.getRootVal()) sVal = sVal + printexp(tree.getRightChild()) + ')' return sVal pt = buildParseTree("( ( 10 + 5 ) * 3 )") # pt.preorder() # postorder(pt) # ans = evaluate(pt) # print(ans) # print(postordereval(pt)) # inorder(pt) # print(pt) sVal = printexp(pt) print(sVal)