数据结构&算法 解析树

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

实现代码:

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

def buildparsetree(exp):
    # 初始化存储结果的列表和操作符栈
    result = []
    stack = []

    # 遍历表达式的每个字符
    for c in exp:
        # 如果是数字，则将其添加到结果列表中
        if c.isdigit():
            result.append(c)
        # 如果是运算符，则将其添加到操作符栈中
        else:
            stack.append(c)

    # 将操作符栈中的所有操作符添加到结果列表中
    result.extend(stack[::-1])
    return result

# 测试代码
print(buildparsetree("1+2*3-4"))

建立表达式解析树：代码

class BinaryTree:
    def __init__(self, rootObj):
        self.key = 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.key = obj

    def getRootVal(self):
        return self.key


class Stack:
    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[-1]

    def size(self):
        return len(self.items)


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

利用表达式解析树求值：代码

import operator
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()

参考一下吧https://blog.csdn.net/qq_38882327/article/details/89308879

望采纳！谢谢！
你可以使用以下代码来求解析树（buildparsetree）处理字符间没有空格的数学表达式：

import re

def build_parse_tree(expression):
    """
    解析表达式并构建抽象语法树
    """
    # 删除表达式中的空格
    expression = re.sub(r'\s+', '', expression)

    # 匹配操作符
    match = re.search(r'[+-/*]', expression)
    if not match:
        # 如果没有匹配到操作符，说明表达式是一个数字
        return int(expression)
    else:
        # 如果匹配到操作符，则构建一个二元节点
        op_index = match.start()
        left_expression = expression[:op_index]
        right_expression = expression[op_index+1:]
        return (expression[op_index], build_parse_tree(left_expression), build_parse_tree(right_expression))

# 测试
expression = '4*5/6-7+8'
parse_tree = build_parse_tree(expression)
print(parse_tree)
# 输出：('+', ('-', ('*', 4, ('/', 5, 6)), 7), 8)

上面的代码使用了正则表达式来处理字符间没有空格的表达式。具体做法是，使用re.sub函数将表达式中的空格替换为空字符。然后使用re.search函数匹配操作符。如果匹配到了，则表示表达式中有操作符，需要构建二元节点。如果没有匹配到，则表示表达式中没有操作符，直接将表达式转化为数字并返回。