Python解析树ParseTree

本文阅读 1 分钟
首页 Python笔记 正文
  1. '''
  2. 构造一棵解析树
  3. 需要调用之前写过的Stack文件和BinaryTree文件
  4. '''
  5. from Stack import Stack
  6. from BinaryTree import BinaryTree
  7. import operator
  8. # 构造解析树
  9. def buildParseTree(fpexp):
  10. fplist = fpexp.split()
  11. pStack = Stack()
  12. eTree = BinaryTree('')
  13. pStack.push(eTree)
  14. currentTree = eTree
  15. for i in fplist:
  16. if i == '(':
  17. currentTree.insertLeft('')
  18. pStack.push(currentTree)
  19. currentTree = currentTree.getLeftChild()
  20. elif i not in ['+', '-', '*', '/', ')']:
  21. currentTree.setRootVal(int(i))
  22. parent = pStack.pop()
  23. currentTree = parent
  24. elif i in ['+', '-', '*', '/']:
  25. currentTree.setRootVal(i)
  26. currentTree.insertRight('')
  27. pStack.push(currentTree)
  28. currentTree = currentTree.getRightChild()
  29. elif i == ')':
  30. currentTree = pStack.pop()
  31. else:
  32. raise ValueError
  33. return eTree
  34. # 递归实现两个叶结点的运算
  35. def evaluate(parseTree):
  36. opers = {'+':operator.add, '-':operator.sub, '*':operator.mul, '/':operator.truediv}
  37. leftC = parseTree.getLeftChild()
  38. rightC = parseTree.getRightChild()
  39. if leftC and rightC:
  40. fn = opers[parseTree.getRootVal()]
  41. return fn(evaluate(leftC), evaluate(rightC))
  42. else:
  43. return parseTree.getRootVal()
  44. # 递归实现树的后序遍历
  45. def postorder(tree):
  46. if tree != None:
  47. postorder(tree.getLeftChild())
  48. postorder(tree.getRightChild())
  49. print(tree.getRootVal())
  50. # 利用后序遍历实现两个叶结点的运算
  51. def postordereval(tree):
  52. opers = {'+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.truediv}
  53. res1 = None
  54. res2 = None
  55. if tree:
  56. res1 = postordereval(tree.getLeftChild())
  57. res2 = postordereval(tree.getRightChild())
  58. if res1 and res2:
  59. return opers[tree.getRootVal()](res1, res2)
  60. else:
  61. return tree.getRootVal()
  62. # 递归实现中序遍历
  63. def inorder(tree):
  64. if tree != None:
  65. inorder(tree.getLeftChild())
  66. print(tree.getRootVal())
  67. inorder(tree.getRightChild())
  68. # 因为中序遍历会丢失括号信息, 因此尝试构造一个函数回复解析表达式
  69. def printexp(tree):
  70. sVal = ''
  71. if tree:
  72. sVal = '(' + printexp(tree.getLeftChild())
  73. sVal = sVal + str(tree.getRootVal())
  74. sVal = sVal + printexp(tree.getRightChild()) + ')'
  75. return sVal
  76. pt = buildParseTree("( ( 10 + 5 ) * 3 )")
  77. # pt.preorder()
  78. # postorder(pt)
  79. # ans = evaluate(pt)
  80. # print(ans)
  81. # print(postordereval(pt))
  82. # inorder(pt)
  83. # print(pt)
  84. sVal = printexp(pt)
  85. print(sVal)
解压密码: detechn或detechn.com

免责声明

本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。

本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。

本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。

Python归并排序
« 上一篇 01-21
Python实现队列
下一篇 » 01-21

发表评论