简介这份课程设计资料包围绕重言式判别程序的实现展开面向学习数据结构与算法、需要完成逻辑表达式课程设计的本科生及自学者。内容以二叉树表示布尔表达式结合前序、中序、后序遍历与栈的后进先出特性讨论逻辑运算符处理、重言式判定及用户交互界面设计并强调项目文档的完整性。压缩包共4个文件以2个C源程序和2个Word文档为主前者承载核心算法与代码实现后者用于课程设计说明、设计思路与测试记录整体约38KB体量轻便便于查阅。该资料已有383人学习适合作为课程设计参考、算法复盘或二叉树与栈综合练习的辅助材料。读者可从中了解表达式树构建、后序遍历求值、栈辅助计算以及文档撰写的基本框架并据此梳理重言式判别的实现路径与测试思路。1. 重言式判别程序课程设计先别急着上真值表三个边界先想清楚做重言式判别程序课程设计很多人第一反应是写个三重循环把真值表打出来真到验收时变量一多、括号一嵌套、非运算符一出现程序就开始胡言乱语。这个资源围绕数据结构课程设计里的重言式程序实现给出一套可复现的解析、求值、判定和文档资料先把命题逻辑表达式拆成 token再建抽象语法树最后用真值枚举或等价变换判断是否在所有赋值下为真。适合正在交课程设计、需要源码对照和测试用例的人也适合想把表达式解析补进工具箱的开发者。它不解决“无限变量”的幻想变量规模、运算符优先级、非法输入这些边界会在文档里写清楚。2. 表达式解析与抽象语法树数据结构课程设计里最容易低估的四步重言式判别程序看起来是逻辑题落到代码里第一关其实是表达式解析。课程设计里常见做法是用栈把中缀表达式转成后缀再求值这条路能跑但调试成本高一旦优先级或括号出错错误会藏到求值阶段才爆出来。我一般更愿意用递归下降先建一棵抽象语法树把“字符流”变成“可打印、可遍历、可复用的数据结构”后面判重言式、输出反例、做等价变换都围绕这棵树展开。选递归下降的理由很直接每个函数只负责一个优先级层级出错时能快速定位是词法没拆对还是某个层级少消费了一个 tokenAST 还能直接打印出来对照手算结果比盯一长串后缀 token 舒服得多。2.1 词法扫描把A!B拆成 token 流词法扫描先解决“什么是一个符号”。命题逻辑表达式里常见的符号有!、、|、、、(、)变量名可能是单字母也可能是多字母。课程设计文档资料里必须先固定一套词法规则变量名是否区分大小写、是否允许多字母、空白字符怎么处理、遇到非法字符报什么错。常见翻车点是词法阶段只读单字符结果AB被拆成A和B后面判定结果和手算对不上。下面的写法把连续字母当成一个变量名同时保留运算符的二元组结构方便解析器按类型消费。# 词法扫描把表达式拆成 token 列表 def tokenize(expr: str): tokens [] i 0 while i len(expr): ch expr[i] if ch.isspace(): i 1 continue if ch in ()!|^: # 支持 ! | ^ 六种符号其中 表示等价 表示蕴含 tokens.append((ch, ch)) i 1 elif ch.isalpha(): j i while j len(expr) and expr[j].isalpha(): j 1 name expr[i:j] tokens.append((VAR, name)) i j else: raise ValueError(f非法字符: {ch!r} 位置 {i}) tokens.append((EOF, )) return tokens这段代码做了三件事跳过空白、把运算符转成(类型, 值)、把连续字母收成一个变量 token。参数上expr是用户输入的原始表达式字符串返回值是 token 列表最后追加(EOF, )作为结束哨兵解析器靠它判断表达式是否读完。i是扫描指针j只用于变量名截取。边界要写进文档变量名大小写敏感^如果没定义语义就不要放进运算符集合在这里表示等价不要和赋值混淆。提示词法阶段报错要带位置否则验收时排查非法字符会变成黑匣子。2.2 递归下降建 AST优先级、结合性和括号解析阶段的核心是优先级表。课程设计里常见的优先级从低到高可以定为等价最低其次是蕴含再是或|、与、非!最高。括号单独处理遇到左括号就递归解析到右括号。结合性也要固定和|一般左结合通常右结合可以按左结合处理但必须在文档资料里写清楚。下面的解析器把每个优先级写成一个函数eq调impimp调or_or_调and_and_调not_not_处理一元非并递归到原子。这样写不是为了炫技是为了让错误定位有层次结果不对时先打印 AST看是哪个层级结合错了。from dataclasses import dataclass dataclass class Node: op: str # VAR / NOT / AND / OR / IMP / EQ left: object None right: object None name: str # 递归下降优先级从低到高为 等价 蕴含 或 与 非 class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def eat(self, kind): tok self.peek() if tok[0] ! kind: raise SyntaxError(f期望 {kind}实际 {tok}) self.pos 1 return tok def parse(self): node self.eq() self.eat(EOF) return node def eq(self): node self.imp() while self.peek()[0] : self.eat() node Node(EQ, node, self.imp()) return node def imp(self): node self.or_() if self.peek()[0] : self.eat() # 蕴含右结合递归调用 imp node Node(IMP, node, self.imp()) return node def or_(self): node self.and_() while self.peek()[0] |: self.eat(|) node Node(OR, node, self.and_()) return node def and_(self): node self.not_() while self.peek()[0] : self.eat() node Node(AND, node, self.not_()) return node def not_(self): if self.peek()[0] !: self.eat(!) return Node(NOT, rightself.not_()) return self.atom() def atom(self): tok self.peek() if tok[0] VAR: self.eat(VAR) return Node(VAR, nametok[1]) if tok[0] (: self.eat(() node self.eq() self.eat()) return node raise SyntaxError(f意外的 token: {tok})这段代码把 token 流变成 ASTParser持有 token 列表和当前指针pospeek看当前 tokeneat消费并校验类型parse从最低优先级入口最后要求读到EOF防止AB)C这种多余右括号被悄悄放过。参数上tokens是词法输出self.pos是当前解析位置Node.op用字符串区分节点类型left和right是子节点name只给变量节点用。imp里递归调用自身是为了右结合and_和or_用while是为了左结合。注意不同教材对和的优先级可能写得不一样源码和文档资料必须统一否则验收时手算和程序各说各话。2.3 变量收集与常量折叠真值表之前先减负AST 建好后不要立刻枚举真值表。先做两件小事收集变量集合做最基础的常量折叠。变量收集要深度遍历左右子树用集合去重最后排序保证每次运行的反例输出顺序一致。常量折叠不是必须但课程设计里很能体现数据结构的使用A1、A|0、!!A这类结构可以先化简减少后续求值节点数。下面的collect_vars是判定模块的前置步骤simplify只演示常量折叠入口不承担完整布尔代数化简避免代码和文档吹得太大。def collect_vars(node, bagNone): if bag is None: bag set() if node.op VAR: bag.add(node.name) if node.left: collect_vars(node.left, bag) if node.right: collect_vars(node.right, bag) return bag def simplify(node): # 只做最简单的常量折叠NOT 常量、AND/OR 的短路常量 if node.op NOT: child simplify(node.right) if child.op CONST: return Node(CONST, namestr(not (child.name True))) return Node(NOT, rightchild) if node.op in (AND, OR, IMP, EQ): left simplify(node.left) right simplify(node.right) # 完整布尔代数化简不在这里展开保留结构交给求值阶段 return Node(node.op, left, right) return nodecollect_vars用递归深度优先收集变量名bag是可变集合递归时复用避免每层新建集合。参数上node是 AST 根节点返回的集合可以直接sorted()后用于枚举。simplify里演示了NOT遇到CONST时的折叠CONST节点需要你在 AST 定义里补一个类型示例只给入口。边界要明确变量名大小写敏感多字母变量和单字母变量只能选一种规则不要在化简函数里偷偷做重言式判定否则后面测试失败时很难判断是化简错还是判定错。提示变量数超过 12 个时真值表枚举会迅速变慢先做变量去重和常量折叠再考虑更进一步的等价变换。3. 真值枚举与重言式判定变量数超过 10 个时怎么不翻车判定重言式的朴素定义很直白对所有变量赋值组合表达式都为真。代码写起来也直白收集变量、枚举2^n种赋值、逐一代入求值。真正容易翻车的地方在边界变量数一多枚举时间指数上涨表达式一深递归求值可能碰到递归深度限制程序只输出“是/否”验收时被问“为什么不是重言式”却拿不出反例。更稳的做法是把判定拆成三层求值器只负责单次赋值枚举器负责生成赋值并记录反例等价变换负责在暴力枚举之前减负。这样每一层都能单独测试出问题时不至于全盘重写。3.1 真值表枚举递归模板与位运算两种写法枚举变量赋值常见有两种写法递归生成字典或者用位掩码。递归写法可读性好适合课程设计文档资料里画调用树位掩码写法紧凑适合变量数中等时快速跑测试。下面用位掩码变量排序后第i个变量对应mask的第i位mask从 0 到2^n - 1每个mask就是一种完整赋值。求值器按节点类型递归计算IMP按not left or right展开EQ直接比较左右布尔值。返回值设计成(是否重言式, 反例环境)反例是后面调试的关键。def evaluate(node, env): op node.op if op VAR: return env[node.name] if op NOT: return not evaluate(node.right, env) if op AND: return evaluate(node.left, env) and evaluate(node.right, env) if op OR: return evaluate(node.left, env) or evaluate(node.right, env) if op IMP: return (not evaluate(node.left, env)) or evaluate(node.right, env) if op EQ: return evaluate(node.left, env) evaluate(node.right, env) raise ValueError(f未知节点: {op}) def is_tautology_bruteforce(root): variables sorted(collect_vars(root)) n len(variables) for mask in range(1 n): env {name: bool((mask i) 1) for i, name in enumerate(variables)} if not evaluate(root, env): return False, env return True, Noneevaluate是单次赋值下的递归求值器参数node是 AST 节点env是变量到布尔值的字典遇到未知节点直接抛错避免静默返回None把错误带到判定层。is_tautology_bruteforce先排序变量保证mask和变量顺序稳定1 n是2^nmask i 1取第i位一旦发现某个赋值下为假立刻返回False和反例环境不继续跑完剩余组合。边界n0时range(1)仍然会跑一次适合判断常量表达式Python 递归深度默认有限表达式嵌套很深时要改迭代求值或调整限制变量名重复不会影响集合但排序后顺序固定反例输出可复现。3.2 短路求值与反例输出别让程序只给“是/否”课程设计验收时老师经常随手给一个不是重言式的表达式问“你程序说不是那哪个赋值让它假”。如果程序只打印False这个环节就很被动。反例输出不需要复杂 UI把变量名和布尔值按字典序拼成一行就够用。format_env接收env或NoneNone表示所有赋值都为真有反例时输出AFalse, BTrue这种形式。这个函数很小但它把“判定结果”变成了“可验证的证据”调试时也能直接拿反例去手算 AST 的每个节点。def format_env(env): if env is None: return 无所有赋值均为真 return , .join(f{k}{v} for k, v in sorted(env.items())) # 使用示例先解析再判定最后打印反例 root Parser(tokenize((AB)AB)).parse() ok, bad is_tautology_bruteforce(root) print(ok, format_env(bad))这段代码做了两件事format_env把反例环境排序后转成可读字符串ok和bad分别承接判定结果和反例。参数上env是is_tautology_bruteforce返回的字典或Nonesorted(env.items())保证输出稳定。注意示例表达式里的括号和优先级(AB)AB按前面的优先级会解析成((AB)A)B如果你想要的是((AB)A)B这个例子可以如果想要(AB)(AB)必须补括号。很多翻车不是算法错是测试表达式自己写得有歧义。3.3 剪枝与等价变换什么时候该放弃暴力枚举暴力枚举适合变量数小、表达式短的课程设计演示但文档资料里要写清楚适用范围。变量数到 12 个时4096种赋值还能接受到 20 个就是一百万级别Python 里会明显变慢。减负的第一步是等价变换把蕴含AB换成!A|B把等价AB换成(AB)(BA)这样 AST 里只剩NOT、AND、OR和变量后续转否定范式或 CNF 都方便。下面的eliminate_imp_eq只做蕴含和等价消除返回新树不修改原树方便对比变换前后的结构。def eliminate_imp_eq(node): if node.op VAR: return node if node.op NOT: return Node(NOT, righteliminate_imp_eq(node.right)) left eliminate_imp_eq(node.left) right eliminate_imp_eq(node.right) if node.op IMP: # A B 等价于 !A | B return Node(OR, Node(NOT, rightleft), right) if node.op EQ: # A B 等价于 (A B) (B A) return Node(AND, Node(OR, Node(NOT, rightleft), right), Node(OR, Node(NOT, rightright), left)) return Node(node.op, left, right)eliminate_imp_eq按节点类型递归变量原样返回NOT继续处理子节点IMP展开成OR(NOT(left), right)EQ展开成两个蕴含再合并。参数node是 AST 根返回值是新树原树保留方便在测试里对比“变换前求值”和“变换后求值”是否一致。边界EQ展开会让节点数明显增加大表达式要先做结构共享或哈希缓存这里没有做德摩根律NOT里面还可能包着AND/OR后续转 NNF 要补。提示变量数超过 12 个、表达式节点数超过几百时先做常量折叠和蕴含/等价消除再决定是否继续暴力枚举不要在课程设计文档里写“支持任意变量数”那是给自己挖坑。4. 课程设计文档与模块接口把文档资料写成能验收的六张表课程设计最冤的翻车不是代码跑不通而是代码能跑、文档资料对不上接口表写的输入是字符串代码实际收 token 列表测试用例表只写“测试成功”没有预期输出报告里画了模块图源码里却找不到对应函数。验收老师一般不会逐行读代码但会顺着文档找证据这个模块输入什么、输出什么、异常怎么处理、测试覆盖了哪些边界。把文档资料写成表格比写大段说明更稳因为表格逼着你把每个字段填实。下面按模块接口、测试用例、报告结构三块拆表格里的内容可以直接照着改不用硬凑代码块。4.1 模块拆分解析、求值、判定、UI 四层接口模块拆分不要按“文件”拆要按“职责”拆。解析层负责字符串到 AST求值层负责 AST 加环境到布尔值判定层负责枚举和反例UI 或命令行层负责输入输出。每层只暴露一个主函数异常在层内转成可读信息。这样文档资料里的接口表就能和源码函数一一对应。下面这张表是课程设计里最该先填的填完再写代码能少返工。模块主函数输入输出异常/边界测试点词法tokenize(expr)原始表达式字符串token 列表末尾EOF非法字符、空串空白、多字母变量、非法符号解析Parser(tokens).parse()token 列表AST 根节点括号不匹配、多余 token优先级、结合性、括号嵌套求值evaluate(node, env)AST、变量环境布尔值未知节点、缺变量单变量、嵌套非、蕴含判定is_tautology_bruteforce(root)AST(bool, env或None)变量过多、递归过深重言式、矛盾式、可满足式输出format_env(env)环境或None可读字符串None表示全真反例排序、空环境表格填完后文档里还要补一句“层与层之间只通过返回值传递不共享全局变量”。课程设计里常见做法是全局变量存 token 列表短期省事后面加测试用例时互相污染。参数说明要落到字段expr不能为Nonetokens必须含EOFenv的键必须覆盖 AST 里所有变量缺变量应该在求值前报错而不是让KeyError随机冒出来。注意接口表里的函数名要和源码一致别文档写parse_expr代码里叫parse验收时很难解释。4.2 测试用例表重言式、矛盾式、可满足式各给三条测试用例不要只写“A|!A是重言式”。要按类别覆盖重言式、矛盾式、可满足但非重言式、非法输入、优先级边界、多字母变量。每条用例写清表达式、期望结果、覆盖点最好再写一个反例或说明。下面这张表可以直接放进文档资料代码里的单元测试按编号对应。表达式里的变量尽量用A、B、C多字母变量单独一组避免和单字母规则混淆。编号表达式期望覆盖点T01A!A重言式T02(AB)(BA)重言式T03(AB)(BA)重言式等价对称性T04A!A矛盾式矛盾式判定反例全假T05AB可满足非重言反例ATrue,BFalseT06ABC可满足非重言T07!!AA重言式连续非、等价T08(AB)(!A!B)T09A语法错误缺右操作数T10A$B词法错误非法字符定位这张表的关键不是数量是每类都有。T04 用来验证程序不是“全返回真”T05 用来验证反例输出T06 用来抓优先级翻车T09 和 T10 用来验证异常路径。文档资料里要给每条用例写“实际输出”栏验收前手动跑一遍填进去不要留空。参数上期望结果只有三类重言式、矛盾式、可满足非重言式如果程序只输出布尔值矛盾式和可满足非重言式都返回False文档里要额外用反例区分。提示测试用例表里不要写“测试通过”四个字就结束至少写清反例或错误信息否则后面排查没有证据。4.3 报告结构问题描述到测试记录的顺序课程设计报告不要按“想到哪写到哪”组织。比较稳的顺序是问题描述、需求分析、数据结构设计、算法流程、模块接口、测试记录、边界与不足。问题描述里写清楚“重言式”的定义和输入表达式文法需求分析里写变量规模上限和异常处理要求数据结构设计放 AST 节点定义和 token 结构算法流程放递归下降和真值枚举模块接口放 4.1 的表测试记录放 4.2 的表和实际输出边界与不足里老实写“变量数超过 12 个时暴力枚举变慢当前版本用等价变换减负未实现 SAT 求解器”。这样写不丢人反而显得知道边界。报告章节写什么验收点问题描述重言式定义、输入输出约定文法是否明确需求分析变量规模、异常类型、运行方式边界是否写清数据结构token、AST 节点、变量集合字段和源码是否一致算法流程词法、递归下降、枚举、反例优先级和结合性模块接口函数签名、参数、返回值能否对应源码测试记录用例表、实际输出、反例是否覆盖异常边界与不足变量上限、未实现功能是否诚实报告里的图和表要能回指源码。比如 AST 节点表里写op取值VAR/NOT/AND/OR/IMP/EQ源码里就不能多一个没解释的XOR算法流程写“右结合”测试用例里就要有连续蕴含的用例。文档资料不是装饰它是验收时老师顺着查的路线图。注意报告里不要贴大段没有注释的代码关键函数贴签名和注释即可完整源码放配套文件里正文解释参数和边界。5. 避坑与排查重言式程序实现里最常见的 5 个翻车点重言式程序实现的代码量不大翻车点却很集中优先级、变量收集、反例输出、递归深度、文档和代码不一致。下面 5 条是课程设计验收里最容易碰到的每条按“现象 → 原因 → 解决”写。排查顺序建议固定成先跑词法确认 token 流再打印 AST确认结构再跑单变量用例确认求值最后跑多变量和异常用例。这个顺序能把问题锁在小范围内不至于一上来就怀疑算法。5.1 解析阶段的三个坑现象表达式A|BC的判定结果和手算不一致手算是A|(BC)程序却像按(A|B)C算。原因递归下降的优先级层级写反了or_里先调了and_才对但如果and_里又回头调or_或者parse入口从and_开始就会把或和与的优先级颠倒。解决固定优先级从低到高为等价、蕴含、或、与、非入口从最低的eq开始在文档资料里写一张优先级表测试用例加A|BC和A(B|C)对照。血泪经验是优先级错误不会在解析时报错只会在判定时给出一个看起来很合理的结果所以必须靠用例表抓。现象连续非!!A报语法错误或者程序卡住。原因not_函数只处理一层!消费后直接调atom第二个!落到atom里没有匹配分支另一种写法是not_里用if而不是while连续非只吃一个。解决not_在遇到!后递归调用自身而不是直接调atom测试用例加!A、!!A、!!!A并在 AST 打印里确认NOT嵌套层数。注意连续非在布尔值上会抵消但 AST 结构必须保留否则文档里说的“一元非节点”就对不上。现象多字母变量AB被拆成A和B判定结果和预期完全不同。原因词法扫描按单字符读变量或者文档里写“变量为单字母”代码却允许连续字母规则不统一。解决二选一。要么词法把连续字母收成一个变量名文档里写“变量名由字母组成区分大小写”要么词法只读单字符遇到连续字母报错文档里写“变量仅限单字母”。不要代码支持多字母、文档写单字母验收时老师输入AB就会出问题。测试用例要单独加多字母组比如AA|!AA确认变量集合里只有一个AA。5.2 判定与文档的两个坑现象程序判定某个表达式是重言式验收时老师随手给一个赋值却是假。原因变量收集漏了右子树或者收集时用了局部集合但没有合并导致枚举的变量集合少了变量求值时缺失变量被默认成False于是某些赋值根本没被枚举到。解决collect_vars必须同时遍历left和right递归返回同一个集合求值前检查env是否覆盖collect_vars的全部变量缺变量直接报错不要给默认值。排查时打印变量集合和枚举次数变量数n对应枚举次数应该是2^n对不上就说明收集有问题。现象变量数一多程序卡死命令行半天不返回。原因暴力枚举是2^n变量数到 20 以上时组合数爆炸如果表达式里还有重复子结构求值又在重复递归时间会更高。解决在文档里写清适用范围比如“变量数不超过 12 个时直接枚举超过时先做常量折叠和蕴含/等价消除仍超限则提示用户”代码里加变量数上限和耗时保护不要把“支持任意变量”写进报告。更进一步的 SAT 或 BDD 思路可以放在“不足与改进”里但不要假装已经实现。提示课程设计验收更看重边界诚实和测试完整吹一个跑不动的无限变量支持反而扣分。现象文档资料里的接口表和源码对不上报告写parse_expr代码里是Parser.parse测试记录写“全部通过”但实际输出栏空着。原因文档是最后补的代码改完没回填或者测试用例只跑了正常路径异常路径没记录。解决先定接口表再写代码代码改签名时同步改表测试记录必须贴实际输出至少包含一条反例和一条错误信息。排查时拿报告里的函数名去源码里搜搜不到就是不一致。注意文档里的“变量上限”“异常类型”“运行方式”要和源码常量、raise语句对得上别写一套做一套。6. 进阶验证与性能对照用随机对拍和等价变换给结果上保险判定逻辑写完后最容易犯的错是“只拿自己编的几个用例跑通就交付”。手工用例覆盖有限优先级、括号、连续非这些组合一多边缘错误很难靠肉眼发现。我一般会加一层随机对拍随机生成表达式用 AST 求值器算一遍再用另一套独立的求值方式算一遍逐赋值比较。另一套求值方式不需要多高级把表达式转成 Python 布尔表达式在受限命名空间里求值即可但只能用于测试生成串不能拿用户输入直接eval。这样做的价值是把“我觉得对”变成“两套实现互相印证”翻车概率会低很多。6.1 随机表达式对拍让两套求值器互相盯着随机生成器控制深度递归拼接变量和二元运算符括号全部显式加上避免优先级干扰对拍本身。转换函数把、|、、替换成 Python 的布尔运算AB在布尔序上等价于AB替换成。对拍循环里AST 求值用布尔字典本文还有配套的精品资源点击获取 
长河君 · 2026/10/29 11:41:37 · 阅读 1.2k 重言式判别程序课程设计：表达式解析与AST真值枚举
简介这份课程设计资料包围绕重言式判别程序的实现展开面向学习数据结构与算法、需要完成逻辑表达式课程设计的本科生及自学者。内容以二叉树表示布尔表达式结合前序、中序、后序遍历与栈的后进先出特性讨论逻辑运算符处理、重言式判定及用户交互界面设计并强调项目文档的完整性。压缩包共4个文件以2个C源程序和2个Word文档为主前者承载核心算法与代码实现后者用于课程设计说明、设计思路与测试记录整体约38KB体量轻便便于查阅。该资料已有383人学习适合作为课程设计参考、算法复盘或二叉树与栈综合练习的辅助材料。读者可从中了解表达式树构建、后序遍历求值、栈辅助计算以及文档撰写的基本框架并据此梳理重言式判别的实现路径与测试思路。1. 重言式判别程序课程设计先别急着上真值表三个边界先想清楚做重言式判别程序课程设计很多人第一反应是写个三重循环把真值表打出来真到验收时变量一多、括号一嵌套、非运算符一出现程序就开始胡言乱语。这个资源围绕数据结构课程设计里的重言式程序实现给出一套可复现的解析、求值、判定和文档资料先把命题逻辑表达式拆成 token再建抽象语法树最后用真值枚举或等价变换判断是否在所有赋值下为真。适合正在交课程设计、需要源码对照和测试用例的人也适合想把表达式解析补进工具箱的开发者。它不解决“无限变量”的幻想变量规模、运算符优先级、非法输入这些边界会在文档里写清楚。2. 表达式解析与抽象语法树数据结构课程设计里最容易低估的四步重言式判别程序看起来是逻辑题落到代码里第一关其实是表达式解析。课程设计里常见做法是用栈把中缀表达式转成后缀再求值这条路能跑但调试成本高一旦优先级或括号出错错误会藏到求值阶段才爆出来。我一般更愿意用递归下降先建一棵抽象语法树把“字符流”变成“可打印、可遍历、可复用的数据结构”后面判重言式、输出反例、做等价变换都围绕这棵树展开。选递归下降的理由很直接每个函数只负责一个优先级层级出错时能快速定位是词法没拆对还是某个层级少消费了一个 tokenAST 还能直接打印出来对照手算结果比盯一长串后缀 token 舒服得多。2.1 词法扫描把A!B拆成 token 流词法扫描先解决“什么是一个符号”。命题逻辑表达式里常见的符号有!、、|、、、(、)变量名可能是单字母也可能是多字母。课程设计文档资料里必须先固定一套词法规则变量名是否区分大小写、是否允许多字母、空白字符怎么处理、遇到非法字符报什么错。常见翻车点是词法阶段只读单字符结果AB被拆成A和B后面判定结果和手算对不上。下面的写法把连续字母当成一个变量名同时保留运算符的二元组结构方便解析器按类型消费。# 词法扫描把表达式拆成 token 列表 def tokenize(expr: str): tokens [] i 0 while i len(expr): ch expr[i] if ch.isspace(): i 1 continue if ch in ()!|^: # 支持 ! | ^ 六种符号其中 表示等价 表示蕴含 tokens.append((ch, ch)) i 1 elif ch.isalpha(): j i while j len(expr) and expr[j].isalpha(): j 1 name expr[i:j] tokens.append((VAR, name)) i j else: raise ValueError(f非法字符: {ch!r} 位置 {i}) tokens.append((EOF, )) return tokens这段代码做了三件事跳过空白、把运算符转成(类型, 值)、把连续字母收成一个变量 token。参数上expr是用户输入的原始表达式字符串返回值是 token 列表最后追加(EOF, )作为结束哨兵解析器靠它判断表达式是否读完。i是扫描指针j只用于变量名截取。边界要写进文档变量名大小写敏感^如果没定义语义就不要放进运算符集合在这里表示等价不要和赋值混淆。提示词法阶段报错要带位置否则验收时排查非法字符会变成黑匣子。2.2 递归下降建 AST优先级、结合性和括号解析阶段的核心是优先级表。课程设计里常见的优先级从低到高可以定为等价最低其次是蕴含再是或|、与、非!最高。括号单独处理遇到左括号就递归解析到右括号。结合性也要固定和|一般左结合通常右结合可以按左结合处理但必须在文档资料里写清楚。下面的解析器把每个优先级写成一个函数eq调impimp调or_or_调and_and_调not_not_处理一元非并递归到原子。这样写不是为了炫技是为了让错误定位有层次结果不对时先打印 AST看是哪个层级结合错了。from dataclasses import dataclass dataclass class Node: op: str # VAR / NOT / AND / OR / IMP / EQ left: object None right: object None name: str # 递归下降优先级从低到高为 等价 蕴含 或 与 非 class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 def peek(self): return self.tokens[self.pos] def eat(self, kind): tok self.peek() if tok[0] ! kind: raise SyntaxError(f期望 {kind}实际 {tok}) self.pos 1 return tok def parse(self): node self.eq() self.eat(EOF) return node def eq(self): node self.imp() while self.peek()[0] : self.eat() node Node(EQ, node, self.imp()) return node def imp(self): node self.or_() if self.peek()[0] : self.eat() # 蕴含右结合递归调用 imp node Node(IMP, node, self.imp()) return node def or_(self): node self.and_() while self.peek()[0] |: self.eat(|) node Node(OR, node, self.and_()) return node def and_(self): node self.not_() while self.peek()[0] : self.eat() node Node(AND, node, self.not_()) return node def not_(self): if self.peek()[0] !: self.eat(!) return Node(NOT, rightself.not_()) return self.atom() def atom(self): tok self.peek() if tok[0] VAR: self.eat(VAR) return Node(VAR, nametok[1]) if tok[0] (: self.eat(() node self.eq() self.eat()) return node raise SyntaxError(f意外的 token: {tok})这段代码把 token 流变成 ASTParser持有 token 列表和当前指针pospeek看当前 tokeneat消费并校验类型parse从最低优先级入口最后要求读到EOF防止AB)C这种多余右括号被悄悄放过。参数上tokens是词法输出self.pos是当前解析位置Node.op用字符串区分节点类型left和right是子节点name只给变量节点用。imp里递归调用自身是为了右结合and_和or_用while是为了左结合。注意不同教材对和的优先级可能写得不一样源码和文档资料必须统一否则验收时手算和程序各说各话。2.3 变量收集与常量折叠真值表之前先减负AST 建好后不要立刻枚举真值表。先做两件小事收集变量集合做最基础的常量折叠。变量收集要深度遍历左右子树用集合去重最后排序保证每次运行的反例输出顺序一致。常量折叠不是必须但课程设计里很能体现数据结构的使用A1、A|0、!!A这类结构可以先化简减少后续求值节点数。下面的collect_vars是判定模块的前置步骤simplify只演示常量折叠入口不承担完整布尔代数化简避免代码和文档吹得太大。def collect_vars(node, bagNone): if bag is None: bag set() if node.op VAR: bag.add(node.name) if node.left: collect_vars(node.left, bag) if node.right: collect_vars(node.right, bag) return bag def simplify(node): # 只做最简单的常量折叠NOT 常量、AND/OR 的短路常量 if node.op NOT: child simplify(node.right) if child.op CONST: return Node(CONST, namestr(not (child.name True))) return Node(NOT, rightchild) if node.op in (AND, OR, IMP, EQ): left simplify(node.left) right simplify(node.right) # 完整布尔代数化简不在这里展开保留结构交给求值阶段 return Node(node.op, left, right) return nodecollect_vars用递归深度优先收集变量名bag是可变集合递归时复用避免每层新建集合。参数上node是 AST 根节点返回的集合可以直接sorted()后用于枚举。simplify里演示了NOT遇到CONST时的折叠CONST节点需要你在 AST 定义里补一个类型示例只给入口。边界要明确变量名大小写敏感多字母变量和单字母变量只能选一种规则不要在化简函数里偷偷做重言式判定否则后面测试失败时很难判断是化简错还是判定错。提示变量数超过 12 个时真值表枚举会迅速变慢先做变量去重和常量折叠再考虑更进一步的等价变换。3. 真值枚举与重言式判定变量数超过 10 个时怎么不翻车判定重言式的朴素定义很直白对所有变量赋值组合表达式都为真。代码写起来也直白收集变量、枚举2^n种赋值、逐一代入求值。真正容易翻车的地方在边界变量数一多枚举时间指数上涨表达式一深递归求值可能碰到递归深度限制程序只输出“是/否”验收时被问“为什么不是重言式”却拿不出反例。更稳的做法是把判定拆成三层求值器只负责单次赋值枚举器负责生成赋值并记录反例等价变换负责在暴力枚举之前减负。这样每一层都能单独测试出问题时不至于全盘重写。3.1 真值表枚举递归模板与位运算两种写法枚举变量赋值常见有两种写法递归生成字典或者用位掩码。递归写法可读性好适合课程设计文档资料里画调用树位掩码写法紧凑适合变量数中等时快速跑测试。下面用位掩码变量排序后第i个变量对应mask的第i位mask从 0 到2^n - 1每个mask就是一种完整赋值。求值器按节点类型递归计算IMP按not left or right展开EQ直接比较左右布尔值。返回值设计成(是否重言式, 反例环境)反例是后面调试的关键。def evaluate(node, env): op node.op if op VAR: return env[node.name] if op NOT: return not evaluate(node.right, env) if op AND: return evaluate(node.left, env) and evaluate(node.right, env) if op OR: return evaluate(node.left, env) or evaluate(node.right, env) if op IMP: return (not evaluate(node.left, env)) or evaluate(node.right, env) if op EQ: return evaluate(node.left, env) evaluate(node.right, env) raise ValueError(f未知节点: {op}) def is_tautology_bruteforce(root): variables sorted(collect_vars(root)) n len(variables) for mask in range(1 n): env {name: bool((mask i) 1) for i, name in enumerate(variables)} if not evaluate(root, env): return False, env return True, Noneevaluate是单次赋值下的递归求值器参数node是 AST 节点env是变量到布尔值的字典遇到未知节点直接抛错避免静默返回None把错误带到判定层。is_tautology_bruteforce先排序变量保证mask和变量顺序稳定1 n是2^nmask i 1取第i位一旦发现某个赋值下为假立刻返回False和反例环境不继续跑完剩余组合。边界n0时range(1)仍然会跑一次适合判断常量表达式Python 递归深度默认有限表达式嵌套很深时要改迭代求值或调整限制变量名重复不会影响集合但排序后顺序固定反例输出可复现。3.2 短路求值与反例输出别让程序只给“是/否”课程设计验收时老师经常随手给一个不是重言式的表达式问“你程序说不是那哪个赋值让它假”。如果程序只打印False这个环节就很被动。反例输出不需要复杂 UI把变量名和布尔值按字典序拼成一行就够用。format_env接收env或NoneNone表示所有赋值都为真有反例时输出AFalse, BTrue这种形式。这个函数很小但它把“判定结果”变成了“可验证的证据”调试时也能直接拿反例去手算 AST 的每个节点。def format_env(env): if env is None: return 无所有赋值均为真 return , .join(f{k}{v} for k, v in sorted(env.items())) # 使用示例先解析再判定最后打印反例 root Parser(tokenize((AB)AB)).parse() ok, bad is_tautology_bruteforce(root) print(ok, format_env(bad))这段代码做了两件事format_env把反例环境排序后转成可读字符串ok和bad分别承接判定结果和反例。参数上env是is_tautology_bruteforce返回的字典或Nonesorted(env.items())保证输出稳定。注意示例表达式里的括号和优先级(AB)AB按前面的优先级会解析成((AB)A)B如果你想要的是((AB)A)B这个例子可以如果想要(AB)(AB)必须补括号。很多翻车不是算法错是测试表达式自己写得有歧义。3.3 剪枝与等价变换什么时候该放弃暴力枚举暴力枚举适合变量数小、表达式短的课程设计演示但文档资料里要写清楚适用范围。变量数到 12 个时4096种赋值还能接受到 20 个就是一百万级别Python 里会明显变慢。减负的第一步是等价变换把蕴含AB换成!A|B把等价AB换成(AB)(BA)这样 AST 里只剩NOT、AND、OR和变量后续转否定范式或 CNF 都方便。下面的eliminate_imp_eq只做蕴含和等价消除返回新树不修改原树方便对比变换前后的结构。def eliminate_imp_eq(node): if node.op VAR: return node if node.op NOT: return Node(NOT, righteliminate_imp_eq(node.right)) left eliminate_imp_eq(node.left) right eliminate_imp_eq(node.right) if node.op IMP: # A B 等价于 !A | B return Node(OR, Node(NOT, rightleft), right) if node.op EQ: # A B 等价于 (A B) (B A) return Node(AND, Node(OR, Node(NOT, rightleft), right), Node(OR, Node(NOT, rightright), left)) return Node(node.op, left, right)eliminate_imp_eq按节点类型递归变量原样返回NOT继续处理子节点IMP展开成OR(NOT(left), right)EQ展开成两个蕴含再合并。参数node是 AST 根返回值是新树原树保留方便在测试里对比“变换前求值”和“变换后求值”是否一致。边界EQ展开会让节点数明显增加大表达式要先做结构共享或哈希缓存这里没有做德摩根律NOT里面还可能包着AND/OR后续转 NNF 要补。提示变量数超过 12 个、表达式节点数超过几百时先做常量折叠和蕴含/等价消除再决定是否继续暴力枚举不要在课程设计文档里写“支持任意变量数”那是给自己挖坑。4. 课程设计文档与模块接口把文档资料写成能验收的六张表课程设计最冤的翻车不是代码跑不通而是代码能跑、文档资料对不上接口表写的输入是字符串代码实际收 token 列表测试用例表只写“测试成功”没有预期输出报告里画了模块图源码里却找不到对应函数。验收老师一般不会逐行读代码但会顺着文档找证据这个模块输入什么、输出什么、异常怎么处理、测试覆盖了哪些边界。把文档资料写成表格比写大段说明更稳因为表格逼着你把每个字段填实。下面按模块接口、测试用例、报告结构三块拆表格里的内容可以直接照着改不用硬凑代码块。4.1 模块拆分解析、求值、判定、UI 四层接口模块拆分不要按“文件”拆要按“职责”拆。解析层负责字符串到 AST求值层负责 AST 加环境到布尔值判定层负责枚举和反例UI 或命令行层负责输入输出。每层只暴露一个主函数异常在层内转成可读信息。这样文档资料里的接口表就能和源码函数一一对应。下面这张表是课程设计里最该先填的填完再写代码能少返工。模块主函数输入输出异常/边界测试点词法tokenize(expr)原始表达式字符串token 列表末尾EOF非法字符、空串空白、多字母变量、非法符号解析Parser(tokens).parse()token 列表AST 根节点括号不匹配、多余 token优先级、结合性、括号嵌套求值evaluate(node, env)AST、变量环境布尔值未知节点、缺变量单变量、嵌套非、蕴含判定is_tautology_bruteforce(root)AST(bool, env或None)变量过多、递归过深重言式、矛盾式、可满足式输出format_env(env)环境或None可读字符串None表示全真反例排序、空环境表格填完后文档里还要补一句“层与层之间只通过返回值传递不共享全局变量”。课程设计里常见做法是全局变量存 token 列表短期省事后面加测试用例时互相污染。参数说明要落到字段expr不能为Nonetokens必须含EOFenv的键必须覆盖 AST 里所有变量缺变量应该在求值前报错而不是让KeyError随机冒出来。注意接口表里的函数名要和源码一致别文档写parse_expr代码里叫parse验收时很难解释。4.2 测试用例表重言式、矛盾式、可满足式各给三条测试用例不要只写“A|!A是重言式”。要按类别覆盖重言式、矛盾式、可满足但非重言式、非法输入、优先级边界、多字母变量。每条用例写清表达式、期望结果、覆盖点最好再写一个反例或说明。下面这张表可以直接放进文档资料代码里的单元测试按编号对应。表达式里的变量尽量用A、B、C多字母变量单独一组避免和单字母规则混淆。编号表达式期望覆盖点T01A!A重言式T02(AB)(BA)重言式T03(AB)(BA)重言式等价对称性T04A!A矛盾式矛盾式判定反例全假T05AB可满足非重言反例ATrue,BFalseT06ABC可满足非重言T07!!AA重言式连续非、等价T08(AB)(!A!B)T09A语法错误缺右操作数T10A$B词法错误非法字符定位这张表的关键不是数量是每类都有。T04 用来验证程序不是“全返回真”T05 用来验证反例输出T06 用来抓优先级翻车T09 和 T10 用来验证异常路径。文档资料里要给每条用例写“实际输出”栏验收前手动跑一遍填进去不要留空。参数上期望结果只有三类重言式、矛盾式、可满足非重言式如果程序只输出布尔值矛盾式和可满足非重言式都返回False文档里要额外用反例区分。提示测试用例表里不要写“测试通过”四个字就结束至少写清反例或错误信息否则后面排查没有证据。4.3 报告结构问题描述到测试记录的顺序课程设计报告不要按“想到哪写到哪”组织。比较稳的顺序是问题描述、需求分析、数据结构设计、算法流程、模块接口、测试记录、边界与不足。问题描述里写清楚“重言式”的定义和输入表达式文法需求分析里写变量规模上限和异常处理要求数据结构设计放 AST 节点定义和 token 结构算法流程放递归下降和真值枚举模块接口放 4.1 的表测试记录放 4.2 的表和实际输出边界与不足里老实写“变量数超过 12 个时暴力枚举变慢当前版本用等价变换减负未实现 SAT 求解器”。这样写不丢人反而显得知道边界。报告章节写什么验收点问题描述重言式定义、输入输出约定文法是否明确需求分析变量规模、异常类型、运行方式边界是否写清数据结构token、AST 节点、变量集合字段和源码是否一致算法流程词法、递归下降、枚举、反例优先级和结合性模块接口函数签名、参数、返回值能否对应源码测试记录用例表、实际输出、反例是否覆盖异常边界与不足变量上限、未实现功能是否诚实报告里的图和表要能回指源码。比如 AST 节点表里写op取值VAR/NOT/AND/OR/IMP/EQ源码里就不能多一个没解释的XOR算法流程写“右结合”测试用例里就要有连续蕴含的用例。文档资料不是装饰它是验收时老师顺着查的路线图。注意报告里不要贴大段没有注释的代码关键函数贴签名和注释即可完整源码放配套文件里正文解释参数和边界。5. 避坑与排查重言式程序实现里最常见的 5 个翻车点重言式程序实现的代码量不大翻车点却很集中优先级、变量收集、反例输出、递归深度、文档和代码不一致。下面 5 条是课程设计验收里最容易碰到的每条按“现象 → 原因 → 解决”写。排查顺序建议固定成先跑词法确认 token 流再打印 AST确认结构再跑单变量用例确认求值最后跑多变量和异常用例。这个顺序能把问题锁在小范围内不至于一上来就怀疑算法。5.1 解析阶段的三个坑现象表达式A|BC的判定结果和手算不一致手算是A|(BC)程序却像按(A|B)C算。原因递归下降的优先级层级写反了or_里先调了and_才对但如果and_里又回头调or_或者parse入口从and_开始就会把或和与的优先级颠倒。解决固定优先级从低到高为等价、蕴含、或、与、非入口从最低的eq开始在文档资料里写一张优先级表测试用例加A|BC和A(B|C)对照。血泪经验是优先级错误不会在解析时报错只会在判定时给出一个看起来很合理的结果所以必须靠用例表抓。现象连续非!!A报语法错误或者程序卡住。原因not_函数只处理一层!消费后直接调atom第二个!落到atom里没有匹配分支另一种写法是not_里用if而不是while连续非只吃一个。解决not_在遇到!后递归调用自身而不是直接调atom测试用例加!A、!!A、!!!A并在 AST 打印里确认NOT嵌套层数。注意连续非在布尔值上会抵消但 AST 结构必须保留否则文档里说的“一元非节点”就对不上。现象多字母变量AB被拆成A和B判定结果和预期完全不同。原因词法扫描按单字符读变量或者文档里写“变量为单字母”代码却允许连续字母规则不统一。解决二选一。要么词法把连续字母收成一个变量名文档里写“变量名由字母组成区分大小写”要么词法只读单字符遇到连续字母报错文档里写“变量仅限单字母”。不要代码支持多字母、文档写单字母验收时老师输入AB就会出问题。测试用例要单独加多字母组比如AA|!AA确认变量集合里只有一个AA。5.2 判定与文档的两个坑现象程序判定某个表达式是重言式验收时老师随手给一个赋值却是假。原因变量收集漏了右子树或者收集时用了局部集合但没有合并导致枚举的变量集合少了变量求值时缺失变量被默认成False于是某些赋值根本没被枚举到。解决collect_vars必须同时遍历left和right递归返回同一个集合求值前检查env是否覆盖collect_vars的全部变量缺变量直接报错不要给默认值。排查时打印变量集合和枚举次数变量数n对应枚举次数应该是2^n对不上就说明收集有问题。现象变量数一多程序卡死命令行半天不返回。原因暴力枚举是2^n变量数到 20 以上时组合数爆炸如果表达式里还有重复子结构求值又在重复递归时间会更高。解决在文档里写清适用范围比如“变量数不超过 12 个时直接枚举超过时先做常量折叠和蕴含/等价消除仍超限则提示用户”代码里加变量数上限和耗时保护不要把“支持任意变量”写进报告。更进一步的 SAT 或 BDD 思路可以放在“不足与改进”里但不要假装已经实现。提示课程设计验收更看重边界诚实和测试完整吹一个跑不动的无限变量支持反而扣分。现象文档资料里的接口表和源码对不上报告写parse_expr代码里是Parser.parse测试记录写“全部通过”但实际输出栏空着。原因文档是最后补的代码改完没回填或者测试用例只跑了正常路径异常路径没记录。解决先定接口表再写代码代码改签名时同步改表测试记录必须贴实际输出至少包含一条反例和一条错误信息。排查时拿报告里的函数名去源码里搜搜不到就是不一致。注意文档里的“变量上限”“异常类型”“运行方式”要和源码常量、raise语句对得上别写一套做一套。6. 进阶验证与性能对照用随机对拍和等价变换给结果上保险判定逻辑写完后最容易犯的错是“只拿自己编的几个用例跑通就交付”。手工用例覆盖有限优先级、括号、连续非这些组合一多边缘错误很难靠肉眼发现。我一般会加一层随机对拍随机生成表达式用 AST 求值器算一遍再用另一套独立的求值方式算一遍逐赋值比较。另一套求值方式不需要多高级把表达式转成 Python 布尔表达式在受限命名空间里求值即可但只能用于测试生成串不能拿用户输入直接eval。这样做的价值是把“我觉得对”变成“两套实现互相印证”翻车概率会低很多。6.1 随机表达式对拍让两套求值器互相盯着随机生成器控制深度递归拼接变量和二元运算符括号全部显式加上避免优先级干扰对拍本身。转换函数把、|、、替换成 Python 的布尔运算AB在布尔序上等价于AB替换成。对拍循环里AST 求值用布尔字典本文还有配套的精品资源点击获取