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

表达式树是一种二叉树，用于表示数学表达式。在这种二叉树中，每个叶节点是一个操作数，每个非叶子节点是一个运算符。构造表达式树是将给定的表达式转换为二叉树的过程。在构造表达式树之前，需要了解表达式树的定义和二叉树的相关知识。

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

表达式树的定义

表达式树是由以下几个部分组成的：

• 叶节点：操作数，即表达式中的数字或字母；
• 非叶节点：运算符，即表达式中的加减乘除等数学符号。

对于每个非叶节点，它的左右子节点分别为该运算符的操作数。

二叉树的相关知识

二叉树是一种特殊的树，每个节点最多有两个子节点。在二叉树中，左子节点比右子节点小或等于该节点。二叉树具有以下几个特点：

• 二叉树可以为空树，即没有节点；
• 二叉树的叶节点深度相同；
• 二叉树可以不是完整填充的，即可以存在只有一个子节点的节点。

了解了表达式树和二叉树的相关知识后，可以开始编写构造表达式树的 Python 程序了。

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def buildExpTree(s):
    # 转换为后缀表达式
    postfix = []
    stack = []
    priorities = {'+': 1, '-': 1, '*': 2, '/': 2}
    for c in s:
        if c.isdigit():
            postfix.append(c)
        elif c.isalpha():
            postfix.append(c)
        elif c == '(':
            stack.append(c)
        elif c == ')':
            while stack[-1] != '(':
                postfix.append(stack.pop())
            stack.pop()
        else:
            while stack and stack[-1] != '(' and priorities[stack[-1]] >= priorities[c]:
                postfix.append(stack.pop())
            stack.append(c)
    while stack:
        postfix.append(stack.pop())

    # 构造表达式树
    stack = []
    for c in postfix:
        if c.isdigit() or c.isalpha():
            stack.append(TreeNode(c))
        else:
            node = TreeNode(c)
            node.right = stack.pop()
            node.left = stack.pop()
            stack.append(node)
    return stack[0]

上面的程序中，buildExpTree 函数从给定的表达式字符串 s 中构造表达式树。具体步骤如下：

1. 将中缀表达式转换为后缀表达式；
2. 构造表达式树。

下面分别介绍这两个步骤的具体实现。

将中缀表达式转换为后缀表达式

中缀表达式是人类习惯的数学表达式表示法，例如 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3。但是，计算机并不擅长处理这种表达式，因为它需要根据运算优先级和括号来正确计算表达式。

因此，我们可以将中缀表达式转换为后缀表达式，这种表达方式被计算机更容易处理。例如， 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 的后缀表达式为 3 4 2 * 1 5 - 2 3 ^ ^ / +。在后缀表达式中，操作数排在前面，运算符排在后面。下面是如何将中缀表达式转换为后缀表达式的 Python 代码：

postfix = []  # 存储后缀表达式
stack = []  # 存储运算符的栈
priorities = {'+': 1, '-': 1, '*': 2, '/': 2}  # 运算符优先级
for c in s:
    if c.isdigit():  # 如果是数字，将其添加到后缀表达式中
        postfix.append(c)
    elif c.isalpha():  # 如果是字母，将其添加到后缀表达式中
        postfix.append(c)
    elif c == '(':  # 如果是左括号，将其压入栈中
        stack.append(c)
    elif c == ')':  # 如果是右括号，将栈中的运算符弹出并添加到后缀表达式中，直到遇到左括号为止
        while stack[-1] != '(':
            postfix.append(stack.pop())
        stack.pop()
    else:  # 如果是运算符，比较其优先级，将栈中优先级大于或等于该运算符的运算符弹出并添加到后缀表达式中，然后将该运算符压入栈中
        while stack and stack[-1] != '(' and priorities[stack[-1]] >= priorities[c]:
            postfix.append(stack.pop())
        stack.append(c)

# 将栈中剩余的运算符弹出并添加到后缀表达式中
while stack:
    postfix.append(stack.pop())

上面的代码中，s 是中缀表达式字符串。首先创建两个数组 postfix 和 stack，其中 postfix 存储后缀表达式，stack 存储运算符。priorities 是一个字典，用于存储运算符的优先级。

然后，遍历中缀表达式中的每个字符。如果是数字或字母，将其添加到后缀表达式中；如果是左括号，将其压入栈中；如果是右括号，将栈中的运算符弹出并添加到后缀表达式中，直到遇到左括号为止；如果是运算符，将栈中优先级大于或等于该运算符的运算符弹出并添加到后缀表达式中，然后将该运算符压入栈中。

最后，将栈中剩余的运算符弹出并添加到后缀表达式中。这样，我们就得到了中缀表达式的后缀表达式表示。

构造表达式树

有了后缀表达式，可以使用一个栈来构造表达式树。遍历后缀表达式中的每个字符，如果是操作数，将其转换为节点并压入栈中；如果是运算符，将其弹出栈中两个操作数作为子节点，并将运算符节点作为父节点，然后将运算符节点压入栈中。

最后，栈中只剩下一个节点，即表达式树的根节点。下面是如何构造表达式树的 Python 代码：

stack = []  # 存储节点的栈
for c in postfix:
    if c.isdigit() or c.isalpha():  # 如果是数字或字母，创建节点并压入栈中
        stack.append(TreeNode(c))
    else:  # 如果是运算符，弹出栈中两个节点作为其子节点，并将运算符作为父节点，然后将其压入栈中
        node = TreeNode(c)
        node.right = stack.pop()
        node.left = stack.pop()
        stack.append(node)

# 栈中只剩下一个节点，即表达式树的根节点
return stack[0]

上面的代码中，postfix 是后缀表达式数组。

首先创建一个栈 stack，用于存储节点。遍历后缀表达式中的每个字符，如果是操作数，创建一个节点并压入栈中；如果是运算符，弹出栈中两个节点作为其右子节点和左子节点，并将运算符作为父节点，然后将其压入栈中。

最后，栈中只剩下一个节点，即表达式树的根节点。这个节点即为整个表达式的表达式树。

示例

假设有一个表达式 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3，我们可以使用上面的程序来构造表达式树。

s = '3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3'
root = buildExpTree(s)

我们可以使用中序遍历来输出表达式树，验证结果是否正确：

def inorderTraversal(root):
    if root:
        inorderTraversal(root.left)
        print(root.val, end=' ')
        inorderTraversal(root.right)

inorderTraversal(root)

输出结果为：

3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3

我们可以使用图形方式来表示表达式树：

            +
           / \
          3   /
             / \
            *   ^
           / \ / \
          4  2 1  3

结论

通过本文的介绍，我们可以了解到表达式树的定义和构造方法，并学习了如何将中缀表达式转换为后缀表达式，以及如何使用栈来构造表达式树的 Python 程序。有了表达式树，我们可以方便地对数学表达式进行求值，也可以通过表达式树将表达式转换为其他形式。