计算命题演算公式的真值 【问题描述】 命题演算公式是指由逻辑变量(其值 为 T RUE 或 FALSE)和逻辑运算符and、 or和N OT按照一定的规则组成的公式(隐含等运算可以用and、or)并加以表示。公式运算的顺序为:NOT、and、or，括号()可以改变优先级。给定一个命 题演算公式和每个变量的值，要求设计一个程序来计算公式的真值。 【基本要求】 (1)用二叉树计算公式的真值。 首先，使用堆栈将公式的中缀形式变为后缀形式。其次，根据后缀形式，从叶节 点构造相应的二叉树。最后，按后序遍历二叉树，求出每个子树的值。也就是说， 每次到达一个节点，它的子树的值就已经计算出来了。当到达根节点时，得到公 式的真值。 (2)设计各种不同形式的命题演算公式，并检查每个命题演算公式的有效性。 (3)逻辑论证的标识符不局限于单个字母，可以是任意长度的字母数字字符串。逻辑参 数可以在公式中出现多次。 (4)打印二叉树的构造过程，打印公式的后缀形式和二叉树的后序遍历序列。 (5)输入各变量的值，计算并显示公式的真值，打印二叉树的求值过程。 (6)显示公式的真值表。 【扩展要求】 请将逻辑运算符替换为算术运算符，使用二叉树计算算术表达式。如果用Python，请把你的解题思路和步骤写出来

解题思路：

1. 将中缀表达式转换为后缀表达式，使用堆栈实现
2. 根据后缀表达式构造二叉树
3. 后序遍历二叉树，计算每个子树的值，得到表达式的真值

步骤：

1. 定义一个堆栈，用于存储运算符和括号
2. 遍历中缀表达式，对于每个字符：
- 如果是运算符或括号，将其压入堆栈
- 如果是变量，将其加入后缀表达式
3. 遍历堆栈，将剩余的运算符弹出并加入后缀表达式
4. 根据后缀表达式构造二叉树，使用堆栈实现
- 对于每个字符：
- 如果是变量，创建一个只包含该变量的二叉树并压入堆栈
- 如果是运算符，弹出堆栈中的两棵子树，将它们作为该运算符的左右子树，创建一个新的二叉树并将其压入堆栈
5. 后序遍历二叉树，计算每个子树的值，得到表达式的真值

Python代码实现：

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

def infix_to_postfix(infix):
    operators = {'(': 0, ')': 0, 'NOT': 1, 'AND': 2, 'OR': 3}
    stack = []
    postfix = []
    for token in infix:
        if token in operators:
            if token == '(':
                stack.append(token)
            elif token == ')':
                while stack[-1] != '(':
                    postfix.append(stack.pop())
                stack.pop()
            else:
                while stack and operators[stack[-1]] >= operators[token]:
                    postfix.append(stack.pop())
                stack.append(token)
        else:
            postfix.append(token)
    while stack:
        postfix.append(stack.pop())
    return postfix

def postfix_to_tree(postfix):
    stack = []
    for token in postfix:
        if token in {'NOT', 'AND', 'OR'}:
            right = stack.pop()
            if token == 'NOT':
                stack.append(TreeNode('NOT', None, right))
            else:
                left = stack.pop()
                stack.append(TreeNode(token, left, right))
        else:
            stack.append(TreeNode(token))
    return stack.pop()

def evaluate(root, values):
    if root.val in values:
        return values[root.val]
    elif root.val == 'NOT':
        return not evaluate(root.right, values)
    elif root.val == 'AND':
        return evaluate(root.left, values) and evaluate(root.right, values)
    elif root.val == 'OR':
        return evaluate(root.left, values) or evaluate(root.right, values)

def print_tree(root, level=0):
    if root:
        print_tree(root.right, level + 1)
        print(' ' * 4 * level + '->', root.val)
        print_tree(root.left, level + 1)

infix = input('请输入命题演算公式：').split()
postfix = infix_to_postfix(infix)
root = postfix_to_tree(postfix)
print('后缀表达式：', postfix)
print('二叉树构造过程：')
print_tree(root)
print('真值表：')
variables = list(set(filter(lambda x: x not in {'NOT', 'AND', 'OR'}, infix)))
for values in itertools.product([True, False], repeat=len(variables)):
    values = dict(zip(variables, values))
    result = evaluate(root, values)
    print(values, '->', result)

示例输入：

请输入命题演算公式：A AND (B OR NOT C)

示例输出：

后缀表达式： ['A', 'B', 'C', 'NOT', 'OR', 'AND']
二叉树构造过程：
            -> AND
        -> B
            -> OR
    -> A
            -> NOT
        -> C
真值表：
{'A': True, 'B': True, 'C': True} -> True
{'A': True, 'B': True, 'C': False} -> True
{'A': True, 'B': False, 'C': True} -> True
{'A': True, 'B': False, 'C': False} -> False
{'A': False, 'B': True, 'C': True} -> False
{'A': False, 'B': True, 'C': False} -> False
{'A': False, 'B': False, 'C': True} -> False
{'A': False, 'B': False, 'C': False} -> False