重言式判别课程设计详解：二叉树与双栈实现逻辑表达式求值

简介：合肥学院计算机科学与技术专业的一份课程设计报告，围绕数据结构与算法课程中“重言式判别”题目，完整展示了如何通过真值表判断逻辑表达式属于重言式、矛盾式还是可满足式。报告从题目描述、基本要求、测试数据出发，深入分析了空格符去除、运算符优先级、基于堆栈与二叉树的中序表达式求值等关键问题，并给出数据结构选择、概要设计和具体算法实现思路。压缩包内仅含1个doc文档，大小约293KB；目前已有147人学习/下载，内容集中且便于直接阅读。报告中的测试数据涵盖(A|~A)&(B|~B)、(A&~A)&C、A&B&C&~B等典型表达式，可用于验证判别程序的正确性；设计部分还包含算符优先关系表和二叉树构造示意，适合学习数据结构、逻辑表达式求值以及课程设计写作的计算机专业学生参考，可借鉴其堆栈与二叉树结合的真值表判别方法、测试用例设计思路和报告组织方式。

重言式判别课程设计：基于二叉树和双栈的完整实现

看到“重言式判别”这个题目，多数人第一反应是“枚举所有变量取值，逐行算一遍真值表”——听起来不难，但实际动手后你会发现，真正的难点不在枚举，而在怎么把一个带括号、带空格、优先级混乱的字符串表达式变成计算机能一步步求值的结构。这份合肥学院计算机科学与技术系的数据结构与算法课程设计报告，恰好把这条路完整走了一遍：两个栈 + 一颗二叉表达式树，把“输入字符串”到“输出 True forever / False forever / Satisfactible”的全过程拆得明明白白。适合正在做课程设计、或者想复习表达式求值的人拿来当参考骨架。

2. 重言式判别的数学结构：为什么落在二叉树和双栈上

2.1 算符优先级表：整个程序的题眼

逻辑表达式的运算规则其实和我们小学学的算术表达式一模一样：先括号内后括号外，先取反、再相与、后相或。也就是说，运算符的优先级从高到低是“~” > “&” > “|”。但光有这条还不够，因为表达式里还有括号和结束符。

报告里把运算符和界限符统称为“算符”，算符集是 { ~, &, |, (, ), # }，其中 # 是表达式的起始/结束符。任何两个前后相继出现的算符 a1 和 a2 之间，都存在三种关系：a1 优先级低于 a2（记作 <）、高于 a2（记作 >）、等于 a2（记作 =）。把所有组合列出来，就是那张关键的算符优先关系表：

这张表怎么读？a1 是运算符栈栈顶的算符，a2 是刚从表达式里读入的算符，查表得到的 <、>、= 决定下一步动作：< 说明栈顶优先级低，a2 入栈；> 说明栈顶优先级高，栈顶出栈参与运算；= 说明左右括号相遇或起始结束符相遇，直接出栈。

2.2 为什么选“栈 + 二叉树”，而不是中缀转后缀

看一个最简单的例子：(A|~A)&(B|~B)。如果按常规思路先转后缀表达式再求值，也能做，但要额外处理括号的匹配和运算符的临时存储，还要在求值时维护操作数栈。这份报告的做法更直接：用两个栈，一个放运算符、一个放变量，每次栈顶运算符优先级高于待入栈运算符时，就弹出栈顶算符和变量栈里的两个变量，组合成一棵子树的结点，再压回变量栈。这样扫完一遍表达式，变量栈里剩下的就是一棵完整的表达式二叉树。

这棵树的定义很干净，每个结点要么是大写字母变量、要么是逻辑运算符|&~，运算符结点的左右孩子是它的操作数，~是单目运算，只有右孩子：

typedef struct node { // 二叉树的结点 char data; // 变量字母或运算符 | & ~ struct node *lchild; // 左孩子 struct node *rchild; // 右孩子 } BiTNode, *bitree;

之所以用二叉树而不是直接边扫描边算，是因为后面要遍历所有变量取值组合。如果边扫描边算，每换一组变量值就得把整个表达式重新解析一遍；而建成二叉树后，只要换变量取值，再对这棵树做一次中序遍历求值即可，解析只做一次。这是典型的“一次编译、多次执行”思路。

2.3 变量取值组合的数学规律：二进制数位

报告用了一个很巧的规律：给 n 个变量赋第 k 组值，第 i 个变量的取值等于(k >> i) % 2。也就是说，所有变量的取值组合，本质是从 0 到 2^n - 1 的二进制数按位展开。

举个例子，两个变量 A、B 的四种取值：

若 B 是低位、A 是高位，那么(k >> 0) % 2是 B 的值，(k >> 1) % 2是 A 的值。代码里把这个规律落成了这样：

void creatzuhe(int n, int m, char a[]) { int lzp = m - 1; for (int i = 0; i < m; i++) { // a[lzp] 是当前变量的字母，减去 'A' 得到它在取值数组中的下标 // (n >> i) % 2 取二进制第 i 位的值 zuhe[a[lzp] - 65] = (n >> i) % 2; lzp--; } }

这里a[]是变量名列表，m是变量个数，n是第几次组合。赋值的目标下标不是“第几个变量”，而是“该变量字母在 ASCII 码中相对 A 的位置”。比如变量 F，赋值的下标是'F' - 'A' = 5。这样后面递归到叶子结点时，直接查zuhe[tree->data - 'A']就能拿到这个变量当前的值，不用再从头找变量名下标。

3. 核心代码落点：从字符串到二叉树的三个关键函数

3.1 去空格与变量收集

用户输入的逻辑表达式长度不超过一行，且任意位置可以有多个空格。报告的处理是把空格全部剔除，再把连续字符串存到一个干净的数组里：

for (; *pstr != '\0'; pstr++, n++) { if (str[n] != ' ') { stri[i++] = *pstr; // 只拷贝非空格字符 } }

为什么非得去空格？因为后续的扫描逻辑是按“变量或算符”逐字符判断的，空格既不可能是变量也不可能是算符，留着只会打断if (stri[k] >= 65 && stri[k] <= 90)这种连续判断，还容易让人误以为读到了非法字符。

找变量就是在去空格后的字符串上扫一遍，遇到大写字母就和已收集的变量列表比对，如果重复就跳过，否则追加到变量数组bl[]里，变量个数加一：

for (int k = 0; k < strlen(stri); k++) { if (stri[k] >= 65 && stri[k] <= 90) { // 大写字母 A-Z int mark = 0; for (int j = 0; j < m; j++) { if (bl[j] == stri[k]) { // 这个变量已经收集过 mark = 1; break; } } if (mark == 0) { bl[m++] = stri[k]; // m 是当前变量总数 } } }

这里有个细节容易踩：65和90是 ASCII 码里 A 和 Z 的位置，所以这个程序只支持大写字母做变元，小写字母会被当作非法输入。测试数据也全是 A 到 E 的大写字母，这是题目约束，不是偷懒。

3.2 优先级查表：用二维数组存算子关系

报告把整张算符优先关系表存进了一个二维数组，表里的行号是 a1（栈顶算符）、列号是 a2（当前读入算符），查表函数返回<、>或=：

char youxianji(char m, char n) { // 二维数组：行是栈顶运算符，列是读入运算符 char bijiao[7][7] = { {' ', '|', '&', '~', '(', ')', '#'}, {'|', '>', '<', '<', '<', '>', '>'}, {'&', '>', '>', '<', '<', '>', '>'}, {'~', '>', '>', '>', '<', '>', '>'}, {'(', '<', '<', '<', '<', '=', ' '}, {')', '>', '>', '>', ' ', '>', '>'}, {'#', '<', '<', '<', '<', ' ', '='} }; int i, j; for (i = 0; i < 7; i++) { if (bijiao[0][i] == n) break; // 找到 n 的列号 } for (j = 0; j < 7; j++) { if (bijiao[j][0] == m) break; // 找到 m 的行号 } return bijiao[j][i]; // 返回 '<' '>' '=' }

这段代码的边界值得多说一句：(行、)列的那个=表示“左右括号相遇”，出栈左括号即可，不生成运算结点；#行、#列的=表示表达式扫描结束，这时运算符栈弹空，算法结束。

这张表是整个程序唯一一处需要“背下来”的逻辑，其他地方都是从这张表推出来的。如果你要改造成支持更多运算符（比如异或^、蕴含->），只需要扩表、加列，逻辑部分基本不用动。

3.3 建树主循环：一次扫描，算符栈和变量栈交替工作

这是整个程序最核心的循环，也是最能体现“栈 + 二叉树”组合的地方。我把报告里的关键逻辑整理成可读性更好的伪代码：

while (*s != '\0') { if (*s 是大写字母) { // 读到了变量，建一个叶子结点压入变量栈 variables = (bitree)malloc(sizeof(node)); variables->data = *s; push(variable, variables); } else if (*s 是算符) { gettop(logic, e); // 取运算符栈栈顶 switch (youxianji(*s, e->data)) { case '<': // 栈顶优先级低：当前算符入栈 logics = (bitree)malloc(sizeof(node)); logics->data = *s; push(logic, logics); break; case '=': pop(logic, kuohao); // 左右括号相遇或 # 相遇，直接出栈 break; case '>': // 栈顶优先级高：弹出一个算符和两个变量，组成新子树 pop(logic, g); pop(variable, a); b = NULL; if (g->data != '~') { pop(variable, b); // 双目运算需要第二个变量 } create(g, b, a); // 建树：b 是左孩子，a 是右孩子 push(variable, g); // 子树根当作一个新的“变量” gettop(logic, e); // 关键修正：如果当前算符优先级还是低于新栈顶，不能急着入栈 if (*s != '#' && *s != ')' && youxianji(*s, e->data) != '>') { logics = (bitree)malloc(sizeof(node)); logics->data = *s; push(logic, logics); } else { s = s - 1; // 回退一步，让当前算符下一轮重新参与比较 } break; } } s++; } tree = g; // 循环结束后，g 就是整棵表达式树的根

讲一下这段代码最容易绕晕的地方：case '>'里为什么有时候要s = s - 1回退？

因为一次出栈建树可能还没把栈顶所有高优先级算符处理完。处理完一个算符后，新栈顶算符可能仍然比当前读入的算符优先级高，此时应该继续出栈运算，而不是把当前算符入栈。如果不回退，当前算符就被跳过了；如果直接入栈，就会产生报告里“测试数据 A&~B|~A&B 结果错误”的那种优先级错乱。回退让当前字符下一轮再比较一次，相当于“压栈前先清空所有优先级更高的算符”。

create函数做的事就是把两个变量结点挂到一个算符结点下面。需要注意~是单目运算符，报告里把~的左孩子置空、右孩子挂操作数。放到二叉树里理解，就是左孩子为 NULL 的算符结点。

3.4 递归求值：中序遍历二叉树

建好树之后，给一组变量取值，求表达式值的函数就是一个标准的中序遍历。报告用zuhe[]数组存当前这组取值，叶子结点返回zuhe[tree->data - 'A']，内部结点按运算符递归计算：

int valuetree(bitree tree) { if (!tree) return 0; // 空结点按 0 处理 if (tree->data != '|' && tree->data != '&' && tree->data != '~') return zuhe[tree->data - 'A']; // 叶子：查变量当前取值 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; } }

这个函数的递归边界藏着一个易错点：if (!tree) return 0针对的是~结点左孩子为空的情况。也就是说，~的左孩子是一棵空树，递归进去会返回 0，但不会被当作变量参与运算。

主程序里对 2^n 组取值逐一调用valuetree，把返回值求和，得到SUM。然后按三条规则判别：

• SUM == 2^n：重言式，输出True forever
• SUM == 0：矛盾式，输出False forever
• 0 < SUM < 2^n：可满足式，输出Satisfactible

顺带提一句：对这个题目来说，中间结果相加的判断方式并不是唯一解。也可以在循环里加短路判断——一旦发现既有真又有假，就可以提前判定为可满足式。不过课程设计的场景下，把 2^n 组全部计算完看 SUM 更直观，代码也更容易讲清楚。

4. 避坑记录：三个典型翻车现场

4.1 现象：A&~B|~A&B计算结果不对

• 现象：测试题目给的第六组数据A&~B|~A&B输出不符合预期，表达式被判成了错误类型。
• 原因：建树时如果当前读入的算符优先级低于栈顶优先级，需要先弹出栈顶算符运算。但原代码只在弹出一个算符后就急着把当前算符入栈，如果弹出后新栈顶优先级仍然高于当前算符，继续运算的逻辑就丢了。结果就是|的优先级实际上被抬高了，整棵树的形态不对。
• 解决：把算符入栈条件从if (*s != '#' && *s != ')')改成if (*s != '#' && *s != ')' && youxianji(*s, e->data) != '>')，同时配合s = s - 1回退。也就是说，“入栈前先把所有优先级更高的栈顶算符清空”。

4.2 现象：变量不是按字母顺序输入时结果错

• 现象：测试A&B&F&G这类表达式（变量名不是从 A 开始连续取）时，结果完全乱套。
• 原因：creatzuhe里最初用zuhe[i] = (n >> i) % 2给变量赋值，下标i按变量列表顺序递增；但valuetree里叶子结点取值时用的是zuhe[tree->data - 'A']，下标是变量字母的 ASCII 差。两者对不上。如果变量恰好是 A、B、C、D 这种连续字母，两个下标恰好一致，程序碰巧能跑对；一旦出现 F、G 这种跳跃字母，错位就暴露了。
• 解决：把赋值语句改成zuhe[a[lzp] - 65] = (n >> i) % 2，让“变量列表顺序”和“ASCII 码下标”一致。这个小 bug 恰好说明了一个通用教训：全局数组的下标语义必须统一，要么都用“第几个变量”，要么都用“字母序号”，混用必然翻车。

4.3 现象：括号匹配后多出一个空结点

• 现象：表达式中出现形如(A|B)这种最普通的括号时，建树后偶尔多出一个 data 为空的结点，求值时返回 0，污染最终结果。
• 原因：左右括号相遇时，case '='只做了一次pop(logic, kuohao)把左括号弹出。但如果括号内的小表达式已经建好子树，这个子树已经被压入变量栈，此时应该直接结束本轮循环，继续读下一个字符，不应该再有额外的建树动作。部分实现里循环控制条件写得不严谨，在=分支后继续走s++，让右括号字符也被当成算符处理了一轮。
• 解决：在case '='分支处理完后，用break跳出 switch，确保右括号只负责“闭合”，不参与运算。写代码时养成一个好习惯：栈弹出后如果该分支不需要再访问栈顶，立刻 break，不要让它掉进后续的公共逻辑。

5. 测试验证：六组数据的预期与实测

报告作者把题目给的六组测试数据全部跑了一遍，我把它们整理成一张判别表，方便你复核自己的实现：

注意第一组(A|~A)&(B|~B)，它本质是(A 或 非A) 与 (B 或 非B)，前半部分恒真、后半部分恒真，所以是重言式。而(A&~A)&C中A 与 非A恒假，无论 C 取什么都输出假，所以是矛盾式。中间那组A|B|C|D|E|~A其实包含了 A 和 ~A 的同或关系，任何取值下至少有一个为真，也是重言式。

如果拿你自己的实现去测第五组(A|B)&(A|~B)，可以在草稿纸上演算一下：A 取 0、B 取 0 时表达式为 0，A 取 1、B 取 0 时为 1，所以既不是恒真也不是恒假，是可满足式。

时间性能方面，这个算法给每个变量赋值要 O(n)，共有 2^n 种组合，所以建树后求值部分的时间复杂度是 O(n * 2^n)。当变量个数 n 超过 20 时，这个算法会明显吃力；但对课程设计的测试数据规模（最多 5 个变量）来说完全够用。

6. 进阶用法：把“只能判别”升级成“可交互的工具”

课程设计的原始实现有一条交互线索：用户输入表达式后，可以选择“程序自动穷举”或“用户手动赋值”。原代码里这两种模式是通过菜单选项切换的，但很多同学在复现时只实现了穷举判别，把用户手动赋值这条路丢了。其实加这个功能不复杂，核心就两件事：一是预留一个模式标记，二是把valuetree从“读全局取值数组”改成“读用户输入的值”。

常见的做法是这样：在判别主循环里加一个mode变量，mode == 0走穷举求和，mode == 1走用户交互。穷举模式跑完如果发现是可满足式，而且用户想进一步看某个具体取值下的结果，就切换到手动模式：

int mode; // 0 自动穷举，1 用户手动赋值 if (mode == 0) { // 自动穷举所有 2^n 组取值 for (int k = 0; k < pow(2, N); k++) { creatzuhe(k, N, bl); sum += valuetree(tree); } if (sum == pow(2, N)) { printf("True forever\n"); } else if (sum == 0) { printf("False forever\n"); } else { printf("Satisfactible\n"); } } else { // 用户手动给每个变量输入 0 或 1 for (int i = 0; i < N; i++) { printf("%c = ", bl[i]); scanf("%d", &zuhe[bl[i] - 'A']); } printf("%d\n", valuetree(tree)); }

这段代码把两种模式合并进了同一个框架。手动模式下输入变量值后，仍然通过valuetree求值，区别只是取值数组的来源不同。

既然要做成交互工具，表达式健壮性也得跟上。原程序对非法输入的容忍度很低，比如输入小写字母、数字、运算符连续出现，都会导致不可预期行为。我的习惯是在去空格之后、建树之前加一道校验：遇到既不是大写字母、也不是|&~()的字符，直接报错退出并提示“只支持大写字母 A-Z 和逻辑运算符 | & ~ 以及括号”。

for (int k = 0; k < strlen(stri); k++) { char ch = stri[k]; if (!((ch >= 'A' && ch <= 'Z') || ch == '|' || ch == '&' || ch == '~' || ch == '(' || ch == ')')) { printf("非法字符 %c，仅支持大写字母和逻辑运算符\n", ch); return -1; } }

另外一个值得加的细节是括号配对检查。可以在建树前用计数器扫描一遍：遇(加一，遇)减一，最终计数不为 0 直接拒绝，避免括号不匹配时建树过程死循环或崩溃。这两个校验加起来不到二十行，但对程序的鲁棒性提升非常明显。

回想我自己做类似题目时的教训：一开始总是觉得“测试数据能过就行”，结果每次换一组新表达式就被打回原形。从那以后我每写完一个表达式处理程序，都强制走一遍“非法字符输入、括号不配对、变量跳跃命名、运算符连续出现”这四个用例，过了这关才敢说程序真的写完了。这份课程设计报告的价值不在于它的思路有多惊艳，而在于它把一个完整的调试路径记录了下来——优先级表怎么建、哪两个栈、哪种下标的坑、哪种情况要回退，全都有据可查。希望这份拆解能帮你在自己的实现里少踩几个坑。

本文还有配套的精品资源，点击获取