FilesExpand file tree

 master

/

ParseTree.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

96 lines (85 loc) · 2.65 KB

 master

/

ParseTree.py

Copy path

Top

File metadata and controls

• Code
• Blame

96 lines (85 loc) · 2.65 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

'''

构造一棵解析树

需要调用之前写过的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)