照着敲了代码 但是不知道怎么测试 数据结构 语义树 算数式计算 递归 栈

Nyyyb_112358

学二叉树照着老师写的代码 内容是把数学表达式拆成二叉树在计算 比如（（3+5）*（3-1））这样的  第一第二块就是定义栈和二叉树 第三部分拆成树 第四部分递归计算 我不知道该怎么验证我写的对不对 后面那几行都是我自己写的但是运行没有任何输出

1. class Stack:    # 定义一个栈类
   
2.      def __init__(self):
   
3.          self.items = []
   
4. 
   
5.      def isEmpty(self):
   
6.          return self.items == []
   
7. 
   
8.      def push(self, item):
   
9.          self.items.append(item)
   
10. 
    
11.      def pop(self):
    
12.          return self.items.pop()
    
13. 
    
14.      def peek(self):
    
15.          return self.items[len(self.items)-1]
    
16. 
    
17.      def size(self):
    
18.          return len(self.items)
    
19. 
    
20. class BinTree:  # 定义一个二叉树类以及其方法
    
21.     def __init__(self, rt_obj):
    
22.         super().__init__()
    
23.         self.key = rt_obj
    
24.         self.l_child = None
    
25.         self.r_child = None
    
26. 
    
27.     def ins_l(self, new_n):
    
28.         if self.l_child == None:
    
29.             self.l_child = BinTree(new_n)
    
30.         else:
    
31.             t = BinTree(new_n)
    
32.             t.l_child = self.l_child
    
33.             self.l_child = t
    
34. 
    
35.     def ins_r(self, new_n):
    
36.         if self.r_child == None:
    
37.             self.r_child = BinTree(new_n)
    
38.         else:
    
39.             t = BinTree(new_n)
    
40.             t.r_child = self.r_child
    
41.             self.r_child = t
    
42. 
    
43.     def get_root_val(self):
    
44.         return self.key
    
45. 
    
46.     def set_root_val(self, key):
    
47.         self.key = key
    
48. 
    
49.     def get_l_child(self):
    
50.         return self.l_child
    
51. 
    
52.     def get_r_child(self):
    
53.         return self.r_child
    
54. 
    
55. 
    
56. 
    
57. 
    
58. def build_parsetree(fpexp):     # 把表达式拆分成一个二叉树
    
59.     fplist = []
    
60.     for i in fpexp:
    
61.         fplist.append(i)        # 拆分表达式存到一个空列表里
    
62.     pStack = Stack()    # 定义一个空栈
    
63.     eTree = BinTree('')     # 空二叉树
    
64.     pStack.push(eTree)      # 入栈
    
65.     cur_tree = eTree    # 追踪扫描的字符
    
66.     for i in fplist:
    
67.         if i == '(':     
    
68.             cur_tree.ins_l('')      # 左括号加一个子树
    
69.             pStack.push(cur_tree)       # 入栈
    
70.             cur_tree = cur_tree.get_l_child()       # 追踪扫描的字符
    
71.         elif i not in [')', '+', '-', '*', '/']:    # 运算数
    
72.             cur_tree.set_rt_val(int(i))     # 结点设置为运算数的值
    
73.             parent = pStack.pop()   
    
74.             cur_tree = parent       # 出栈 追踪扫描光标
    
75.         elif i in ['*', '+', '-', '/']:     # 运算符   
    
76.             cur_tree.set_rt_val(i)          # 节点设置为运算符
    
77.             cur_tree.ins_r('')              # 添加一个右子树
    
78.             pStack.push(cur_tree)           # 下沉入栈
    
79.             cur_tree = cur_tree.get_r_child()       # 追踪扫描光标
    
80.         elif i == ')':          # 右括号
    
81.             pStack.pop()        # 出栈            
    
82.         else:
    
83.             raise ValueError
    
84.     return eTree
    
85. 
    
86. import operator as op
    
87. 
    
88. def evaluate(parse_tree):       # 递归求值 这段我自己不是太懂
    
89.     ops = {'+': op.add, '-': op.sub, '*': op.mul, '/': op.truediv}
    
90.     # 定义一个运算符字典
    
91.     l = parse_tree.get_l_child()
    
92.     r = parse_tree.get_r_child()        
    
93. 
    
94.     if l and r:
    
95.         fn = parse_tree.get_root_val()
    
96.         return fn(evaluate(l), evaluate(r))
    
97.     else:
    
98.         print('hello world')
    
99.         return parse_tree.get_root_val()
    
100.         
     
101. 
     
102. m = "((3+2)*(4-2))"         # 这段我自己写的想测试下这个程序 但是没反应
     
103. n = build_parsetree(m)
     
104. n.get_root_val()
     
105. o = evaluate(n)
     
106. print(o)
     
107. 
     
108. 
     
109. 
     

复制代码

Nyyyb_112358

大概写了点注释 大家凑合看吧

Nyyyb_112358

弄好了 bug出在没有跟踪好光标 line 81             pStack.pop()        # 出栈     应该改成           cur_tree = pStack.pop()        # 出栈