题目说明： 构造合式公式的真值表 时间限制：1 内存限制：256 问题描述：给出任意变元（不超过4个变元，如：P,Q,S,R）的合式公式。构造该合式公式的 真值表。 输入说明：需要用特定的字符串将联结词表示（如~可以表示非，->表示蕴涵， <->表示等价，\/表示析取，/\表示合取，中间不加任何空格），输入合式公式。 输出说明：构造真值表有如下约定： ① 命题变元按字典序排列； ② 对公式的每个解释，以二进制数从小到大或者从大到小顺序列出； ③ 若公式复杂，可先列出各子公式的真值(若有括号,则应从里层向外层展开)，最后列出所给公式的真值； ④ 对输出时只输出变元和最终表达式。 输入样例：~P\/Q/\R 输出样例： P Q R (~P\/Q)/\R 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 输入方式：控制台 判定规则：忽略首尾空白、忽略空行、忽略大小写、数据之间只保留一个空白。 2.测试数据 测试数据1： 输入： (~P\/Q)/\R 输出： P Q R (~P\/Q)/\R 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 测试数据2： 输入： (~P\/Q)/\(P->Q) 输出： P Q (~P\/Q)/\(P->Q) 0 0 1 0 1 1 1 0 0 1 1 1 测试数据3： 输入： (~P\/Q)/\(P<->Q) 输出： P Q (~P\/Q)/\(P<->Q) 0 0 1 0 1 0 1 0 0 1 1 1

这道题可以使用二进制数来表示变元的真值，然后遍历所有可能的真值组合，计算出整个合式公式的真值。具体实现可以使用递归和栈两种方式。 以下是使用递归的实现方式： ```python # 定义运算符的优先级 priority = {'~': 3, '/\\': 2, '\\/': 1, '->': 0, '<->': 0} # 定义运算符的操作 operator = { '~': lambda x: not x, '/\\': lambda x, y: x and y, '\\/': lambda x, y: x or y, '->': lambda x, y: not x or y, '<->': lambda x, y: x == y } # 计算表达式的值 def evaluate(expr, values): if len(expr) == 1: # 单个变元 return values[expr] elif expr[0] == '(' and expr[-1] == ')': # 去掉括号 return evaluate(expr[1:-1], values) else: # 找到最后一个运算符，以它为分界点，递归计算左右两个子表达式的值 index = -1 paren_count = 0 for i in reversed(range(len(expr))): if expr[i] == ')': paren_count += 1 elif expr[i] == '(': paren_count -= 1 elif paren_count == 0 and expr[i] in priority: index = i break op = expr[index:index + 2] if expr[index:index + 2] in priority else expr[index] left_expr = expr[:index].rstrip() right_expr = expr[index + len(op):].lstrip() left_value = evaluate(left_expr, values) right_value = evaluate(right_expr, values) return operator[op](left_value, right_value) # 输出真值表 def print_truth_table(expr): vars = sorted(set(filter(str.isalpha, expr))) # 获取所有变元并按字典序排序 print(' '.join(vars), expr) for i in range(2 ** len(vars)): values = {vars[j]: bool((i >> (len(vars) - j - 1)) & 1) for j in range(len(vars))} row = [int(values[var]) for var in vars] row.append(int(evaluate(expr, values))) print(' '.join(map(str, row))) ``` 使用栈的实现方式： ```python # 计算表达式的值 def evaluate(expr, values): stack = [] for token in expr: if token.isalpha(): # 变量 stack.append(values[token]) elif token in operator: # 运算符 if token == '~': arg = stack.pop() stack.append(operator[token](arg)) else: right_arg = stack.pop() left_arg = stack.pop() stack.append(operator[token](left_arg, right_arg)) return stack[0] # 输出真值表 def print_truth_table(expr): vars = sorted(set(filter(str.isalpha, expr))) # 获取所有变元并按字典序排序 print(' '.join(vars), expr) for i in range(2 ** len(vars)): values = {vars[j]: bool((i >> (len(vars) - j - 1)) & 1) for j in range(len(vars))} row = [int(values[var]) for var in vars] row.append(int(evaluate(expr, values))) print(' '.join(map(str, row))) ``` 两种方式的使用方法相同： ```python expr = input().strip() print_truth_table(expr) ```