基于二叉树（DSA）的Python逻辑表达式：实现真值表生成算法

要实现输入字符串逻辑表达式生成对应真值表的功能，可按以下核心步骤完成：

1. 提取命题变量 #

从输入表达式中识别所有独立的命题变量（如示例中的A、B、R、D），排除运算符、括号等符号。可通过正则匹配大写字母实现。

2. 生成所有真值组合 #

n个变量共有2ⁿ种真值组合，通过二进制计数的方式遍历生成从全False到全True的所有组合。

3. 处理逻辑表达式计算 #

优先级与运算符转换 #

逻辑运算符的优先级从高到低为：() > NOT > AND > OR > =>（蕴含）。其中蕴含运算P=>Q等价于¬P∨Q，需做转换处理。

中缀转后缀表达式 #

为正确处理运算优先级，先将输入的中缀表达式转换为后缀表达式（逆波兰表达式），再基于栈结构计算结果。

4. 生成并输出真值表 #

遍历每一组真值组合，代入表达式计算结果，最终整理成表头+行数据的表格格式。

示例实现（Python） #

import re

def extract_variables(expr):
    # 提取所有大写字母作为变量并去重排序
    return sorted(list(set(re.findall(r'[A-Z]', expr))))

def generate_truth_combinations(variables):
    n = len(variables)
    combinations = []
    # 遍历2^n种真值组合
    for i in range(2**n):
        # 将数字转为二进制字符串，补前导零至n位
        bits = bin(i)[2:].zfill(n)
        # 生成变量与真值的映射字典
        combo = {var: bool(int(bit)) for var, bit in zip(variables, bits)}
        combinations.append(combo)
    return combinations

def infix_to_postfix(expr):
    # 定义运算符优先级
    precedence = {'NOT': 3, 'AND': 2, 'OR': 1, '=>': 0}
    output = []
    stack = []
    # 拆分表达式为token：变量、运算符、括号
    tokens = re.findall(r'[A-Z]+|=>|AND|OR|NOT|\(|\)', expr)
    
    for token in tokens:
        if token in precedence:
            # 栈顶运算符优先级更高则弹出至输出
            while stack and stack[-1] != '(' and precedence[stack[-1]] >= precedence[token]:
                output.append(stack.pop())
            stack.append(token)
        elif token == '(':
            stack.append(token)
        elif token == ')':
            # 弹出括号内所有运算符
            while stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()  # 弹出左括号
        else:
            # 变量直接加入输出
            output.append(token)
    # 弹出栈中剩余运算符
    while stack:
        output.append(stack.pop())
    return output

def evaluate_postfix(postfix, values):
    stack = []
    for token in postfix:
        if token == 'AND':
            b = stack.pop()
            a = stack.pop()
            stack.append(a and b)
        elif token == 'OR':
            b = stack.pop()
            a = stack.pop()
            stack.append(a or b)
        elif token == 'NOT':
            a = stack.pop()
            stack.append(not a)
        elif token == '=>':
            b = stack.pop()
            a = stack.pop()
            # 蕴含运算转换为NOT a OR b
            stack.append(not a or b)
        else:
            # 变量取值加入栈
            stack.append(values[token])
    return stack[0]

def generate_truth_table(expr):
    variables = extract_variables(expr)
    combinations = generate_truth_combinations(variables)
    
    # 打印表头
    header = variables + ['Result']
    print('\t'.join(header))
    print('-' * len('\t'.join(header)))
    
    # 打印每一行真值与结果
    for combo in combinations:
        postfix = infix_to_postfix(expr)
        result = evaluate_postfix(postfix, combo)
        row = [str(combo[var]) for var in variables] + [str(result)]
        print('\t'.join(row))

# 测试示例输入
generate_truth_table("(A AND B)=>R OR D")

输出说明 #

运行上述代码后，会输出包含所有变量真值组合及对应表达式结果的表格，格式与标准真值表一致。

内容的提问来源于stack exchange，提问作者Djamel Tayeb