问题 G: 真值表(Ⅱ) 时间限制: 1 Sec 内存限制: 128 MB 提交: 4903 解决: 785 [状态] [提交] [命题人:cyh] 题目描述 第二阶段的任务是给定一个逻辑表达式，生成真值表。 输入 同子任务一。 输出 对于每一个逻辑表达式，输出其对应的真值表即可。相对于任务一，输出的最右边增加了一列，包含了表达式和它的各个值。具体见样例。 样例输入 Copy p p->q p||q 样例输出 Copy p p 1 1 0 0 p q p->q 1 1 1 1 0 0 0 1 1 0 0 1 p q p||q 1 1 1 1 0 1 0 1 1 0 0 0

以下是 Python3 的解法：

# 定义逻辑运算函数
def and_op(a, b):
    return a and b

def or_op(a, b):
    return a or b

def not_op(a):
    return not a

# 定义递归求解函数
def eval(node, values):
    if node.is_leaf():
        return values[node.data]
    else:
        left_value = eval(node.left, values)
        right_value = eval(node.right, values)
        op = node.data
        if op == '&':
            return and_op(left_value, right_value)
        elif op == '|':
            return or_op(left_value, right_value)
        elif op == '~':
            return not_op(left_value)
        else:
            raise ValueError('Invalid operator: {}'.format(op))

# 定义表达式解析函数
def parse_expr(expr):
    tokens = expr.split()
    stack = []
    for token in tokens:
        if token in {'&', '|', '~'}:
            right = stack.pop()
            left = stack.pop()
            node = Node(token, left, right)
            stack.append(node)
        else:
            node = Node(token)
            stack.append(node)
    return stack.pop()

# 定义主函数
if __name__ == '__main__':
    while True:
        try:
            expr = input()
        except:
            break
        # 解析表达式
        root = parse_expr(expr)
        # 输出表头
        var_names = sorted(root.get_vars())
        print(' '.join(var_names + [expr]))
        # 枚举所有可能的变量取值，并输出真值表
        for i in range(2 ** len(var_names)):
            values = {}
            for j, name in enumerate(var_names):
                values[name] = bool((i >> j) & 1)
            row = [str(int(values[name])) for name in var_names]
            row.append(str(int(eval(root, values))))
            print(' '.join(row))

其中，`Node` 类是用来表示逻辑表达式的节点的，具体实现可以参考以下代码：

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def is_leaf(self):
        return self.left is None and self.right is None

    def get_vars(self):
        if self.is_leaf():
            return {self.data}
        else:
            return self.left.get_vars() | self.right.get_vars()

在主函数中，先使用 `parse_expr` 函数解析输入的逻辑表达式，然后输出表头，再枚举所有可能的变量取值，计算表达式的值，并输出每一行的真值表。