基于算符优先与二叉树的逻辑表达式重言式判别课设实战

简介这份资源是计算机科学与技术专业数据结构与算法课程设计的完整报告文档主题为重言式判别适合正在学习数据结构、需要完成课程设计或想深入理解栈与二叉树应用的高校学生参考。文档围绕逻辑表达式求值展开涵盖输入处理、运算符优先级判定、双栈求值、二叉树构造及真值表判别等核心环节并给出多组测试用例与详细的问题分析。资源包共1个doc文件大小约293KB内容为完整的课程设计报告包含题目描述、问题分析、数据结构选择与概要设计等章节结构规范可直接作为课程设计模板或学习范例。目前已有147人学习下载。读者可从中获取算符优先级表的归纳方法、利用运算符栈与变量栈构造表达式二叉树的具体思路以及通过中序遍历二叉树完成逻辑求值的实现路径对理解栈与二叉树在表达式处理中的协同应用具有较高参考价值。1. 从一份课设报告说起重言式判别到底在练什么很多人看到“重言式判别”这几个字第一反应是离散数学里的真值表第二反应是“这玩意儿能干嘛”。但如果你正在做数据结构与算法课程设计或者想找一个能把栈、二叉树、递归、穷举四件事串起来的练手项目那这份报告其实是个被低估的素材。它表面上是判断一个逻辑表达式是不是永真、永假还是可满足实际上考的是你能不能把中缀表达式求值那套东西从算术域迁移到逻辑域。逻辑运算符只有|、、~三个变量是大写字母空格随便加输入长度不超过一行输出要求也直白永真给True forever永假给False forever否则给Satisfactible并列出变量名序列还能让用户自己给变量赋值再算一次。适合谁正在啃数据结构课设的本科生、想复习栈与二叉树配合的开发者、以及需要一个小型表达式引擎原型的人。下面我按“能跑起来”的标准把这份报告里的设计思路、代码骨架和调试坑拆开讲。2. 算符优先级表与双栈建树把逻辑表达式变成二叉树2.1 为什么不能直接递归下降而要用算符优先表逻辑表达式和算术表达式在结构上几乎同构区别只在于运算符集合和优先级关系。算术里是 - * /和括号逻辑里是| ~和括号。既然算术表达式求值可以用算符优先法配两个栈搞定逻辑表达式同样可以。这份报告选择的就是算符优先法而不是递归下降。原因很实际课设环境里 C 语言写递归下降要处理词法、语法两层代码量大且容易在括号嵌套上翻车算符优先法只需要一张 7×7 的优先关系表加两个栈逻辑清晰调试时能直接看栈内容。算符集是{ |, , ~, (, ), # }其中#是表达式起始和结束的哨兵。优先关系归纳下来就是~最高次之|最低左括号入栈后优先级最低直到遇到右括号右括号遇到左括号时两者优先级相同直接弹掉左括号。报告里给了一张表我把它整理成更直观的形式a1 \ a2|~()#|~(无)无#无这张表是整份报告的核心。表示栈顶算符优先级高要出栈计算表示当前算符优先级高要入栈表示括号配对或哨兵相遇弹栈但不计算。注意~是一元运算符出栈时只弹一个变量做右孩子左孩子置空。2.2 双栈建树的具体步骤与代码骨架建树过程用两个栈logic存算符节点variable存变量或中间结果节点。每个栈元素都是二叉树节点指针。初始化时把#压入logic。然后逐字符扫描表达式遇到大写字母分配节点压入variable。遇到运算符取logic栈顶查表比较优先级。若当前算符优先级高当前算符入logic。若栈顶算符优先级高弹出栈顶算符g从variable弹出一个节点a作为右孩子如果g不是~再弹一个b作为左孩子用g做根把新子树压回variable。然后继续比较当前算符与新的栈顶直到当前算符能入栈。若优先级相同弹出栈顶算符左括号或#当前算符不压栈继续读下一个字符。报告里有一段关键代码我把它整理成可读版本// 算符优先关系表行和列的顺序|,,~,(,),# char bijiao[7][7] { { , |, , ~, (, ), #}, {|, , , , , , }, {, , , , , , }, {~, , , , , , }, {(, , , , , , }, {), , , , , , }, {#, , , , , , } }; char youxianji(char a1, char a2) { int i, j; for (i 0; i 7; i) if (bijiao[0][i] a2) break; // 找 a2 的列号 for (j 0; j 7; j) if (bijiao[j][0] a1) break; // 找 a1 的行号 return bijiao[j][i]; }这段代码的逻辑说明bijiao[0]存的是列头算符bijiao[j][0]存的是行头算符。查表前先定位行列再返回关系字符。参数a1是栈顶算符a2是当前读入算符。注意表中有些位置是空格表示非法组合实际扫描时不会遇到因为括号和哨兵已经保证了合法性。建树主循环里有一个容易写错的地方当栈顶算符优先级高、执行完一次出栈计算后不能直接读下一个字符而要继续拿当前算符和新的栈顶比较。报告里用s s - 1回退一格再break出 switch外层循环s后正好重新处理同一个算符。这个写法有点绕但逻辑是对的。我一般会改成while内循环把“当前算符入栈”作为退出条件可读性更好。2.3 变量提取与赋值组合的生成建树之前要先扫描一遍表达式提取所有不重复的大写字母确定变量个数m。报告里的做法是用一个bl[]数组存变量每遇到一个新字母就检查是否已存在不存在则追加。变量个数决定穷举次数2^m种赋值组合。生成赋值组合的代码很巧妙利用二进制位运算int zuhe[maxsize]; // zuhe[变量ASCII码-65] 存该变量当前取值 void creatzuhe(int n, int m, char a[]) { int lzp m - 1; for (int i 0; i m; i) { zuhe[a[lzp] - 65] (n i) % 2; lzp--; } }逻辑说明n是第几种赋值情况从 0 到2^m - 1。(n i) % 2取n的二进制第i位赋给变量a[lzp]。注意这里a[]存的是变量字母a[lzp] - 65把字母映射到zuhe数组下标。参数m是变量个数lzp从m-1递减保证变量按某种顺序拿到二进制位。这个写法比递归生成全排列更紧凑但前提是变量字母不能重复且zuhe数组要开够大至少 26。3. 中序遍历求值与重言式判定递归、穷举和结果输出3.1 递归求值的边界与运算符处理二叉树建好后求值就是对树做一次中序遍历。递归函数的终止条件是遇到空节点返回 0遇到变量节点返回zuhe[变量ASCII码-65]遇到运算符节点则递归求左右子树再按运算符计算。报告里的valuetree函数把这三类情况写得很清楚int valuetree(bitree tree) { if (!tree) return 0; if (tree-data ! | tree-data ! tree-data ! ~) return zuhe[tree-data - 65]; // 变量节点返回当前赋值 switch (tree-data) { case |: return valuetree(tree-lchild) || valuetree(tree-rchild); case : return valuetree(tree-lchild) valuetree(tree-rchild); case ~: return !valuetree(tree-rchild); // 非运算只有右孩子 default: return 0; } }参数说明tree是当前子树根节点。~节点没有左孩子建树时已经保证。递归深度等于树高最坏情况是表达式完全括号化树退化成链深度为O(m)m是变量个数不会太大。注意 C 语言里||和有短路特性但这里左右子树都必须求值因为递归调用本身有副作用读取zuhe数组短路不影响结果但会少算一个子树逻辑上没问题性能上反而更快。不过如果后续要统计子表达式求值次数就不能依赖短路。3.2 穷举所有赋值并判定表达式类型主判定逻辑是对n从 0 到2^m - 1每次调用creatzuhe(n, m, bl)生成一组赋值再调用valuetree(tree)求值把结果累加到sum。循环结束后sum 2^m重言式输出True forever。sum 0矛盾式输出False forever。否则可满足式输出Satisfactible和变量名序列。报告里还要求可满足式时输出每种赋值和对应的表达式值。这需要在循环里保存每组赋值和结果或者再跑一遍循环输出。我一般会在第一遍循环时把结果存到数组里避免重复计算。时间复杂度是O(m * 2^m)因为每组赋值要遍历m个变量求值本身是O(m)总的就是O(m * 2^m)。空间复杂度O(m)主要是zuhe数组和递归栈。3.3 用户交互与手动赋值报告要求程序提供两种模式自动穷举和用户手动赋值。手动赋值时程序先输出变量名序列然后让用户依次输入每个变量的值0 或 1再调用valuetree求值并显示结果。这部分代码不复杂但要注意输入缓冲区的处理。C 语言里scanf读整数后会留下换行符下一次读字符前要清一下。我一般用getchar()循环吃掉换行或者直接用scanf( %c, ch)前面的空格跳过空白。交互菜单可以用switch实现输入 1 走自动穷举输入 2 走手动赋值输入 3 退出。报告里的流程图显示主循环是while(1)包住菜单每次执行完回到菜单直到用户选择退出。这个结构对课设来说够用但实际产品里会加输入校验防止用户输入非法字符导致死循环。4. 避坑与排查那些让课设卡到半夜的细节4.1 优先级比较后忘记继续出栈导致A~B|~AB算错现象测试表达式A~B|~AB时程序输出结果与真值表不符明明是可满足式却判成重言式或矛盾式。原因建树时当前算符优先级低于栈顶算符执行了一次出栈计算后没有继续比较当前算符与新的栈顶而是直接读下一个字符。这样会导致部分高优先级算符没有被及时计算树结构错误。解决把入栈条件从if (*s ! # *s ! ))改成if (*s ! # *s ! ) youxianji(*s, e-data) ! )。这样只有当前算符优先级高于栈顶时才入栈否则继续出栈计算。报告里就是这么修的我实测有效。4.2 变量不按字母顺序输入时赋值错位现象输入ABFG这种变量不连续、不按字母表顺序的表达式求值结果随机错误。原因生成赋值组合时zuhe数组下标用的是变量在bl[]中的位置而求值时用的是变量 ASCII 码减 65。两套下标对不上导致变量拿到的值张冠李戴。解决统一用 ASCII 码减 65 作为zuhe下标。把zuhe[i] (n i) % 2改成zuhe[a[lzp] - 65] (n i) % 2。这样无论变量输入顺序如何每个变量都能拿到正确的赋值。报告里也是这么改的。4.3 空格处理不干净导致扫描到非法字符现象表达式里带空格时程序把空格当成运算符或变量建树失败或结果异常。原因扫描前没有去除空格或者去除空格时数组越界。解决在读入表达式后、建树前先做一次过滤把所有空格去掉存到新数组stri里。报告里的代码是for (; *pstr ! NULL; pstr, n) { if (str[n] ! ) stri[i] *pstr; }注意stri要手动补\0否则后续strlen会越界。我一般会在循环后加stri[i] \0;。4.4 栈操作没有判空弹出时崩溃现象程序在某个表达式上突然崩溃调试发现是pop时栈已经空了。原因优先级比较或括号匹配逻辑有漏洞导致多弹了一次栈。比如~运算符出栈时代码里先弹了一个变量又判断g-data ! ~才弹第二个但如果表达式非法可能第一个弹的时候就空了。解决在pop函数里加判空空栈时直接返回错误码或打印提示。课设环境里可以在pop开头加if (st-top st-base) { printf(stack empty\n); return; }。另外输入表达式要以#结尾建树循环里靠#和)控制出栈如果用户输入没有#程序会读越界。我一般会在读入后自动在末尾补#。4.5 递归求值时变量节点判断条件写错现象表达式里只有变量和~时求值结果恒为 0 或 1不符合预期。原因valuetree里判断变量节点的条件写成了tree-data ! | tree-data ! tree-data ! ~但如果树节点里存了其他字符比如空格没清干净会走到default返回 0。解决在变量提取阶段就保证stri里只有大写字母、|、、~、(、)、#。建树时遇到非法字符直接报错退出。另外valuetree里变量判断可以改成if (tree-data A tree-data Z)更直观。5. 进阶技巧把课设代码改成可复用的表达式引擎课设代码能跑通测试用例但离“能用”还有距离。我一般会做三件事把栈和二叉树封装成独立模块、把优先关系表改成可配置、加一个批量测试脚本。下面说具体做法。第一栈结构不要用base和top两个指针加stacksize那种写法直接定义struct Stack { bitree data[maxsize]; int top; }push和pop都基于top索引代码短一半也不容易越界。二叉树节点分配用malloc后要检查返回值课设环境里内存充足但养成习惯没坏处。第二优先关系表可以抽成函数把bijiao二维数组改成static const char priority[7][7]行列索引用枚举OP_OR, OP_AND, OP_NOT, OP_LPAREN, OP_RPAREN, OP_END。这样查表时不用循环找行列直接priority[op1][op2]速度快且不易写错。枚举定义如下typedef enum { OP_OR, OP_AND, OP_NOT, OP_LPAREN, OP_RPAREN, OP_END, OP_INVALID } OpType; OpType char_to_op(char c) { switch (c) { case |: return OP_OR; case : return OP_AND; case ~: return OP_NOT; case (: return OP_LPAREN; case ): return OP_RPAREN; case #: return OP_END; default: return OP_INVALID; } }第三批量测试。课设报告里给了 6 组测试数据手动一组组输太慢。我一般写个test.txt每行一个表达式程序读文件逐行处理输出结果到result.txt。这样改代码后跑一遍就能知道有没有回归。测试数据里有一组A~B|~AB;O ,0;0,1;1,0;1,1分号后面是手动赋值的变量值解析时按分号切分即可。第四性能边界。变量个数m超过 20 时2^m超过一百万穷举会明显变慢。课设表达式变量一般不超过 5 个但如果你想扩展成通用引擎可以加一个剪枝如果已经发现一组赋值使表达式为真且一组为假就可以提前判定为可满足式不用跑完所有组合。不过报告要求输出所有赋值结果所以剪枝只在“只判类型”模式下启用。最后说一个我踩过的坑报告里的代码用了#include iostream.h这是老式 C 头文件现代编译器会报错。如果要在新环境编译把iostream.h改成stdio.h和stdlib.h就够了因为代码里没用 C 特性。另外void main()要改成int main()并返回 0否则 GCC 会警告。从那以后我每次拿到课设代码都先跑一遍编译器警告把-Wall打开能省很多调试时间。希望帮到你。本文还有配套的精品资源点击获取