用python实现真值表达式树

好的，实现真值表达式树需要用到二叉树和递归算法，以下是一个简单的 Python 实现：

首先，我们定义一个二叉树节点类，包含了节点的值、左子树和右子树：

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

然后，我们定义一个函数 `build_tree(expr)` 来构建真值表达式树，其中 `expr` 是一个字符串，表示一个真值表达式：

def build_tree(expr):
    if len(expr) == 1:
        return TreeNode(expr[0])
    else:
        root = TreeNode(expr[-1])
        i = len(expr) - 2
        while i >= 0 and expr[i] not in ['&', '|', '!']:
            i -= 1
        root.left = build_tree(expr[:i+1])
        root.right = build_tree(expr[i+1:-1])
        return root

这个函数的实现利用了递归的思想，对于一个长度大于 1 的表达式，我们可以找到最后一位符号作为根节点，然后递归构建左子树和右子树。

最后，我们定义一个函数 `evaluate(root, vars)` 来计算真值表达式树的值，其中 `root` 是真值表达式树的根节点，`vars` 是一个字典，表示变量名和对应的真值：

def evaluate(root, vars):
    if root.val == '!':
        return not evaluate(root.right, vars)
    elif root.val == '&':
        return evaluate(root.left, vars) and evaluate(root.right, vars)
    elif root.val == '|':
        return evaluate(root.left, vars) or evaluate(root.right, vars)
    else:
        return vars[root.val]

这个函数的实现也利用了递归的思想，对于一个非操作符的节点，我们根据节点的值和变量真值字典来计算节点的值；对于一个非操作符的节点，我们递归计算其右子树的值，并对其取反；对于一个与或操作符的节点，我们递归计算其左右子树的值，并进行相应的逻辑运算。

完整的实现代码如下：