Python解析树ParseTree
- '''
- 构造一棵解析树
- 需要调用之前写过的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)
解压密码: detechn或detechn.com
免责声明
本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。
本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。
本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。