数据结构&算法 解析树

Question

求解析树（buildparsetree)处理字符间没有空格的数学表达式代码

Answer 1

实现代码:

import operator  # 操作符模块


# 自定义栈类
class Stack(object):
    def __init__(self):  # 初始化空栈
        self.items = []

    def isEmpty(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(object):
    # 初始化二叉树
    def __init__(self, rootObj):
        self.root = rootObj
        self.leftChild = None
        self.rightChild = None

    # 插入左子树
    def insertLeft(self, newNode):
        if self.leftChild == None:  # 若左子树为空，则
            self.leftChild = BinaryTree(newNode)  # 直接生成左子树
        else:
            t = BinaryTree(newNode)  # 生成初始二叉树
            t.leftChild = self.leftChild  # 将原左子树赋值给新二叉树的左子树
            self.leftChild = t  # 再将新二叉树赋值给原二叉树的左子树

    # 插入右子树
    def insertRight(self, newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

    # 获取右子树
    def getRightChild(self):
        return self.rightChild

    # 获取左子树
    def getLeftChild(self):
        return self.leftChild

    # 设置根节点值
    def setRootVal(self, obj):
        self.root = obj

    # 获取根节点值
    def getRootVal(self):
        return self.root


# 解析树生成函数
def buildParseTree(fpexp):
    fplist = fpexp.split()  # 将传入的完全括号表达式以空格分割成list
    pStack = Stack()  # 实例化栈类
    eTree = BinaryTree('')  # 实例化二叉树类，必须有''
    pStack.push(eTree)  # 将空二叉树的根节点(空)入栈
    currentTree = eTree  # 将空二叉树的根节点(空)作为当前节点
    for i in fplist:  # 循环处理表达式list元素
        if i == '(':  # 遇到"("，则
            currentTree.insertLeft('')  # 创建当前节点的空左子节点
            pStack.push(currentTree)  # 将当前节点入栈
            currentTree = currentTree.getLeftChild()  # 将该左子节点作为当前节点
        elif i not in ['+', '-', '*', '/', ')']:  # 遇到操作数，则
            currentTree.setRootVal(int(i))  # 将操作数设为当前节点的根值
            currentTree = pStack.pop()  # 将出栈节点(父节点)作为当前节点
        elif i in ['+', '-', '*', '/']:  # 遇到操作符，则
            currentTree.setRootVal(i)  # 将操作符设为当前节点的根植
            currentTree.insertRight('')  # 创建当前节点的空右子节点
            pStack.push(currentTree)  # 将当前节点入栈
            currentTree = currentTree.getRightChild()  # 将该右子节点作为当前节点
        elif i == ')':  # 遇到")"，则
            currentTree = pStack.pop()  # 将出栈节点(父节点)作为当前节点
        else:
            raise ValueError  # 抛出异常
    return eTree


# 求值函数，parseTree为当前整个解析树的根节点
def evaluate(parseTree):
    # opers字典是操作符与其对应的运算函数的集合
    opers = {'+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.truediv}
    leftC = parseTree.getLeftChild()  # 获取解析树根节点的左子树
    rightC = parseTree.getRightChild()  # 获取解析树根节点的右子树
    if leftC and rightC:  # 若当前节点存在左右子树，说明该节点不是叶节点，则
        fn = opers[parseTree.getRootVal()]  # 获取解析树根节点值对应的opers字典值作为运算函数
        return fn(evaluate(leftC), evaluate(rightC))  # 将递归获取的左右子树值运算后返回
    else:  # 若当前节点不存在左右子树，说明该节点是叶节点，则
        return parseTree.getRootVal()  # 返回解析树的根节点值


# 前序遍历函数
def preorder(tree):
    if tree:  # 若树不为None，则
        print(tree.getRootVal())  # 打印根节点值
        preorder(tree.getLeftChild())  # 前序遍历左子树
        preorder(tree.getRightChild())  # 前序遍历右子树


# 中序遍历函数
def inorder(tree):
    if tree:  # 若树不为None，则
        inorder(tree.getLeftChild())  # 中序遍历左子树
        print(tree.getRootVal())  # 打印根节点值
        inorder(tree.getRightChild())  # 中序遍历右子树


# 后序遍历函数
def postorder(tree):
    if tree:  # 若树不为None，则
        postorder(tree.getLeftChild())  # 后序遍历左子树
        postorder(tree.getRightChild())  # 后序遍历右子树
        print(tree.getRootVal())  # 打印根节点值


pt = buildParseTree("( ( 10 + 5 ) * 3 )")  # 将完全括号表达式生成解析树
print(evaluate(pt))  # 求该解析树的值
# preorder(pt)                                    #前序遍历树
# inorder(pt)                                        #中序遍历树
# postorder(pt)                                     #后序遍历树

运行结果:

45

Process finished with exit code 0