重言式判别_课程设计报告

编译原理课程设计说明书题目：编译器原型设计与开发院（系）：计算机科学与工程学院专业：计算机科学与技术目录1 引言 (1)1.1 设计概述 (1)1.2 设计目标 (2)1.3 小组分工 (3)2 开发过程 (3)2.1 词法分析 (3)2.1.1 消除白空格以及注释 (3)2.1.2 词法分析 (6)2.2 .语法分析 (8)2.2.1 递归下降手工编码 (8)2.2.2 first集合的计算 (8)2.2.3 左递归消除 (9)2.2.4 selection表自动生成 (10)2.2.5 LL(1)手工编码 (11)2.3 语义分析 (11)2.3.1 表达式求值LR(1) (11)2.3.2 四元式 (13)3 测试过程 (14)4 总结 (19)5 参考文献 (20)6 代码附录 (20)1引言编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都配有不止一个高级语言的编译程序，对有些高级语言甚至配置了几个不同性能的编译程序。

从功能上看，一个编译程序就是一个语言翻译程序。

语言翻译程序把一种语言（称作源语言）书写的程序翻译成另一种语言（称作目标语言）的等价程序。

一个编译程序的重要性体现在它使得多数计算机用户不必考虑与机器有关的繁琐细节，使程序员和程序设计专家独立于机器，这对于当今机器的数量和种类持续不断地增长的年代尤为重要。

编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。

将编译过程划分成词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段。

1.1设计概述编译原理程序结构框图词法分析词法分析是编译过程的第一个阶段。

这个阶段的任务是从左到右有一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词（也称单词符号或符号）。

这里所谓的单词是指逻辑上紧密相连的一组字符，这些字符基友具体含义。

比如标识符是由字母字符开头，后跟字母、数字字符的字符序列组成的一种单词。

数据结构报告—重言式判别1. 简介重言式判别是计算机科学中的一个问题，该问题主要是判断一个逻辑命题是否为重言式。

所谓重言式是指在所有情况下该命题的值都为真。

例如，命题“如果今天是下雨天，那么天空一定是阴天”就是一个重言式，因为不管今天是否下雨，只要天空没有被遮蔽，它就始终是阴天。

判别重言式对于很多应用有着重要的意义，例如逻辑推理、人工智能以及自然语言处理等。

在实际应用中，重言式判别可以作为问题求解的一种手段，计算机可通过判断一个命题是否为重言式，来判断某些问题的可解性，或者判断某个命题是否成立。

本文将介绍重言式的定义和重言式判别的基本方法，包括语义表达方法、真值表法和归结法等。

2. 语义表达法语义表达法是一种基于命题蕴含关系的判别方法。

该方法的基本思路是：将一个逻辑命题中的每个原子命题赋予真值，然后通过实际运算来判断该命题是否为重言式。

例如，对于一个命题P，我们可以将其中的原子命题A、B和C分别赋值为真和假，然后根据布尔运算规则，构造出该命题在这些赋值条件下的真假值运算结果，最终得出该命题的真值表。

3. 真值表法真值表法是一种通过构造命题的真值表进行判别的方法。

该方法的基本思路是：构造一个包含所有命题原子命题的真值表，并将运算结果列出来，判断是否在所有情况下结果为真。

例如，对于一个命题“如果今天是下雨天，那么天空一定是阴天”，我们可以将其中涉及到的两个原子命题“今天下雨”和“天空阴天”分别赋值为真和假，然后列出它们组合起来的所有情况的真值表，并通过计算来判断该命题是否为重言式。

4. 归结法归结法是一种基于逻辑归结理论的推理方法，用于判断一个命题是否是重言式。

该方法的基本思路是：将命题表示为逻辑符号的形式，然后通过逻辑推导的方法来判断它是否为重言式。

目前，归结法主要有两种方法，即前向归结和后向归结。

前向归结是一种基于正向推理的方法，主要是从前提推导出，然后进行归结。

后向归结是一种基于反向推理的方法，主要是从推导出前提，然后进行归结。

河海大学物联网工程学院编译原理课程实践学年学期2015-2016第二学期实验名称语法分析、语义分析作者1362810225刘云瞻组员刘云瞻华路授课班号6282506专业计算机科学与技术13级指导教师金永霞2016年6月目录1．引言 ..........................................................................................- 3 -1.1 实验目的 ..........................................................................- 3 -1.2 实践内容 ..........................................................................- 3 -2.算法设计.............................................................................- 3 -2.1 语法分析 ..........................................................................- 4 -2.1.1 生成（非）终结符表.............................................- 4 -2.1.2 构造FirstVT集和LastVT集...............................- 4 -2.1.4 算符优先分析.........................................................- 7 -2.2 语义分析 ....................................................................... - 10 -2.2.1 算术表达式和简单赋值语句的翻译 ................. - 10 -3. 运行结果与测试.................................................................... - 11 -3.1 运行结果 ........................................................................ - 11 -3.2 错误测试 ....................................................................... - 13 -4.心得体会.......................................................................... - 14 -1．引言1.1 实验目的通过使用高级语言实现部分算法加强对编译技术和理论的理解。

成绩：2016-2017学年第1学期《信息论》课程设计学院名称：班级学号：学生：教师：2016年12 月一、判定唯一可译码1. 任务说明输入：任意的一个码(即已知码字个数及每个具体的码字) 输出：判决结果（是/不是）输入文件:in1.txt ，含至少2组码，每组的结尾为”$”符 输出文件:out1.txt ，对每组码的判断结果说明：为了简化设计，可以假定码字为0，1串2. 实现原理判断方法：将码C 中所有码字可能的尾随后缀组成一个集合F ，当且仅当集合F 中没有 包含任一码字，则可判断此码C 为唯一可译变长码。

构成集合F ：首先观察码C 中最短的码字是否是其他码字的前缀。

若是，将其所有可能 的尾随后缀排列出。

就是将其他码字序列中截去与其最短码字相同的前缀 部分，将余下的序列为尾随后缀。

而这些尾随后缀又可能是某些码字的前 缀，或者最短码字又仍是这些尾随后缀的前缀，再将由这些尾随后缀产生 的新的尾随后缀列出。

然后再观察这些新的尾随后缀是否是某些码字的前 缀，或观察有否其他码字是这些新的尾随后缀的前缀，再将产生的尾随后 缀列出，依次下去，直至没有一个尾随后缀是码字的前缀或没有新的尾随 后缀产生为止。

这样，首先获得的是由最短码字能引起的所有尾随后缀。

接着，按照上述步骤将次短的码字、......所有码字可能产生的尾随后缀前部列出。

由此得到由码C 的所有可能的尾随后缀组成的集合F 。

参考算法伪代码：For all ,i j W W C ∈ doif i W 是j W 的前缀 then将相应的后缀作为一个尾随后缀放入集合0F 中 End if End forLoopFor all i W C ∈ doFor all j n W F ∈ doif i W 是j W 的前缀 then将相应的后缀作为一个尾随后缀放入集合1n F +中 Else if j W 是i W 的前缀 then将相应的后缀作为一个尾随后缀放入集合1n F +中End if End for End for i i F F ←If ,i i W F W C ∃∈∈ thenReturn falseElse if F 中未出现新的元素 thenReturn true End if//能走到这里，说明F 中有新的元素出现，需继续End loop3. 实现源码#include <iostream> #include <fstream> #include <stdio.h> #include <string.h> using namespace std;#pragma warning (disable :4996) char c[100][50]; //保存码字 char f[300][50]; //保存尾随后缀int N, sum = 0; //N 为码字的个数，sum 为尾随后缀个数 int flag; //判断是否唯一可译标志位//检测尾随后缀void patterson(char c[], char d[]) { int i, j, k; for (i = 0;; i++) { If (c[i] == '\0'&&d[i] == '\0')//两字符串一样长，跳出 break ; if (c[i] == '\0') //d 比c 长，将d 的尾随后缀放入f 中 { for (j = i; d[j] != '\0'; j++) f[sum][j - i] = d[j]; f[sum][j - i] = '\0'; for (k = 0; k<sum; k++) { if (strcmp(f[sum], f[k]) == 0) /*查看当前生成的尾随后缀在f 集合中是否存在*/ { sum--; break ; } } sum++; break ;}if (d[i] == '\0') //c比d长，将c的尾随后缀放入f中{for (j = i; c[j] != '\0'; j++)f[sum][j - i] = c[j];f[sum][j - i] = '\0';for (k = 0; k<sum; k++){if (strcmp(f[sum], f[k]) == 0) /*查看当前生成的尾随后缀在f集合中是否存在*/{sum--; break;}}sum++;break;}if (c[i] != d[i])//字符不一样了也退出（前缀不同）break;}}void main(){int k = 0, N = 0, m = 0, a[50], z = 0;a[m] = N; m++;fstream file1;file1.open("out1.txt");//码字读取FILE *file;file = fopen("in1.txt", "r+");int num = fgetc(file) - 48;for (int n = 0; n < num; n++){int i = 0, j;if (fgetc(file) == ' ')N += (fgetc(file) - 48);else N += (fgetc(file) - 48);a[m] = N; m++;fgetc(file);for (k; k < N; k++){for (int q = 0;; q++){char temp = fgetc(file);c[k][q] = temp;if (temp == ' ' || temp == '$'){c[k][q] = '\0';break;}}}//生成尾随后缀flag = 0;for (i = a[z]; i<N - 1; i++)//判断码本身是否重复for (j = i + 1; j<N; j++){if (strcmp(c[i], c[j]) == 0){flag = 1; break;}}if (flag == 1)//如果码本身有重复，就可以断定它不是唯一可译码{for (int y = a[z]; y < N; y++)file1 << c[y] << ' ';file1 << "不是唯一可译码。

学院计算机科学与技术系课程设计报告2016～2017学年第1学期课程数据结构与算法课程设计题目名称重言式的判别学生王芳学号1404011018专业班级计算机科学与技术14级1班指导教师红何立新2016年9月一、题目【问题描述】一个逻辑表达式如果对于其变元的任一种取值都为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式；然而，更多的情况下，既非重言式，也非矛盾式。

试写一个程序，通过真值表判别一个逻辑表达式属于上述哪一类。

【基本要求】(1) 逻辑表达式从终端输入，长度不超过一行。

逻辑运算符包括"|"，"&" 和"~"，分别表示或、与和非，运算优先程度递增，但可由括号改变，即括号的运算优先。

逻辑变元为大写字母。

表达式中任何地方都可以含有多个空格符。

(2) 若是重言式或矛盾式，可以只显示"True forever"，或"False forever"，否则显示"Satisfactible" 以及变量名序列，与用户交互。

若用户对表达式中变元取定一组值，程序就求出并显示逻辑表达式的值。

【测试数据】(1) (A|~A)&(B|~B)(2) (A&~A)&C(3) A|B|C|D|E|~A(4) A&B&C&~B(5) (A|B)&(A|~B)(6) A&~B|~A&B;O ,0;0,1;1,0;1,1 。

二、问题分析1、一个逻辑表达式如果对于其变元的任一种取值均为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式，若对于其变元的任一种取值既有真，又有假，则称其为可满足式。

写一个程序通过真值表判别一个逻辑表达式属于上述哪一类。

基本要求如下：1)逻辑表达式从终端输入，长度不超过一行。

课程设计心得体会《数据结构》课程设计按原计划要做两个星期，主要还是他比较难，相比之前大一的C++课程设计就难多了。

虽说数据结构中不要求具体使用那种语言来实现所要解决问题的办法，但内容上就多了起来。

但通过这次课程设计，使我对《数据结构》这门课程有了更深入的理解。

《数据结构》是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。

我做到课题是“重言式的判别”。

一开始拿到课题时，对于重言式我们在离散数学中学习过，所以第一印象还是感觉还是简单的，但是课程设计怎么可能会那么容易呢，还是有一定难度的，总的来说，个逻辑表达式如果对于其变元的任一种取值都为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式。

首先，建立栈和二叉树，先使用栈将逻辑表达式的变量进行存储，然后将栈中的元素作为二叉树的结点结构，然后根据优先级读取表达式建立二叉树，并通过逐个判断实现对重言式的判别。

总体设计思想就如上所述了。

通过这次课程设计，对平时学习的一些知识有了更加清晰地了解与掌握。

提高了我的综合运用所学知识的能力。

并对VC有了更深入的了解。

《数据结构》是一门实践性很强的课程，上机实习是对学生全面综合素质进行训练的一种最基本的方法，是与课堂听讲、自学和练习相辅相成的、必不可少的一个教学环节。

上机实习一方面能使书本上的知识变“活”，起到深化理解和灵活掌握教学内容的目的；另一方面，上机实习是对学生软件设计的综合能力的训练，包括问题分析，总体结构设计，程序设计基本技能和技巧的训练。

因此，在“数据结构”的学习过程中，必须严格按照老师的要求，主动地、积极地、认真地做好每一个实验，以不断提高自己的编程能力与专业素质。

在编写代码时，总会有这样那样的错误出现，这也很正常，平时没有学好，学的不够牢固，自然在运用的时候容易出错。

很多错误都是自己在写程序时不够细心，一些细节方面的东西没有注意到，导致的一些错误。

当然还有一些错误是自己自身知识储备的不足导致的。

重言式判别(数据结构课程设计) 收藏花了一下午在写这个重言式判别，可能是我孤陋寡闻了，总感觉这个名字怪怪的，就是判断一个永真式、永假式、可满足式了，书上面就要说是"重言式"。

判断这个所谓重言式，核心算法就是用真值表啦，试过所有取值。

具体代码如下(可能有bug)：有些难理解的我都有注释/**//******************************************************************** created: 2007/11/09author: 刺猬purpose: 判断表达式的属性永真式永假式可满足式*********************************************************************/#include<stdio.h>#include<stdlib.h>typedef struct exp...{char data;int weight;}express;express symbolrepresent[27];express originalexpression[50];int trueforever=0;int falseforever=0;int originalexpressionlength =0;int symbolrepresentlength=0;//欢迎屏幕void ShowWelcome()...{printf(" ");printf(" ");printf(" ");printf(" ");printf(" * * * * * * * * * * * * * * * * * * * * * * * * ");printf(" * 数据结构课程设计: * ");printf(" * * * * * * * * * * * * * * * * * * * * * * * * ");printf(" ");printf(" 06052711班");printf(" 刺猬");printf(" ");}//表达式分析器分析权值把| 权值设为1 &设为2 ~设为3//处理括号的思路是：遇见左括号把里面权值提升4 遇见右括号把权值减去4 这样可以处理多括号问题int analyse(express *p)...{int weight=0;int length=0;printf("请输入表达式，并以回车符为结束: ");printf("注意:请自行检查输入表达式的正确性");while(scanf("%c",&(p->data))&&p->data!=10)...{if(p->data>=97&&p->data<=122)p->data=p->data-32;switch(p->data)...{case '(':weight=weight+4; //遇见左括号把里面权值提升4p->weight=0; //注意括号权值为0break;case ')':weight=weight-4; //遇见右括号把权值减去4p->weight=0;break;case '|':p->weight=weight+1;break;case '&':p->weight=weight+2;break;case '~':p->weight=weight+3;break;default:p->weight=0; //imply the data is charbreak;}p++;length++;}}//查找表达式中权值最小的，作为子树的根节点int findMin(express *originalexpression,int start,int end)...{int key=0;int current=start;int location=0;while(!originalexpression[current].weight)...{key=originalexpression[current].weight;current++;}key=current>end?key:originalexpression[current].weight;location=current>end?0:current;while(current<=end)...{if(originalexpression[current].weight&&originalexpression[current].weight<key)...{location=current;key=originalexpression[current].weight;}current++;}return location;}//分析原表达式，提取所有变量就是把所有变量罗列在一个数组内int makeSymbolReprentArray(express *originalexpression)...{int length=0;int hashmap[26]=...{0};while(originalexpression->data!=10)...{if(originalexpression->data>=65&&originalexpression->data<=90)...{if(!hashmap[(int)(originalexpression->data-65)])...{hashmap[(int)(originalexpression->data-65)]=1;symbolrepresent[length].data=originalexpression->data;length++;}}originalexpression++;}}//查找每个变量所代表值0或1int findSymbolRepresent(char symbol)...{int location=0;while(symbolrepresent[location].data!=symbol)...{location++;}return symbolrepresent[location].weight;}//虚拟构建一个二叉树注意并没有真正构建不过可理解为建立一个树了算法核心是一个类似中序遍历二叉树int virtualCreateTree(express *originalexpression,int start,int end) //在以start和end的范围内建子树...{int key=0;if(start==end)//start==end 表明这个是叶子节点那么里面是个变量return findSymbolRepresent(originalexpression[start].data);else if(start>end)return 1; //start>end 处理~的特殊情况else...{key=findMin(originalexpression,start,end); //寻找最小权值作为子树根节点switch(originalexpression[key].data)...{case '|':return(virtualCreateTree(originalexpression,start,key-1)||virtualCreateTree(originalexpression,key +1,end));break;case '&':return(virtualCreateTree(originalexpression,start,key-1)&&virtualCreateTree(originalexpression,k ey+1,end));break;case '~': //注意~的处理实际上我是用的(1&&!右子树)return(virtualCreateTree(originalexpression,start,key-1)&&(!virtualCreateTree(originalexpression, key+1,end)));}}}//递归给所有变量赋值注意递归思想用回溯二叉树理解void recursion(express *symbolrepresent,int i,int length)...{if(i<length)...{symbolrepresent[i].weight=1; //当前变量取1recursion(symbolrepresent,i+1,length); //递归调用下一个变量symbolrepresent[i].weight=0; //当前变量取0recursion(symbolrepresent,i+1,length); //递归调用下一个变量}else //递归结束啦...{if(!trueforever||!falseforever) //注意这个处理当表达式出现可真情况和可假情况那么断定它是可满足式没必要做下去了...{switch(virtualCreateTree(originalexpression,0,originalexpressionlength-1))...{case 1:trueforever++;break;case 0:falseforever++;break;default :break;}}elsereturn ;}}//结果处理没啥说的void resultReturn(int symbolrepresentlength)...{int i=0;if(trueforever&&falseforever)...{printf("您输入的变量名序列为: ");while(i<symbolrepresentlength)...{printf("%c ",symbolrepresent[i].data);i++;}printf(" ");printf("satisfactible ");}else if(!trueforever)printf("falseforever ");elseprintf("trueforever ");}//用户自己设置值也没啥说的void userSetWeight()...{int i=0;printf("请依次为变量赋值,并以回车键结束: ");while(i<symbolrepresentlength)...{printf("%c: ",symbolrepresent[i].data);scanf("%d",&symbolrepresent[i].weight);i++;}if(virtualCreateTree(originalexpression,0,originalexpressionlength-1)) trueforever++;elsefalseforever++;}//主目录void mainFunctionMenus()...{int menu=0;printf("请选择您的变量设值方式: ");printf("1.计算机自动穷举");printf("2.用户指定设置");scanf("%d",&menu);if(1==menu)recursion(symbolrepresent,0,symbolrepresentlength);elseuserSetWeight();}int main()...{ShowWelcome();originalexpressionlength = analyse(originalexpression);symbolrepresentlength = makeSymbolReprentArray(originalexpression);mainFunctionMenus();resultReturn(symbolrepresentlength);//printf("%d",analyse(exp));//printf(" %d",findMin(exp,0,analyse(exp);))return 0;}本文来自CSDN博客，转载请标明出处：/littlehedgehog/archive/2007/11/13/1882625.aspx。

山东理工大学计算机学院课程设计（数据结构）班级姓名学号指导教师二○一一年一月二十日课程设计任务书及成绩评定课题名称重言式的判别Ⅰ、题目的目的和要求：1、设计目的巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。

（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。

（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。

2、设计题目要求：一个逻辑表达式如果对于其变元的任一种取值均为真，则成为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式，然而，更多的情况下，既非重言式，也非矛盾式。

写一个程序通过真值表判别一个逻辑表达式属于上述哪一类。

基本要求如下：（1）逻辑表达式从终端输入，长度不超过一行。

逻辑运算符包括“｜”、“＆”和“～”，分别表示或、与和非，运算优先程度递增，但可有括号改变，即括号内的运算优先。

逻辑变元为大写字母。

表达式中任何地方都可以含有多个空格符。

（2）若是重言式或矛盾式，可以只显示“True Forever”或“False Forever”，否则显示“Statisfactible”以及变量名序列，与用户交互。

若用户对表达式变元取定一组值，程序就求出并显示逻辑表达式的值。

Ⅱ、设计进度及完成情况日期内容1.10-1.11 选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。

1.12~1.14 创建相关数据结构,录入源程序。

1.17~1.19 调试程序并记录调试中的问题，初步完成课程设计报告。

1.20~1.21 上交课程设计报告打印版并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。

考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。

Ⅲ、主要参考文献及资料[1] 严蔚敏数据结构（C语言版）清华大学出版社 1999[2] 严蔚敏数据结构题集（C语言版）清华大学出版社 1999[3] 谭浩强 C语言程序设计清华大学出版社[4] 与所用编程环境相配套的C语言或C++相关的资料Ⅳ、成绩评定：设计成绩：（教师填写）指导老师：（签字）二○一一年一月二十一日目录第一章概述 (1)第二章系统分析 (2)第三章概要设计 (3)第四章详细设计 (5)第五章运行与测试 (11)第六章总结与心得 (12)参考文献 (13)第一章概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。

查重系统课程设计一、课程目标知识目标：1. 学生能够理解查重系统的基本概念和原理，掌握查重技术的基本流程。

2. 学生能够了解查重系统在学术、科研和商业领域的应用，认识其重要性和必要性。

3. 学生掌握查重系统的相关术语，如：相似度、抄袭、引用等，并了解它们之间的关系。

技能目标：1. 学生能够运用查重工具对文本进行自主查重，并分析查重结果。

2. 学生能够根据查重结果，进行文献引用的规范修改，提高学术诚信意识。

3. 学生通过小组合作，能够设计并实施简单的查重系统，提高实际操作能力。

情感态度价值观目标：1. 学生认识到查重系统在维护学术诚信、促进公平竞争方面的作用，树立诚信意识。

2. 学生在查重过程中，培养严谨、细致的学习态度，提高自我要求。

3. 学生通过查重系统的学习，增强对知识产权保护的意识，尊重他人成果。

本课程针对高年级学生，结合学科特点和教学要求，注重理论与实践相结合，旨在培养学生的查重意识，提高学术诚信和实际操作能力。

通过本课程的学习，使学生能够在未来的学术和职业生涯中，遵循诚信原则，规范引用他人成果，为我国科技创新和社会发展贡献力量。

的内容，以下为继续写作的内容：二、教学内容本课程教学内容围绕查重系统的原理、应用与实践展开，共分为三个部分：1. 查重系统原理与概念：- 理解信息检索、文本相似度计算等基本原理；- 学习查重系统的组成、工作流程和关键技术；- 掌握查重系统中的相关术语，如相似度、抄袭、引用等。

教学安排：2课时。

2. 查重系统的应用与案例分析：- 分析查重系统在学术、科研和商业领域的应用实例；- 学习查重结果的解读，分析查重系统在实践中的优缺点；- 探讨查重系统在维护学术诚信、促进公平竞争方面的作用。

教学安排：3课时。

3. 查重实践与操作：- 介绍常用查重工具的使用方法和操作技巧；- 指导学生运用查重工具进行文本查重，并进行结果分析；- 小组合作，设计并实施简单的查重系统，提高实际操作能力。

重⾔式判别题⽬参见：清华⼤学出版社的《数据结构题集（C语⾔版）》 P148 5.1刚开始时不知道从哪⾥下⼿，尤其是将输⼊的字符串序列建⽴成⼆叉树，⾃⼰想了半天越想越复杂，于是决定不浪费时间去⽹上直接找解题思路，发现通过构建加权字符数组的⽅法很不错，整体思路有了就动⼿实现吧，整个过程中对递归的应⽤很多，更加体会到了递归的美妙之处啊。

= v =。

中间⽐较纠结的是判别是否永真或永假，尤其是每进⾏⼀次运算会改变⼆叉树中原先的变元，最初没有考虑到这个结果很多都是直接跳到了结果，没有判断过程。

本来以为构造出⼆叉树之后后⾯的⼯作会简单⼀些，结果还是耗了很长时间。

= =||，⾼兴太早了麽，，，代码就堆在下⾯了。

代码1 #include <stdio.h>2 #include <stdlib.h>3 #include <string.h>45 typedef struct DutyElement6 {7char data;8int duty;9 }DutyElement;1011 DutyElement DutyArray[100]; //定义加权数组1213 typedef struct BiTNode14 {15char data;16struct BiTNode *lchild, *rchild;17 }BiTNode, *BiTree;1819void InitDutyArray(char *s, int n) //根据输⼊的序列初始化加权数组20{21int i, j;22for (i = 0; i < n; i++)23 {24 DutyArray[i].data = s[i];25switch (DutyArray[i].data) //分别赋权值26 {27case'~':28 DutyArray[i].duty = 3; break;29case'&':30 DutyArray[i].duty = 2; break;31case'|':32 DutyArray[i].duty = 1; break;33default:34 DutyArray[i].duty = 0; break;35 }36 }37for (i = 0; i < n; i++)38 {39if (DutyArray[i].data == '(') //是左括号的话则对运算符进⾏加权操作40 {41for (j = i; j < n; j++)42 {43if (DutyArray[j].duty != 0)44 DutyArray[j].duty += 5;45 }46 }47else48 {49if (DutyArray[i].data == ')') //右括号的话对运算符进⾏减权操作50 {51for (j = i; j < n; j++)52 {53if (DutyArray[j].duty != 0)54 DutyArray[j].duty -= 5;55 }56 }57 }58 }59 }6061int SearchMinDutyOperator(int a, int b) //寻找权值最⼩的运算符，即为⼆叉树的根节点62{63int i, n = a, duty = 1000;64for (i = a; i < b + 1; i++)65 {66if (DutyArray[i].duty > 0 && DutyArray[i].duty < duty)67 {68 n = i;69 duty = DutyArray[i].duty;70 }71 }72return n;73 }7475int ParenthesesCloesed(int a, int b) //判断序列是否在最外层有⼀对括号76{77int i, n = 0;78for (i = a; i <= b; i++)79 {80if (DutyArray[i].data == '(')81 n++;82if (DutyArray[i].data == ')')83 n--;84if (n == 0)85break;86 }87if (i == b)88return1;89else90return0;91 }9293 BiTree Create(int a, int b) //根据加权数组创建⼆叉树94{95 BiTree p;96if (DutyArray[a].data == '(' && DutyArray[b].data == ')' && ParenthesesCloesed(a, b) == 1) //去括号97 {98 a += 1;99 b -= 1;100 }101if (a > b)102 p = NULL;103else104 {105if (a == b)106 {107 p = (BiTNode *)malloc(sizeof(BiTNode));108 p->data = DutyArray[a].data;109 p->lchild = NULL;110 p->rchild = NULL;111 }112else113 {114int n;115 n = SearchMinDutyOperator(a, b);116 p = (BiTNode *)malloc(sizeof(BiTNode));117 p->data = DutyArray[n].data;118 p->lchild = Create(a, n - 1);119 p->rchild = Create(n + 1, b);120 }121 }122return p;123 }124125void AssignValue(BiTree T, char letter, char binary) //递归为对应的字母赋⼆进制字符126 {127if (T)128 {129if (T->data == letter)130 T->data = binary;131 AssignValue(T->lchild, letter, binary);132 AssignValue(T->rchild, letter, binary);133 }134 }135136int Calculate(BiTree T) //递归计算⼆进制字符⼆叉树137 {138switch (T->data)139 {140case'0':141return0;142case'1':143return1;144case'~':145return !Calculate(T->rchild);146case'&':147return (Calculate(T->lchild) & Calculate(T->rchild));148case'|':149return (Calculate(T->lchild) | Calculate(T->rchild));150 }151 }152153void main()154 {155 BiTree T;156int m = 0, n, i, j, k, length = 0, strlength, num = 1, flag;157char value[20] = {0};158char s[100] = {0};159char c, *str;160 str = (char *)malloc(sizeof(char) * 20);161for (i = 0; i < 20; i++)162 {163 *(str + i) = 0;164 }165 c = getchar();166 i = 0;167while (c != '\n')168 {169if (c != ' ')170 {171 s[i] = c;172 i++;173 }174 c = getchar();175 }176for (i = 0; i < 100; i++)177 {178if (s[i] == 0)179 {180 n = i; //n为输⼊序列的长度181break;182 }183 }184for (i = 0; i < n; i++)185 {186if (strchr(s, 'A' + i) != NULL)187 length++;188else189break;190 }191 length = i;192 InitDutyArray(s, n); //初始化加权数组193 T = Create(0, n - 1);194for (i = 0; i < length; i++)195 {196 AssignValue(T, 'A' + i, '0');197 }198 flag = Calculate(T);199for (i = 0; i < length; i++)200 {201 num *= 2;202 }203for (i = 0; i < num; i++)204 {205 T = Create(0, n - 1); //由于每运算⼀次会将原来的⼆叉树中的变元改变，所以得重新构造206 itoa(i, str, 2);207 strlength = strlen(str);208for (j = 0; j < length; j++)209 {210if (strlength - j - 1 >= 0)211 value[length - j - 1] = *(str + strlength - 1 - j);212else213 value[length - j - 1] = '0';214215 }216for (k = 0; k < length; k++)217 {218 AssignValue(T, 'A' + k, value[k]);219 }220if (Calculate(T) != flag)221 {222 printf("Satisfactible\n");223break;224 }225else226 {227if (i == num - 1 && flag == 1)228 {229 printf("True forever\n");230return;231 }232if (i == num - 1 && flag == 0)233 {234 printf("False forever\n");235return;236 }237 }238 }239for (i = 0; i < length; i++)240 {241 printf("%c ", 'A' + i);242 }243 printf("\n");244 c = getchar(); //输⼊对各字符的赋值，保存在value数组中245 i = 0;246while (c != ';')247 {248if (c != ',')249 {250 value[i] = c;251 i++;252 }253 c = getchar();254 }255 T = Create(0, n - 1); //重新构造⼆叉树256for (i = 0; i < length; i++)257 {258 AssignValue(T, 'A' + i, value[i]);259 }260 printf("The result is %d\n", Calculate(T));261 }。