重言式判别：递归下降解析与真值表枚举的课程设计实现

简介这份资源是面向计算机科学与技术专业学生的数据结构与算法课程设计报告主题为重言式判别适合正在完成课程设计或需要理解逻辑表达式求值算法的学习者参考。报告围绕编写程序判别逻辑表达式属于重言式、矛盾式还是可满足式展开完整覆盖输入处理、运算符优先级、堆栈求值及二叉树构造等核心环节。压缩包内仅含1个doc文档大小约293KB内容为合肥学院计算机科学与技术系20162017学年第1学期的课程设计报告包含问题描述、基本要求、测试数据、问题分析、数据结构选择与概要设计等章节。文档详细阐述了算符优先关系表的归纳、双堆栈实现表达式求值、中序遍历二叉树计算逻辑值以及通过真值表判定重言式的方法并给出多组测试用例。已有147人学习适合需要完整课程设计框架、算法推导过程与实现思路的读者参考借鉴。1. 重言式判别到底在判什么从一份课程设计报告说起一份数据结构与算法课程设计报告题目落在“重言式判别”上很多人第一反应是打开编译器写个if (a || !a) return true;就交差。真按这个思路做报告大概率会被打回来因为重言式判别要解决的不是“这一个式子成不成立”而是“任意给定一个命题公式能不能用程序机械地判定它是否恒真”。它背后是命题逻辑、表达式解析、真值表枚举和递归下降这几件事的组合是数据结构课设里少有的、能把栈、树、递归、哈希表全串一遍的题目。它适合两类人一类是正在做课程设计、需要一份能跑通又能讲清楚原理的完整方案的学生另一类是想拿它当练手项目、把“字符串解析 递归 状态枚举”这套组合拳打熟的人。下面我按自己带课设时最常用的一条路径从文法定义讲到可复现的代码再到参数怎么设、哪里最容易翻车一层层拆开。读完你应该能独立写出一个支持与、或、非、蕴含、括号和变量的判别器并且知道它在什么规模下会崩。2. 从公式字符串到语法树递归下降解析器的落地写法重言式判别的第一步永远不是判而是解析。你拿到的是(P-Q)(!P|Q)这样的字符串程序得先把它变成一棵能遍历的语法树否则后面枚举真值表时你连变量都找不全。这一章把文法、词法、递归下降三件事按可抄作业的粒度写清楚。2.1 先定文法再写代码顺序不能反命题公式的文法用扩展巴科斯范式写出来优先级从低到高是蕴含-最低其次是或|再是与最高是非!括号改变结合顺序。写成产生式就是Expr - Impl Impl - Or (- Impl)? // 右结合 Or - And (| And)* And - Not ( Not)* Not - ! Not | Atom Atom - Var | ( Expr ) Var - [A-Za-z][A-Za-z0-9_]*这里有个容易被忽略的点蕴含写成(- Impl)?而不是循环是因为P-Q-R在逻辑上通常按右结合理解即P-(Q-R)。如果你写成左结合(P-Q)-R和P-(Q-R)的真值表不一样判重言式的结论就会错。我见过不止一份课设报告栽在这个细节上代码能跑结果全错。提示变量名建议限制成单字母或短标识符真值表枚举是 2 的 n 次方变量一多直接爆炸后面第 5 章会讲这个边界。2.2 词法分析把字符流切成 token解析之前先把字符串扫一遍切成 token 序列顺便把空白字符丢掉。这一步用 Python 写最省事因为字符串处理是它的强项。# 词法分析把公式字符串切成 token 列表 # 支持的 token 类型VAR(变量)、AND、OR、NOT、IMP(蕴含)、LPAREN、RPAREN def tokenize(s): tokens [] i 0 while i len(s): c s[i] if c.isspace(): i 1 continue if c - and i 1 len(s) and s[i1] : tokens.append((IMP, -)) i 2 continue if c : tokens.append((AND, )); i 1; continue if c |: tokens.append((OR, |)); i 1; continue if c !: tokens.append((NOT, !)); i 1; continue if c (: tokens.append((LPAREN, ()); i 1; continue if c ): tokens.append((RPAREN, ))); i 1; continue if c.isalpha(): j i while j len(s) and (s[j].isalnum() or s[j] _): j 1 tokens.append((VAR, s[i:j])) i j continue raise ValueError(f非法字符 {c} 出现在位置 {i}) return tokens逻辑说明-必须优先于单字符-判断否则会被拆成两个 token。变量用isalpha()起头、isalnum()续接保证P1、Q_2这类名字能识别。遇到不认识的字符直接抛异常并带上位置排错时能省很多时间。参数说明这段代码没有可调参数但 token 类型是后续解析器的契约改这里必须同步改解析器里的match判断否则会出现“词法过了、语法报错”的玄学问题。2.3 递归下降建树每个非终结符对应一个函数有了 token 序列按文法一层层往下写函数就行。每个函数负责吃掉自己那一层的 token返回一个节点。# 语法树节点用元组表示(类型, 左子, 右子) 或 (VAR, 名字) class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] if self.pos len(self.tokens) else (None, None) def eat(self, kind): t self.peek() if t[0] ! kind: raise SyntaxError(f期望 {kind}实际 {t[0]} 在位置 {self.pos}) self.pos 1 return t def parse(self): node self.expr() if self.pos ! len(self.tokens): raise SyntaxError(公式末尾有多余 token) return node def expr(self): return self.impl() def impl(self): left self.or_expr() if self.peek()[0] IMP: self.eat(IMP) right self.impl() # 右结合递归调用自己 return (IMP, left, right) return left def or_expr(self): node self.and_expr() while self.peek()[0] OR: self.eat(OR) node (OR, node, self.and_expr()) return node def and_expr(self): node self.not_expr() while self.peek()[0] AND: self.eat(AND) node (AND, node, self.not_expr()) return node def not_expr(self): if self.peek()[0] NOT: self.eat(NOT) return (NOT, self.not_expr()) return self.atom() def atom(self): t self.peek() if t[0] VAR: self.eat(VAR) return (VAR, t[1]) if t[0] LPAREN: self.eat(LPAREN) node self.expr() self.eat(RPAREN) return node raise SyntaxError(f意外的 token {t[0]})逻辑说明impl里递归调用self.impl()实现右结合这是和or_expr、and_expr用while循环的关键区别。not_expr递归调用自己支持!!P这种多重否定。atom处理变量和括号括号内重新回到expr形成闭环。参数说明self.pos是唯一的游标状态所有eat都推进它。如果你要加新的运算符比如异或^在文法里插一层、在tokenize里加分支、在解析器里加对应函数三处必须同步漏一处就会在某个输入上抛SyntaxError。2.4 收集变量并去重为真值表枚举做准备树建好之后遍历一遍把所有VAR节点收集起来去重后排序得到变量列表。这个列表的长度直接决定后面枚举的规模。# 后序遍历收集变量用集合去重后排序保证每次运行顺序一致 def collect_vars(node, accNone): if acc is None: acc set() if node[0] VAR: acc.add(node[1]) elif node[0] NOT: collect_vars(node[1], acc) else: collect_vars(node[1], acc) collect_vars(node[2], acc) return sorted(acc)逻辑说明用集合去重最后sorted保证变量顺序稳定这样生成的真值表行序可复现方便对照和写报告。NOT只有一个子节点要单独分支否则访问node[2]会越界。参数说明acc默认None再初始化避免可变默认参数的坑。变量数量就是len(collect_vars(tree))这个值超过 20 时2 的 20 次方是一百多万行纯 Python 枚举会明显变慢第 5 章会给优化方向。3. 真值表枚举与递归求值把“恒真”判出来解析只是把公式变成了结构真正判重言式靠的是枚举所有变量赋值组合逐行求值看是否每一行都为真。这一章把枚举、求值、判定三件事写透并给出可复现的完整调用链。3.1 用位运算枚举所有赋值组合n 个变量有 2 的 n 次方种赋值。用整数mask从 0 到2**n - 1遍历第 i 位表示第 i 个变量的真假这是最省内存的写法。# 枚举所有赋值mask 的第 i 位对应 vars[i] 的真值 def all_assignments(variables): n len(variables) for mask in range(1 n): env {} for i, name in enumerate(variables): env[name] bool((mask i) 1) yield env逻辑说明1 n就是 2 的 n 次方。(mask i) 1取出第 i 位转成布尔值塞进env字典。用生成器yield而不是一次性建列表变量多的时候内存占用是常数级。参数说明variables必须是去重排序后的列表顺序决定位和变量的对应关系。如果你中途改了变量顺序之前缓存的真值表就全废了所以这个列表一旦生成就不要动。3.2 递归求值遇到变量查环境遇到运算符算子树求值函数按节点类型分派变量查envNOT取反AND、OR、IMP各自按真值表算。蕴含P-Q等价于!P | Q这是最不容易记错的一种写法。# 递归求值env 是 {变量名: bool} 的字典 def evaluate(node, env): op node[0] if op VAR: return env[node[1]] if op NOT: return not evaluate(node[1], env) if op AND: return evaluate(node[1], env) and evaluate(node[2], env) if op OR: return evaluate(node[1], env) or evaluate(node[2], env) if op IMP: # P - Q 等价于 !P or Q return (not evaluate(node[1], env)) or evaluate(node[2], env) raise ValueError(f未知节点类型 {op})逻辑说明IMP用!P or Q实现比写if P then Q else True更简洁也不容易在边界上写错。递归深度等于树高正常公式不会超过几十层Python 默认递归限制够用。参数说明env必须包含树里出现的所有变量缺一个就KeyError。如果你要做部分赋值下的求值比如化简时得先判断变量是否在env里不在就抛一个明确的异常而不是让它静默出错。3.3 判定主流程一行假就短路把所有赋值跑一遍只要有一行使公式为假它就不是重言式可以直接返回并给出反例。全为真才是重言式。# 主判定返回 (是否重言式, 反例赋值或 None) def is_tautology(formula_str): tokens tokenize(formula_str) tree Parser(tokens).parse() variables collect_vars(tree) for env in all_assignments(variables): if not evaluate(tree, env): return False, env # 找到反例短路返回 return True, None # 调用示例 if __name__ __main__: print(is_tautology(P | !P)) # (True, None) print(is_tautology(P - Q)) # (False, {P: True, Q: False}) print(is_tautology((P - Q) (Q - R) - (P - R))) # (True, None)逻辑说明短路返回反例是实用设计报告里能直接展示“为什么它不是重言式”比只输出一个False有说服力。第三个例子是假言三段论经典重言式适合当自测用例。参数说明is_tautology的输入是原始字符串内部完成解析到判定的全流程。如果你要批量判多个公式把解析结果缓存起来避免重复解析同一棵树。3.4 用等价变换做交叉验证真值表枚举是“笨办法”但笨办法最适合当基准。你可以再写一个基于等价变换的判定把公式化成合取范式看是否每个子句都含互补文字。两种方法结果一致才说明实现没大问题。验证方法思路适用规模实现难度真值表枚举枚举 2^n 种赋值逐行求值n ≤ 20低等价变换化范式后检查子句n 较大但结构简单中随机对拍两法跑同一批公式比对任意低注意等价变换实现起来比枚举复杂得多课设里如果时间紧优先把枚举法写扎实再用它给等价变换法做对拍而不是反过来。4. 避坑与排查重言式判别最容易翻车的 5 个地方这一章按“现象 → 原因 → 解决”写都是我见过或自己踩过的真实问题。每一条都对应前面某段代码出问题时先往这里对。4.1 现象P-Q-R判出来和手算不一致原因蕴含的结合性写成了左结合。(P-Q)-R和P-(Q-R)真值表不同前者在P假时整体为真后者在R假时整体为假。解决解析器里impl必须递归调用自己实现右结合不能像or_expr那样用while循环。改完用P-Q-R和P-(Q-R)对拍两者结果应完全一致。4.2 现象变量名P1被拆成P和1解析报错原因词法分析里变量只吃了首字母续接字符判断漏了数字或下划线。解决变量扫描用while j len(s) and (s[j].isalnum() or s[j] _)保证P1、Q_2整体识别。改完补一个P1 !P1的用例应判为重言式。4.3 现象公式里多一个右括号程序不报错但结果乱原因atom里eat(RPAREN)之后没有检查是否还有多余 tokenparse末尾的检查被绕过。解决parse里解析完expr后必须确认self.pos len(self.tokens)否则抛“末尾有多余 token”。补用例(P|Q))应明确报语法错误而不是给个莫名其妙的结果。4.4 现象变量一多程序卡死风扇狂转原因真值表枚举是 2 的 n 次方n25 时是三千万行纯 Python 每行还要递归求值时间直接爆炸。解决先看变量数超过 20 就在报告里说明“枚举法不适用”改用等价变换或加剪枝。实际课设公式变量一般不超过 5 个但你要知道边界在哪答辩时被问到能答上来。4.5 现象!和优先级搞反!P Q算成了!(P Q)原因文法里Not层写在And层下面但解析器里and_expr直接调了atom而不是not_expr。解决and_expr必须调not_exprnot_expr再调atom。用!P Q在P真, Q假时验证正确结果是假 假 假如果算成!(真 假) 真就是优先级错了。5. 进阶技巧把判别器做成能讲清楚、能扩展的版本课设报告写到能跑通只是及格线真正拉开差距的是你能不能把边界讲清楚、把扩展方向留出来。这一章给三个具体技巧都是我在带课设时反复用到的。第一个技巧是加一个“反例解释器”。现在is_tautology返回反例字典但报告里光有字典不够直观。你可以再写一个函数把反例字典代回原公式逐步展示求值过程输出类似PTrue, QFalse 时P-Q 为 False。这个功能实现起来就是给evaluate加一个可选的 trace 参数记录每层子树的中间结果。答辩时演示这个比干讲真值表有说服力得多。第二个技巧是支持变量别名和公式化简。很多课设题目会给P、Q、R这种短名但实际用的时候可能想写Rain、Traffic。你可以在tokenize之后加一层映射把长变量名映射成内部短名判定完再映射回去。化简则是另一个方向如果公式里某个变量只出现一次且不影响结果可以标记出来报告里写“该变量为冗余变量”这是加分项。第三个技巧是给判定器加一个规模预警。在is_tautology开头算一下变量数超过阈值就打印一行提示比如“变量数 22枚举规模约 419 万行预计耗时较长”。这个提示不改变结果但能让使用者心里有数也体现你对复杂度的理解。阈值设多少合适我一般设 20因为 2 的 20 次方是一百多万纯 Python 跑几秒还能接受再往上就明显卡了。扩展方向改动位置预计工作量报告加分点反例解释器evaluate加 trace半天演示效果好变量别名映射tokenize后加一层两小时体现实用性规模预警is_tautology开头半小时体现复杂度意识等价变换对拍新增模块一天验证严谨性最后说个我自己的习惯每写完一个判定函数先拿三个公式自测——P | !P应真、P !P应假、(P-Q) (Q-R) - (P-R)应真。这三个覆盖了重言式、矛盾式和经典推理式跑通它们基本逻辑就不会有大问题。剩下的时间花在把反例输出做得清楚、把边界写进报告比堆功能更值。希望帮到你。本文还有配套的精品资源点击获取