构造给定表达式的表达式树的Python程序

表达式树是叶节点具有要操作的值，内部节点包含叶节点将执行的运算符的树结构。

例如： 4 + ((7 + 9) * 2)将具有以下表达式树-

更多Python相关文章，请阅读：Python 教程

解决此问题的方法

为了为给定的表达式构造表达式树，通常使用堆栈数据结构。最初，我们迭代给定的后缀表达式，并按照以下步骤执行-

如果我们在给定表达式中得到一个操作数，则将其推送到堆栈中。它将成为表达式树的根。
如果运算符在表达式中获得两个值，则将其作为其子级添加到表达式树中，并将它们推入当前节点。
重复步骤1和步骤2，直到我们完成所有的给定表达式。

例子

class stack:
    def __init__(self):
        self.arr = []
    def push(self, data):
        self.arr.append(data)
    def pop(self):
        try:
            return self.arr.pop(-1)
        except:
            pass
    def top(self):
        try:
            return self.arr[-1]
        except:
            pass
    def size(self):
        return len(self.arr)
# 表达式树节点类
class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
# 表达式树类
class exp_tree:
    def __init__(self, postfix_exp):
        self.exp = postfix_exp
        self.root = None
        self.createTree(self.exp)
    def isOperator(self, char):
        optr = [" ", "-", "*", "/", "^"]
        if char in optr: # 如果指定的字符为运算符
            return True # 然后返回true
        return False # 否则返回false
    def createTree(self, exp):
        s = stack()
        # 存储其任一子节点为空的运算符节点
        self.root = node(exp[-1])
        # 后缀表达式的最后一个字符始终是运算符
        s.push(self.root)
        # 移动到剩余的后缀表达式
        for i in "".join(reversed(exp[:-1])):
            curr_node = s.top()
            if not curr_node.right:
                # 如果当前节点的右节点为空
                temp = node(i)
                curr_node.right = temp
                if self.isOperator(i):
                    s.push(temp)
            else: # 如果当前节点的左节点为空
                temp = node(i)
                curr_node.left = temp
                # 如果当前节点没有子节点为空
                s.pop() # 从栈中弹出当前节点
                if self.isOperator(i):
                    s.push(temp)
    def inorder(self, head):
        # 表达式树的中序遍历
        # 中序遍历= >左、根、右
        if head.left:
            self.inorder(head.left)
        print(head.data, end=" ")
        if head.right:
            self.inorder(head.right)
    def infixExp(self):
        # 表达式树的中序遍历给出中缀表达式
        self.inorder(self.root)
        print()
if __name__ == "__main__":
    postfixExp = "ab ef*g*-"
    et = exp_tree(postfixExp)
    et.infixExp()

运行上述代码将生成以下输出：