逻辑命题公式计算

1、-. z.题号：第一题题目：电梯模拟1，需求分析：计算命题演算公式的真值所谓命题演算公式是指由逻辑变量其值为TRUE或FALSE和逻辑运算符AND、OR和NOT按一定规则所组成的公式蕴含之类的运算可以用、和来表示。公式运算的先后顺序为、，而括号可以改变优先次序。一个命题演算公式及各变量的值，要求设计一个程序来计算公式的真值。要求：1利用二叉树来计算公式的真值。首先利用堆栈将中缀形式的公式变为后缀形式；然后根据后缀形式，从叶结点开场构造相应的二叉树；最后按后序遍历该树，求各子树之值，即每到达一个结点，其子树之值已经计算出来，当到达根结点时，求得的值就是公式之真值。2逻辑变元的标识符不限于单字母，

2、而可以是任意长的字母数字串。3根据用户的要求显示表达式的真值表。2，设计：2.1 设计思想：，数据构造设计： (1) 线性堆栈1的数据构造定义 typedef struct DataType stack Ma*StackSize; int top; /* 当前栈的表长*/ SeqStack;用线性堆栈主要是用来存储输入的字符，它的作用就是将中缀表达式变成后缀表达式。(2) 线性堆栈2的数据构造定义typedef struct BiTreeNode *stack Ma*StackSize;int top; /* 当前栈的表长*/ TreeStack;这个堆栈和上面的堆栈的唯一不同就是它们存储的数

3、据的类型不同，此堆栈存储的是树节点，它的作用是将后缀表达式构成一棵二叉树。树节点数据构造定义 typedef struct Node DataType data; struct Node *leftChild; struct Node *rightChild; BiTreeNode; 算法设计详细思路如下： 首先实现将中缀表达式变成后缀表达式： 在将中缀表达式变成后缀表达式的时候会用到堆栈，因此首先需要初始化一个堆栈。又由于逻辑变元可能是字符也可能是字符串，所以它又不同于将单字符的逻辑变元的中缀表达式变成后缀表达式。我的设计是这样的，我将中缀表达式变成后缀表达式的过程分成了两部：化简将一维的复

4、杂的中缀表达式变成一维的简单的中缀表达式，并将字符串逻辑变元存放在二维数组中，转化将化简后的中缀表达式变成后缀表达式。1化简：先用一个字符数组存放输入的中缀表达式表达式以#号完毕，然后将一维的中缀表达式中的字符串逻辑变元用一个字符进展标识，这样我们就可以将原来复杂的中缀表达式变成熟悉而又简单的中缀表达式，同时用二维数组存放那些字符串逻辑变元。实现的过程就是首先扫描一维中缀表达式，如果遇到逻辑符号，则记住这个逻辑符号在数组中的相对位置用一个变量存放，然后继续扫描中缀表达式直到再次遇到逻辑符号，再一次记住它在中缀表达式中的相对位置，这两个逻辑符号之间的局部就是一个完整的逻辑变元，将这个字符串逻辑变

5、元用一个字符代替并将这个字符串逻辑变元保存在二维数组中。这个过程的实现我把它放在change()函数中。2转化：在实现该功能时，首先需要定义各符号的优先级，即：( 和 ) 的优先级最高；!逻辑非号的优先级次之；&逻辑与号的优先级又低一级，|逻辑或号的优先级跟低；# 他不是逻辑符号，只是为了方便使用堆栈而设置的优先级最低，接着将 #压入堆栈。在这之后就是正式的转化了，其过程为：当读到的是逻辑变元时直接输出，并保存到保存后缀表达式的数组中，当读到的单词为运算符时，令*1为当前栈顶运算符的变量，*2为当前扫描到的简单中缀表达式的运算符的变量，把当前读入的单词赋予变量*2，然后比拟*1和*2的优先级。

6、假设*1的优先级高于*2的优先级，将*1退栈作为后缀表达式的一个单词输出，然后接着比拟新的栈顶运算符*1的优先级与*2的优先级；假设*1的优先级低于*2的优先级，将*2的值进栈，然后接着读下一个单词；假设*1的优先级等于*2的优先级且*1为，*2为，将*1退栈，然后接着读下一个单词；假设*1的优先级等于*2的优先级且*1为#，*2为#，算法完毕。这个过程我把它放在InToPost()函数中。 然后用后缀表达式构造出二叉树：在这个过程中，我用到了之前所定义的存放树的堆栈。具体实现为：扫描后缀表达式，如果遇到逻辑变元然后将这个变元变成一个树节点，它的实现就是将该逻辑变元赋给树的data域，然后将它

7、的左右子树赋为NULL，然后将这个树节点压入相应的堆栈；接着继续扫描，如果遇到的是单目运算符非号！也将它构造成一个树节点然后从堆栈里面弹出一个树形节点，将弹出的元素的作为它的左子树，右子树设置为NULL，然后将这个树节点压入相应的堆栈；如果扫描到的是双目运算符与号&或者或号|将它也构造成一棵树，然后将这个树节点压入相应的堆栈，然后从栈中弹出两个元素，一个作为它的左子树，一个作为它的右子树，如此重复nn为后缀表达式的长度次。这个过程我把它放在Maketree()函数中。 最后打印真值表：打印真值表也用到了前面的简单的后缀表达式，其实现的根本思想为和构造二叉树差不多，它实现了每到一个根节点就计算一

8、个运算的值。在打印之前需要统计字符的个数，有m个字符则要打印2m行，因为他有这么多情况。具体实现为：用一个字符型的数组来存放每个元素的一次取值，然后扫描后缀表达式，如果遇到逻辑变元就通过这个标识将相应的取值赋给它，然后它压入堆栈；接着继续扫描，如果遇到的是单目运算符非号！则从堆栈里面弹出一个元素，并对它进展非运算，然后又将这个运算后的值压入堆栈；如果扫描到的是双目运算符与号&或者或号|则从栈中弹出两个元素，并对这两个元素进展相应的运算，然后将这个运算后的值压入堆栈，如此重复nn为后缀表达式的长度次。这个过程我把它放在Print()函数中。其中第一，二过程的流程图描述分别为：开场扫描后缀表达式扫

9、描后缀表达式扫描到的是逻辑变元？扫描到*2是逻辑变元？输出YesYes栈顶元素的优先级高？NoNo构造成树节点并进栈取栈顶元素*1双目运算符单目运算符构造成树节点从栈中弹出两个元素作为其左右子树构造成树节点从栈中弹出一个元素作为其左子树 No进栈小于出栈Yes进栈进栈Yes完毕*1,*2都为#*1为(,*2we为)No2.2 设计表示：, 函数调用关系及函数说明： main()Maketree()Print()InToPost()change()StackPush1()StackPop1StackTop()StackPop()StackPush()Precede()StackPop()Stac

10、kPush() change()函数原型为： void change(char prefi*Str1,char prefi*Str,int length,char store10,int* row,int* k )该函数含有有六个参数，其中 prefi*Str1为用户输入的中缀表达式，prefi*Str为即将转化成为的简单中缀表达式，length为二维数组中存放的各个字符串的的长度store10用来存放中缀表达式中的逻辑变元，row就是逻辑变元的个数，k简化后的中缀表达式的长度。该函数的功能就是将复杂的中缀表达式变成简单的中缀表达式。 InToPost()函数原型为：void InToPost

11、(char prefi*Str,char postfi*Str,SeqStack* myStack,int* n,int k)该函数函数有五个参数 prefi*Str为中缀表达式，postfi*Str为简化后的后缀表达式，myStack为在转化过程中用到的堆栈，n为后缀表达式的字符长度，k为中缀表达式的字符长度。该函数的功能就是将简单的中缀表达式变成简单的后缀表达式。Maketree()函数原型为： void Maketree(BiTreeNode *root,TreeStack* myTree,char postfi*Str,int n)该函数共有四个参数，其中root为所建立的树的根节点，

12、myTree是在构造树时所用到的堆栈，另外两个参数和前面的同名参数具有一样意义。这个函数的功能就是将简单的中缀表达式变成简单的后缀表达式。Precede()函数原型为： DataType Precede(DataType *1,DataType *2)该函数有两个参数，返回值类型为DataType型，其中*1和*2就是要进展优先级比拟的两个两个字符。*1为栈顶元素，*2为扫描到的元素。该函数的功能就是比拟*1和*2的优先级并将比拟结果返回给调用函数。 Print()函数原型为：void Print(char postfi*Str,char store10,int length,int row,

13、int n,SeqStack* myStack)该函数有六个参数，其中myStack是在输出真值表过程中要用到的堆栈，其余的参数和前面介绍的函数中的同名参数具有一样的意义。该函数的功能就是打印真值表。 函数接口说明：函数的调用关系在上面的图中已经显示出来了，整个程序就是由一些子函数的集合，他们之间按所要实现的功能不同而调用不同的函数。在这些函数中除主函数外，其它函数的级别一样。2.3详细设计：，定义所需要的构造体，前面已经介绍了；2，我将中缀表达式变成后缀表达式的过程分成了两部：化简将一维的复杂的中缀表达式变成一维的简单的中缀表达式，并将字符串逻辑变元存放在二维数组中，转化将化简后的中缀表达式

14、变成后缀表达式。其中化简局部将要用伪代码描述为while(prefi*Str1m!=#)扫描中缀表达式while(prefi*Str1m不为运算符)继续扫描，直到扫描到运算符;扫描到运算符后 构造简化的中缀表达式; 得到这个字符串的长度; 将这个字符串存放在store10中; 转化局部用伪代码描述为： 循环扫描中缀表达式 if(扫描到逻辑变元) 保存到后缀表达式中；elseStackTop(myStack,&*);res=Precede(*,扫描到的运算符);if(res=) *退栈；if(res=leftChild=*1; 4，打印二叉树，其根本思想就是每到一个根节点就计算一个值，如此重复，

15、直到总根节点，用伪代码简单描述为： 循环赋值if(扫描到逻辑变元) 赋值进栈；elseif(扫描到双目运算符) 从栈中弹出两数对两数进展相应的运算;将运算构造进栈；;else 从栈中弹出两数; 对两数进展非运算; 将运算构造进栈; 每循环一次输出一个构造; 3，调试分析：，调试过程中遇到的问题与解决方案：这个题我个人觉的是这几个中最麻烦的一个，因为它有几个难点去分析与实现：首先就是中缀表达式中的逻辑变元不是单个字符而是一些字符串，这样在将中缀表达式转化成后缀表达式的时候就会比拟麻烦，起初我也不太清楚该怎么处理他，后来经过一番分析与调试后，我觉得用二维数组存放比拟好，那样实现起来就会比拟简单，当

16、然虽然这么说，其实实现起来也还是有一定的困难的，比方怎样去找到一个完整的字符串逻辑变元，找到之后又怎样存放等等。然后再就是构造树，在构造树时要用到堆栈，但是前面用到的堆栈的数据类型和此时用到的又有很大的差异，在此时又要想到再换一个类型的堆栈，同时在构造树的时候有要找到适宜的算法最后就是真值表的打印，对这一模块的实现最容易想到的就是有几个逻辑变元就进展几次循环，每一重循环对应着一个变量的取值。但是经过分析这显然是行不通的，因为在事先我们并不知道会有多少个变元。最后我用到的方法就是那种最原始的方法，用一重循环去实现，每重循环都会有一个值，将这个值反复进展对2取余和对2进展整除，将取余后的值赋给相应

17、的变元。这样总共循环2的变元素的n次方次即可。当然在完成这个程序时还遇到其它的很多的问题，这里就不多进展列出了，最后我在声明一下这个程序的一个缺陷，他在进展逻辑变元数统计的时候没有对两个一样的变元进展识别。，算法的时空复杂度分析： 本次程序的完成除书上的那些头文件外，其它的算法都是自己提供，对于我自己写的那些函数，比方change()函数，InToPost()函数，Print()函数，Maketree()函数他们的时间复杂度均为o(n),而对于change()函数其空间复杂度为o(1),其它的三个函数，由于他们都用到了堆栈这个数据构造他们的空间复杂度都是o(n).4，用户手册： 本程序经过编译

18、，连接后，运行时只需要用户输入一个中缀表达式，也即用户想要进展的逻辑运算的表达式。这里有三点需要要提醒用户： 1，在输入表达式时&表示逻辑与；|号表示逻辑或，！表示逻辑非。在输入中缀表达式后程序将自动执行并输出构造，用户不需进展干预； 2，在本程序的书写中我定义了一个最多的逻辑变元的数量为十个，用户在输入表达式时应该注意输入，不要超过这个界限。 3，用户在输入完所要进展运算的表达式后要记得以#号结尾，#号是判断输入完毕的标识，如果用户没有以#号完毕，则程序的运行结果将会出错，这时用户必须重新对程序进展编译连接，然后按照要求输入表达式。5，测试数据及测试结果： 由于用户的不同输入将对应着不同的结

19、果，这里我仅随便输入一个逻辑表达式以供用户参考：请输入表达式(以#号完毕)： !aaa&(bb|cd1)&wq|d#将中缀表达式变成后缀表达式为：aaa ! bb cd1 | & wq & d |打印构造的二叉树为： -d-| -wq -& -! -aaa -& -cd1 -| -bb二叉树的后序遍历为：bb cd1 | aaa ! & wq & d |打印真值表为：aaa bb cd1 wq d 运算结果0 0 0 0 0 01 0 0 0 0 00 1 0 0 0 01 1 0 0 0 00 0 1 0 0 01 0 1 0 0 00 1 1 0 0 01 1 1 0 0 00 0 0 1

20、 0 01 0 0 1 0 00 1 0 1 0 11 1 0 1 0 00 0 1 1 0 11 0 1 1 0 00 1 1 1 0 11 1 1 1 0 00 0 0 0 1 11 0 0 0 1 10 1 0 0 1 11 1 0 0 1 10 0 1 0 1 11 0 1 0 1 10 1 1 0 1 11 1 1 0 1 10 0 0 1 1 11 0 0 1 1 10 1 0 1 1 11 1 0 1 1 10 0 1 1 1 11 0 1 1 1 10 1 1 1 1 11 1 1 1 1 16，源程序清单：caculate.cpp /程序源文件BiTree.h /树的相关操作

21、的头文件BiTreeTraverse.h /树的遍历的头文件caozuo.h /自己提供的为实现所要求的功能而添加的头文件pare.h /比拟运算符优先级的头文件SeqStack.h /线性堆栈的有关操作的头文件TreeStack.h /为构造树而用到的头文件/caculate.cpp 程序源文件#include #include #include #define Ma*StackSize 50#include SeqStack.h#include BiTree.h#include TreeStack.h#include pare.h#include BiTreeTraverse.h#incl

22、ude caozuo.h/void main()int i,j,n=0,k=0,row=0;SeqStack myStack;char prefi*Str100,prefi*Str1100;char postfi*Str100;char store1010;int length10,inde*=0; BiTreeNode *root; TreeStack myTree;StackInitiate(&myStack);StackPush(&myStack,#);printf(请输入表达式(以#号完毕)： );scanf(%s,prefi*Str1);change(prefi*Str1,prefi

23、*Str,length,store,&row,&k); /k是中缀表达式的字符长度InToPost(prefi*Str,postfi*Str,&myStack,&n,k);/ printf(将中缀表达式变成后缀表达式为： n);for(i=0;i=A & postfi*Stri=Z) for(j=0;jleftChild,store,length);printf(n);/打印真值表printf(n打印真值表为： n);Print(postfi*Str,store,length,row,n,&myStack);/caozuo.h 头文件void change(char prefi*Str1,ch

24、ar prefi*Str,int length,char store10,int* row,int* k )int j,t,m=0;char ch=A;while(prefi*Str1m!=#)j=m;while(prefi*Str1m!=& & prefi*Str1m!=| & prefi*Str1m!=! & prefi*Str1m!=( & prefi*Str1m!=) & prefi*Str1m!=#)m+;if(m!=j) prefi*Str(*k)+=ch; ch+=1; for(t=j;tm;t+) length*row=m-j; store*rowt-j=prefi*Str1t

25、; (*row)+;prefi*Str(*k)+=prefi*Str1m;m+;if(prefi*Str1m=& | prefi*Str1m=| | prefi*Str1m=! | prefi*Str1m=( | prefi*Str1m=) | prefi*Str1m=#) prefi*Str(*k)+=prefi*Str1m;else m-;if(prefi*Str1m!=#) m+;elsebreak;/void InToPost(char prefi*Str,char postfi*Str,SeqStack* myStack,int* n,int k)int i;DataType res

26、,*;for(i=0;i=A & prefi*Stri)while(res=) StackPop(myStack,&*); postfi*Str(*n)+=*;StackTop(myStack,&*);res=Precede(*,prefi*Stri);if(res=)StackPush(myStack,prefi*Stri);if(res= & *=()StackPop(myStack,&*);if(res= & *=#)break;/void Print(char postfi*Str,char store10,int length,int row,int n,SeqStack* mySt

27、ack)char *ptr;DataType *,v1,v2;int i,j,t,total=1;int value,value1,value2,value3;for(i=0;irow;i+)for(j=0;jlengthi;j+)printf(%c,storeij);printf( );printf(运算结果);printf(n);for(i=0;irow;i+)total*=2;ptr=(char* )malloc(sizeof(char)*row); for(i=0;itotal;i+)t=i;for(j=0;jrow;j+) ptrj=t%2+48; printf(%c ,ptrj);

28、 t=t/2;for(j=0;j=A & postfi*Strj=Z)value=postfi*Strj-A;StackPush(myStack,ptrvalue);elseif(postfi*Strj!=!) StackPop(myStack,&v1);value1=v1-48;StackPop(myStack,&v2);value2=v2-48;switch(postfi*Strj) case &: value3=value1&value2; break;case |: value3=value1|value2; break;*=value3+48;StackPush(myStack,*)

29、;else StackPop(myStack,&v1);value1=v1-48;value3=!value1;*=value3+48;StackPush(myStack,*);StackPop(myStack,&*);printf( %c,*);printf(n);/void Maketree(BiTreeNode *root,TreeStack* myTree,char postfi*Str,int n)int i; BiTreeNode *p,*1,*2; for(i=0;i=A & postfi*Stridata=postfi*Stri;p-leftChild=NULL;p-rightChild=NULL;StackPush1(myTree,p);else p=(BiTreeNode *)malloc(sizeof(BiTreeNode); *1=(BiTreeNode *)malloc(sizeof(BiTreeNode); *2=(BiTreeNode *)malloc(sizeof(BiTreeNode);if(postfi*Stri!=!) StackPop1(myTree,&*1); StackPop1(m