计算命题演算公式真值数据结构C语言版实习报告

1、计算命题演算公式的真值李仙伟014072-281 .需求分析1.1. 命题演算公式由逻辑变量(其值为TRU或FALSE和逻辑运算符A(AND、V(OR和(NOT按一定规则所组成的公式。公式运算的先后顺序为、A、V,而括号()可以改变优先次序。1.2. 输入输出以人机对话的方式让用户输入要计算的命题表达式；计算出最后的真值并输到屏幕上。1.3. 测试数据：-(-a&b)|c)&d(boy&girl)father)&mother(5&99)|02 .概要设计2.1. 基本思想：利用二叉树计算公式的真值:第一步：利用堆栈将中缀形式的公式变为后缀形式；第二步：根据后缀形式，从叶结点开始构造相应的二叉树

2、；第三步：按后序遍历该树，求各子树之值，即每到达一个结点，其子树之值已经计算出来，当到达根结点时，求得的值就是公式之真值；逻辑变元的标识符不限于单字母，而可以是任意长的字母数字用；根据用户的要求显示表达式的真值表。2.2. 程序设计的概要图如下所示：2.3.抽象数据类型的定义及其相应的操作函数定义如下:/*定义一个堆栈SeqStackl,用来实现将输入的中缀表达式转换为后缀表达式*/typedefcharDataType;typedefstruct(DataTypestackMaxStackSize;inttop;SeqStack1;/*初始化SeqStack1,栈底为#*/voidStack

3、Initiate1(SeqStack1*S)/*将元素压入SeqStack1*/voidStackPush1(SeqStack1*S,DataTypex)/*SeqStack1出栈*/voidStackPop1(SeqStack1*S,DataType*x)/*取SeqStack1的栈顶元素*/intStackTop1(SeqStack1S,DataType*d)/*定义链式堆栈LSNode用于检测表达式的括号匹配*/typedefstructsnode(DataTypedata;Structsnode*next;LSNode;/*初始化堆栈LSNode*/voidStackInitiate(

4、LSNode*head)/*判断堆栈LSNod睨否为空的函数，空返回0,否则返回1*/intStackNotEmpty(LSNode*head)/*LSNode入栈函数*/intStackPush(LSNode*head,DataTypex)/*LSNode出栈函数*/intStackPop(LSNode*head,DataType*d)/*LSNode取栈顶元素*/intStackTop(LSNode*head,DataType*d)/*撤消LSNod呦态中t1空间*/voidDestroy(LSNode*head)/*检测输入表达式白括号匹配函数*/voidExpIsCorrect(cha

5、rexp)/*定义二叉机t的结点BiTreeNode*/typedefstructNodeDataTypedataMaxStackSize;structNode*leftChild;structNode*rightChild;structNode*parent;BiTreeNode;/*初始化BiTreeNode的根结点*/voidInitiate(BiTreeNode*root)/*将BiTreeNode结点压入堆栈2*/voidStackPush2(SeqStack2*S,BiTreeNode*x)/*逆时针打印BiTreeNode*/voidprint(BiTreeNode*bt,int

6、n)/*定义一个顺序堆栈SeqStack2,用于构造二叉树时对结点的保存*/typedefstructBiTreeNode*SaveMaxStackSize;inttop;SeqStack2;/*初始化SeqStack2*/voidStackInitiate2(SeqStack2*S)/*SeqStack2出栈*/BiTreeNode*StackPop2(SeqStack2*S)/*将待求表达式子转换为后缀形式*/intConvert(charaMaxSize1,charbMaxSize1MaxSize2,SeqStack1*S,intn)/*根据上面转换的表达式的后缀形式，构造相应的二叉树*

7、/BiTreeNode*BuildTree(charbMaxSize1MaxSize2,intn)/*后序遍历该树，并且每到达一个结点时候，计算其子树之值，当到达根结点时，求得的值就是公式之真值。*/intPostOrder(BiTreeNode*t,intcMaxSize1,charbMaxSize1MaxSize2,intn)/*主函数*/voidmain()3 .详细设计#include#include#includetypedefcharDataType;#includetypedefstructsnode/*定义链式堆栈的结点，用于检测表达式的括号匹配*/DataTypedata;s

8、tructsnode*next;LSNode;voidStackInitiate(LSNode*head)/*初始化堆栈*/if(*head=(LSNode*)malloc(sizeof(LSNode)=NULL)exit(1);(*head)-next=NULL;intStackNotEmpty(LSNode*head)/*检测堆栈是否为空的函数，若为空，返回0,否则返回1*/if(head-next=NULL)return0;elsereturn1;intStackPush(LSNode*head,DataTypex)/*将元素入栈*/LSNode*p;if(p=(LSNode*)mall

9、oc(sizeof(LSNode)=NULL)printf(t内存空间不足无法插入！n);return0;p-data=x;p-next=head-next;head-next=p;return1;)intStackPop(LSNode*head,DataType*d)/*出栈*/(LSNode*p=head-next;if(p=NULL)(printf(t堆栈空出错n);return0;)head-next=p-next;*d=p-data;free(p);return1;)intStackTop(LSNode*head,DataType*d)/*取栈顶元素*/(LSNode*p=head-

10、next;if(p=NULL)(printf(t堆栈已空出错n);return0;)*d=p-data;return1;)voidDestroy(LSNode*head)(LSNode*p,*p1;p=head;while(p!=NULL)(p1=p;p=p-next;free(p1);/*检测输入表达式的括号匹配函数*/voidExplsCorrect(charexp)(LSNode*head;inti=0;charc;StackInitiate(&head);while(expi)/*表达式没读完时，执行while循环*/(if(expi=()StackPush(head,expi);/*

11、遇到左括号(将其进栈*/elseif(expi=)&StackNotEmpty(head)&StackTop(head,&c)&c=()StackPop(head,&c);/*栈顶元素为(且当前元素为)时，出栈，继续读下面的字符*/elseif(expi=)&StackNotEmpty(head)&StackTop(head,&c)&c!=()/*栈顶元素不为(且当前元素为)时，输出左右括号不匹配，退出重新输入*/(printf(nt左右括号配对次序不正确！n);exit(1);)elseif(expi=)&!StackNotEmpty(head)/*当前元素为)但是堆栈已空时候，输出右括号多

12、于左括号，退出程序重新输入*/(printf(nt右括号多于左括号！n);exit(1);)i+;)if(StackNotEmpty(head)/*此时若堆栈非空，则输出左括号多于右括号，退出程序重新输入*/(printf(nt左括号多于右括号！n);exit(1);)elseprintf(nt左右括号匹配正确n);/*若此时堆栈为空，表明输入的表达式左右括号匹配正确，继续执行下面的程序*/printf(n);printf(-n);printf（t其后缀表达式子为：n）;typedefstruct(DataTypestack1000;inttop;SeqStack1;/*用来实现将输入的中缀表

13、达式转换为后缀表达式*/typedefstructNode(DataTypedata1000;structNode*leftChild;structNode*rightChild;structNode*parent;BiTreeNode;/*定义二叉树的结点*/typedefstruct(BiTreeNode*address1000;/*结点的保存*/inttop;SeqStack2;定义成树结点的指针，方便下面构造二叉树时，对voidStackInitiate1(SeqStack1*S)/*(S-stack0=#;S-top=1;初始化，栈底为#*/voidStackPush1(SeqSta

14、ck1*S,DataTypex)/*(S-stackS-top=x;S-top+;voidStackPop1(SeqStack1*S,DataType*x)/*(S-top-;*x=S-stackS-top;将元素压入堆栈1*/弹出堆栈1的栈顶元素*/intStackTop1(SeqStack1S,DataType*d)(/*取堆栈1的栈顶元素*/if(S.topleftChild=NULL;(*root)-rightChild=NULL;(*root)-parent=NULL;)voidprint(BiTreeNode*bt,intn)/*逆时针打印二叉树*/(inti,j,m;if(bt=

15、NULL)return;print(bt-rightChild,n+1);for(i=0;i=0)(printf(-);m=strlen(bt-data);for(j=0;jdataj);printf(n);)print(bt-leftChild,n+1);)初始化堆栈2*/voidStackInitiate2(SeqStack2*S)/*(S-top=0;voidStackPush2(SeqStack2*S,BiTreeNode*x)/*将二叉树结点压入堆栈2*/(S-addressS-top=x;S-top+;)BiTreeNode*StackPop2(SeqStack2*S)/*从堆栈2

16、中弹出栈顶元素*/(BiTreeNode*x;S-top-;x=S-addressS-top;returnx;)将待求表达式子|ai=)|ai=#)ai=&|ai=(此时堆栈和当前都为intConvert(chara500,charb500100,SeqStack1*S,intn)/*转换为后缀形式*/(inti,j,k=0;charcharacter;for(i=0;in;i+)(if(ai=|ai=|ai=&|ai=(while(ai=|ai=|ai=)|ai=#)(StackTop1(*S,&character);if(character=#&ai=#)returnk;/*#时结束算法*

17、/elseif(character=#&ai!=#)|(character=|&ai=-)|(character=|&ai=&)|(character=|&ai=()|(character=&ai=-)|(character=&ai=()|(character=&ai=()|(character=(&ai!=)(StackPush1(S,ai);/*当中缀表达式当前运算符优先级较高时，进栈*/break;)elseif(character=(&ai=)/*(和)相遇时，将(退栈，接着读下面的*/(StackPop1(S,&character);break;)else(StackPop1(S,&

18、character);/*当栈顶元素优先级较高时，退栈*/bk0=character;bk1=0;k+;continue;)continue;)if(ai!=&ai!=|&ai!=&ai!=(&ai!=)&ai!=#)(j=0;while(ai!=&ai!=|&ai!=&ai!=(&ai!=)&ai!=#)(bkj=ai;/*当前为变量时，直接存入二维数组b中*/j+;i+;)i-;bkj=0;/*表示该行结束*/k+;)return0;)BiTreeNode*BuildTree(charb500100,intn)(inti;BiTreeNode*p,*q,*o;SeqStack2s;Stac

19、kInitiate2(&s);for(i=0;idata,bi);/*p-rightChild=NULL;/*p-leftChild=NULL;p-parent=NULL;if(bi0=)(q=StackPop2(&s);p-rightChild=q;/*q-parent=p;StackPush2(&s,p);elseif(bi0=|bi0=&)(q=StackPop2(&s);/*o=StackPop2(&s);/*q-parent=p;o-parent=p;p-leftChild=o;p-rightChild=q;StackPush2(&s,p);/*else(StackPush2(&s,

20、p);将变量赋给结点P的数据域*/初始化左右子树以及双亲指针*/将弹出后的结点作为右孩子*/弹出q作为右孩子*/弹出0作为左孩子*/根结点入栈*/p=StackPop2(&s);/*弹出构造好的二叉数的根结点指针，并返回*/returnp;intPostOrder(BiTreeNode*t,intc500,charb500100,intn)/*/(intn1,n2,i;后序遍历该树if(t!=NULL)(n1=PostOrder(t-leftChild,c,b,n);n2=PostOrder(t-rightChild,c,b,n);if(t-data0=)/*(if(n2=0)return1;

21、if(n2=1)return0;)遇到将值置反*/elseif(t-data0=&)/*遇到&只有两个都为真时才为真*/(if(n1=1&n2=1)return1;elsereturn0;)elseif(t-data0=|)/*遇到|只有两个都为假时才为假*/(if(n1=0&n2=0)return0;elsereturn1;)else(for(i=0;idata)break;/*当该结点数据域为变量时*/)returnci;/*直接返回该变量的真值*/)return-1;voidmain()(数组用来存放变量的真值*/chara500,b500100;inti,j,n,answer,flag

22、,c500;/*ccharm=y;SeqStack1S;BiTreeNode*P;printf(nn);printf(tttt计算命题演算公式);printf(nn);printf(ttt&、|、分别代表与、或、非)；printf(n)；while(m=y)(Initiate(&P);StackInitiate1(&S);printf(nt请输入待求表达式，例如：2(2&0)|5n);printf();printf(nt用户输入为：)；scanf(%s,a);printf(n);printf(nt现在检测其括号匹配：n);ExplsCorrect(a);n=strlen(a);an=#;n=C

23、onvert(a,b,&S,n+1);/*此时n的值为二维数组b的行数目*/*测试输出后序表达式*/printf(nt);for(i=0;in;i+)(for(j=0;bij!=0;j+)/*0为二维数组b每行的结束标志*/(printf(%c,bij);printf(n);P=BuildTree(b,n);/*测试打印二叉树*/printf(n);printf(t构造的二叉树结构为：n);print(P,0);printf(n);while(1)(printf(nt请为变量赋值nn);for(i=0;in;i+)(flag=0;if(bi0!=&bi0!=&bi0!=T)(for(j=0;j

24、i;j+)(if(!strcmp(bi,bj)(flag=1;break;/*有重复变量时flag为1,且找到第一个重复变量bj*/if(flag=0)(printf(t请设定上述待求表达式中的变量%s的真值(0or1?):nt,bi);/*给变量赋真值0或1*/scanf(%d”,&ci);printf(n);else(ci=cj;/*把重复出现的变量都用第一次的值赋值*/elseci=-1;answer=PostOrder(P,c,b,n);printf(nt该表达式的最后结果为：%dn,answer);printf(nnt0.退出该表达式子的真值计算1.重新输入表达式各变量的真值计算：n

25、t);scanf(%d,&i);if(i=0)break;printf(nty:继续下一个表达式的计算n:退出程序bt);printf(ntyorn?nt);scanf(%c,&m);while(m!=y&m!=n)printf(twronginput!n);printf(tPleasechooseyorn!nt);scanf(%c,&m);printf(nnn);4、使用说明此程序中&、|、分别代表代表与、或、非运算符，输入格式如同离散数学中真值表达式的输入，比如（!a&b）&d。注意括号是否匹配（程序中有检测）和提示，注意看界面；输入完成后，按Enter执行，屏幕会输出相应的后缀表达式和建

26、立的二叉数，接着，跟着提示，为表达式中的各个变量赋予初值（0或1）,按Enter执行输出结果；若要继续执行该表达式子的变量的不同真值情况下的表达式的真值，输入1;退出该表达式的计算请输入0,继续下一组表达式的计算，输入y,退出整个程序输入n。5、调试分析程序出的错多为分号和括号多少，经简单的调试后编译和链接无错误，如下所示：本程序中主要三个函数的时间空间复杂度如下：intConvert();时间复杂度O(n)空间复杂度O(n)BiTreeNode*BuildTree();时间复杂度0(2An)空间复杂度O(n)PostOrder();时间复杂度0(2An)空间复杂度0(n)6、测试结果测试数据：(a&b)|c)&d(boy&girl)|father)&mother(