python---数学表达式的分析树实现，python表达式,先走一遍，前面很多知

python---数学表达式的分析树实现，python表达式,先走一遍，前面很多知

先走一遍，

前面很多知道点，都串起来了。

# coding = utf-8# 使用列表实现栈的功能class Stack:    def __init__(self):        self.items = []    # 是否为空    def is_empty(self):        return self.items == []    # 进栈    def push(self, item):        self.items.append(item)    # 出栈    def pop(self):        return self.items.pop()    # 返回栈顶值，不改变栈    def peek(self):        return self.items[len(self.items) - 1]    # 返回栈长度    def size(self):        return len(self.items)# 使用递归实现二叉树基本功能class BinaryTree:    def __init__(self, root_obj):        self.key = root_obj        self.left_child = None        self.right_child = None    def insert_left(self, new_node):        node = BinaryTree(new_node)        if self.left_child is None:            self.left_child = node        else:            node.left_child = self.left_child            self.left_child = node    def insert_right(self, new_node):        node = BinaryTree(new_node)        if self.right_child is None:            self.right_child = node        else:            node.right_child = self.right_child            self.right_child = node    def get_right_child(self):        return self.right_child    def get_left_child(self):        return self.left_child    def set_root_val(self, obj):        self.key = obj    def get_root_val(self):        return self.key# 建立一个算术分析树def build_parse_tree(fp_exp):    fp_list = fp_exp.split()    p_stack = Stack()    e_tree = BinaryTree(‘‘)    p_stack.push(e_tree)    current_tree = e_tree    for item in fp_list:        if item == ‘(‘:            current_tree.insert_left(‘‘)            p_stack.push(current_tree)            current_tree = current_tree.get_left_child()        elif item not in [‘+‘, ‘-‘, ‘*‘, ‘/‘, ‘)‘]:            current_tree.set_root_val(int(item))            parent = p_stack.pop()            current_tree = parent        elif item in [‘+‘, ‘-‘, ‘*‘, ‘/‘]:            current_tree.set_root_val(item)            current_tree.insert_right(‘‘)            p_stack.push(current_tree)            current_tree = current_tree.get_right_child()        elif item == ‘)‘:            current_tree = p_stack.pop()        else:            raise ValueError    return e_tree# 匹配加减乘除规则class DoMatch:    @staticmethod    def add(op1, op2):        return op1 + op2    @staticmethod    def sub(op1, op2):        return op1 - op2    @staticmethod    def mul(op1, op2):        return op1 * op2    @staticmethod    def true_div(op1, op2):        return op1 / op2# 算术分析式的求值def evaluate(parse_tree):    operator = DoMatch()    opers = {‘+‘: operator.add,             ‘-‘: operator.sub,             ‘*‘: operator.mul,             ‘/‘: operator.true_div             }    left_c = parse_tree.get_left_child()    right_c = parse_tree.get_right_child()    if left_c and right_c:        fn = opers[parse_tree.get_root_val()]        return fn(evaluate(left_c), evaluate(right_c))    else:        return parse_tree.get_root_val()# 前序遍历def pre_order(tree):    if tree:        print(tree.get_root_val())        pre_order(tree.get_left_child())        pre_order(tree.get_right_child())# 后序遍历def post_order(tree):    if tree:        print(tree.get_root_val())        post_order(tree.get_left_child())        post_order(tree.get_right_child())# 中序遍历def in_order(tree):    if tree:        print(tree.get_root_val())        in_order(tree.get_left_child())        in_order(tree.get_right_child())# 分析树打印def print_exp(tree):    s_val = ‘‘    if tree:        s_val = ‘(‘ + str(print_exp(tree.get_left_child()))        s_val = s_val + str(tree.get_root_val())        s_val = s_val + str(print_exp(tree.get_right_child())) + ‘)‘    return s_valpt = build_parse_tree("( ( 7 + 3 ) * ( 5 - 2 ) )")print(‘=========pre_order================‘)pre_order(pt)print(‘=========post_order================‘)post_order(pt)print(‘=========in_order================‘)in_order(pt)print(‘=========print_exp================‘)print(print_exp(pt))print(‘=========evaluate================‘)print(evaluate(pt))

=========pre_order================*+73-52=========post_order================*+73-52=========in_order================*+73-52=========print_exp================(((7)+(3))*((5)-(2)))=========evaluate================30

python---数学表达式的分析树实现