树的应用举例——四则计算

计算四则运算：

import ninth lesson_Tree

def build_parse_Tree(alist):
    alst = alist.split()
    # 创建一个节点栈
    astack = []
    res_Tree = BinaryTree('')
    astack.append(res_Tree)
    currentTree = res_Tree

    for i in alst:
        # 如果是'('，则创建左子节点，并把该父节点记录入栈，再把指针指向左子节点
        if i == '(':
            currentTree.insertLeft('')
            astack.append(currentTree)
            currentTree = currentTree.getLeftChildren()
        # 如果是数字，则给节点赋值，并把父节点出栈，再把指针指向父节点
        elif i is not in ['+', '-', '*', '/']:
            currentTree.setVal(int(i))
            currentTree = astack.pop()
        # 如果是符号，则给节点赋值符号，并把该节点入栈，并创建右子节点，再把指针指向右子节点
        elif i in ['+', '-', '*', '/']:
            currentTree.setVal(i)
            currentTree.insertRight('')
            astack.append(currentTree)
            currentTree = currentTree.getRightChildren()
        # 如果是')'，则返回上一节点，即将栈压出上一节点
        elif i == ')':
            currentTree = astack.pop()

        else:
            raise ValueError

    return res_Tree

# 递归调用，基本结束条件为节点为叶节点，返回叶节点的值进行计算
def evaluate(res_Tree):
    opers = {'+': operator.add(), '-': operator.sub(), '*': operator.mul(), '/': operator.truediv()}

    left = res_Tree.getLeftChildren()
    right = res_Tree.getRightChildren()

    if left and right:
        fn = opers[res_Tree.getRootVal()]
        return fn(evaluate(left),evaluate(right))
    else:
        return res_Tree.getRootVal()