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

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

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

3、k1，栈底为#*/void StackInitiate1(SeqStack1 *S) /*将元素压入SeqStack1*/void StackPush1(SeqStack1 *S,DataType x) /* SeqStack1出栈*/void StackPop1(SeqStack1 *S,DataType *x) /*取SeqStack1的栈顶元素*/int StackTop1(SeqStack1 S,DataType *d) /*定义链式堆栈LSNode，用于检测表达式的括号匹配*/typedef struct snodeDataType data;Struct snode *next;L

4、SNode;/*初始化堆栈LSNode*/void StackInitiate(LSNode* head)/*判断堆栈LSNode是否为空的函数，空返回0，否则返回1*/int StackNotEmpty(LSNode*head)/*LSNode入栈函数*/int StackPush(LSNode* head,DataType x)/*LSNode出栈函数*/int StackPop(LSNode* head,DataType* d)/*LSNode取栈顶元素*/int StackTop(LSNode* head,DataType *d)/*撤消LSNode动态申请空间*/void Destr

5、oy(LSNode* head)/*检测输入表达式的括号匹配函数*/void ExpIsCorrect(char exp) /*定义二叉树的结点BiTreeNode*/typedef struct Node DataType dataMaxStackSize; struct Node *leftChild; struct Node *rightChild; struct Node *parent;BiTreeNode;/*初始化BiTreeNode的根结点*/void Initiate(BiTreeNode *root) /*将BiTreeNode结点压入堆栈2*/void StackPush

6、2(SeqStack2 *S,BiTreeNode *x)/*逆时针打印BiTreeNode */void print(BiTreeNode *bt,int n) /*定义一个顺序堆栈SeqStack2，用于构造二叉树时对结点的保存*/typedef structBiTreeNode * SaveMaxStackSize; int top;SeqStack2;/*初始化SeqStack2*/void StackInitiate2(SeqStack2 *S) /*SeqStack2出栈*/ BiTreeNode * StackPop2(SeqStack2 *S) /*将待求表达式子转换为后缀形式

7、*/int Convert(char aMaxSize1,char bMaxSize1MaxSize2,SeqStack1 *S,int n) /*根据上面转换的表达式的后缀形式，构造相应的二叉树*/BiTreeNode * BuildTree(char bMaxSize1MaxSize2,int n) /*后序遍历该树，并且每到达一个结点时候，计算其子树之值，当到达根结点时，求得的值就是公式之真值。*/int PostOrder(BiTreeNode *t,int cMaxSize1,char bMaxSize1MaxSize2,int n) /*主函数*/void main() 3详细设计

8、#include<stdafx.h>#include<malloc.h>#include<string.h>typedef char DataType;#include<stdlib.h> typedef struct snode /*定义链式堆栈的结点，用于检测表达式的括号匹配*/ DataType data;struct snode* next;LSNode; void StackInitiate(LSNode* head) /*初始化堆栈*/if(*head=(LSNode*)malloc(sizeof(LSNode)=NULL)exit(

9、1);(*head)->next=NULL;int StackNotEmpty(LSNode* head) /*检测堆栈是否为空的函数，若为空，返回0，否则返回1*/if(head->next=NULL)return 0;else return 1;int StackPush(LSNode* head,DataType x) /*将元素入栈*/LSNode* p;if(p=(LSNode*)malloc(sizeof(LSNode)=NULL)printf("t内存空间不足无法插入!n");return 0;p->data=x;p->next=hea

10、d->next;head->next=p;return 1;int StackPop(LSNode* head,DataType* d) /*出栈*/LSNode* p=head->next;if(p=NULL)printf("t堆栈空出错n");return 0;head->next=p->next;*d=p->data;free(p);return 1;int StackTop(LSNode* head,DataType *d) /*取栈顶元素*/LSNode* p=head->next;if(p=NULL)printf(&qu

11、ot;t堆栈已空出错n");return 0;*d=p->data;return 1;void Destroy(LSNode* head)LSNode* p,*p1;p=head;while(p!=NULL)p1=p;p=p->next;free(p1); /*检测输入表达式的括号匹配函数*/void ExplsCorrect(char exp) LSNode *head;int i=0;char c; StackInitiate(&head);while(expi) /*表达式没读完时，执行'while'循环*/ if(expi='(&#

12、39;)StackPush(head,expi); /*遇到左括号'('将其进栈*/ else if(expi=')'&&StackNotEmpty(head)&&StackTop(head,&c)&&c='(')StackPop(head,&c); /*栈顶元素为'('且当前元素为')'时，出 栈，继续读下面的字符*/else if (expi=')'&&StackNotEmpty(head)&&Sta

13、ckTop(head,&c)&&c!='(')/*栈顶元素不为'('且当前元素为')'时，输出'左右括号不匹配'，退出重新输入*/ printf("nt 左右括号配对次序不正确!n"); exit(1);else if(expi=')')&&!StackNotEmpty(head)/*当前元素为')'但是堆栈已空时候，输出'右括号多于左括号'，退出程序重新输入*/printf("nt 右括号多于左括号!n"

14、;);exit(1);i+;if(StackNotEmpty(head) /*此时若堆栈非空，则输出'左括号多于右括号'，退出程序重新输入*/printf("nt 左括号多于右括号!n");exit(1);else printf("nt 左右括号匹配正确n"); /*若此时堆栈为空，表明输入的表达式左右括号匹配正确，继续执行下面的程序*/printf("n"); printf("-n");printf("t其后缀表达式子为:n");typedef struct DataType

15、stack1000;int top;SeqStack1; /*用来实现将输入的中缀表达式转换为后缀表达式*/typedef struct Node DataType data1000; struct Node *leftChild; struct Node *rightChild; struct Node *parent;BiTreeNode;/*定义二叉树的结点*/ typedef structBiTreeNode * address1000; /*定义成树结点的指针，方便下面构造二叉树时，对结点的保存*/ int top;SeqStack2;void StackInitiate1(SeqS

16、tack1 *S) /*初始化，栈底为#*/S->stack0='#' S->top = 1;void StackPush1(SeqStack1 *S,DataType x) /*将元素压入堆栈1*/S->stackS->top = x ; S->top+; void StackPop1(SeqStack1 *S,DataType *x) /*弹出堆栈1的栈顶元素*/S->top-; *x = S->stackS->top;int StackTop1(SeqStack1 S,DataType *d) /*取堆栈1的栈顶元素*/if

17、(S.top<=0)printf("t堆栈已空!n");return 0;else*d=S.stackS.top-1;return 1; void Initiate(BiTreeNode *root) /*初始化树的根结点*/*root = (BiTreeNode * ) malloc(sizeof(BiTreeNode);(*root)->leftChild=NULL; (*root)->rightChild=NULL; (*root)->parent=NULL;void print(BiTreeNode *bt,int n) /*逆时针打印二叉树

18、*/int i,j,m; if(bt=NULL) return; print(bt->rightChild,n+1); for(i=0;i<n;i+)printf(" "); if(n>=0)printf(" -"); m=strlen(bt->data);for(j=0;j<m;j+)printf("%c",bt->dataj); printf("n"); print(bt->leftChild,n+1);void StackInitiate2(SeqStack2 *S)

19、 /*初始化堆栈2*/S->top = 0; void StackPush2(SeqStack2 *S,BiTreeNode *x) /*将二叉树结点压入堆栈2 */ S->addressS->top = x;S->top+; BiTreeNode * StackPop2(SeqStack2 *S) /*从堆栈2中弹出栈顶元素 */ BiTreeNode *x; S->top-;x = S->addressS->top;return x;int Convert(char a500,char b500100,SeqStack1 *S,int n) /*将

20、待求表达式子转换为后缀形式*/int i,j,k=0; char character; for(i=0;i<n;i+)if(ai='' | ai='|' | ai='&' |ai='(' |ai=')'|ai='#')while(ai='' | ai='|' | ai='&' |ai='(' |ai=')'|ai='#')StackTop1(*S,&character);if

21、(character='#'&&ai='#')return k; /*此时堆栈和当前都为#时结束算法*/else if(character='#'&&ai!='#')|(character='|'&&ai='')|(character='|'&&ai='&') |(character='|'&&ai='(')|(character='&

22、;'&&ai='')|(character='&'&&ai='(') |(character=''&&ai='(')|(character='('&&ai!=')') StackPush1(S,ai); /*当中缀表达式当前运算符优先级较高时，进栈*/break;else if(character='('&&ai=')') /*'('和

23、9;)'相遇时，将'('退栈，接着读下面的*/StackPop1(S,&character);break;elseStackPop1(S,&character); /*当栈顶元素优先级较高时，退栈*/ bk0=character;bk1=0; k+;continue; continue;if(ai!='' && ai!='|' && ai!='&' && ai!='(' && ai!=')' &&

24、amp; ai!='#')j=0;while(ai!='' && ai!='|' && ai!='&' && ai!='(' && ai!=')' && ai!='#')bkj=ai; /*当前为变量时，直接存入二维数组b中*/j+;i+;i-;bkj=0; /*表示该行结束*/k+;return 0;BiTreeNode * BuildTree(char b500100,int n)int i;

25、BiTreeNode *p,*q,*o;SeqStack2 s;StackInitiate2(&s);for(i=0;i<n;i+)p=(BiTreeNode *)malloc(sizeof(BiTreeNode); strcpy(p->data,bi); /*将变量赋给结点P的数据域*/p->rightChild=NULL; /*初始化左右子树以及双亲指针*/p->leftChild=NULL; p->parent=NULL;if(bi0='')q=StackPop2(&s);p->rightChild=q; /*将弹出后的

26、结点作为右孩子*/q->parent=p;StackPush2(&s,p); else if(bi0='|' | bi0='&')q=StackPop2(&s); /*弹出q作为右孩子*/ o=StackPop2(&s); /*弹出0作为左孩子*/ q->parent=p;o->parent=p;p->leftChild=o;p->rightChild=q;StackPush2(&s,p); /*根结点入栈*/elseStackPush2(&s,p);p=StackPop2(&

27、s); /*弹出构造好的二叉数的根结点指针，并返回*/return p; int PostOrder(BiTreeNode *t,int c500,char b500100,int n) /*后序遍历该树*/int n1,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) return 1; if(n2=1) return 0;else if(t->d

28、ata0='&') /*遇到'&'只有两个都为真时才为真*/if(n1=1 && n2=1) return 1;else return 0;else if(t->data0='|') /*遇到'|'只有两个都为假时才为假*/if(n1=0 && n2=0) return 0;else return 1;elsefor(i=0;i<n;i+)if(!(strcmp( bi,t->data) break; /*当该结点数据域为变量时*/return ci; /*直接返回

29、该变量的真值*/return -1;void main()char a500,b500100; int i,j,n,answer,flag,c500; /*c数组用来存放变量的真值*/char m='y'SeqStack1 S;BiTreeNode *P;printf("nn");printf("tttt计算命题演算公式");printf("nn");printf("ttt &、|、 分别代表 与、或、非 "); printf("n.");while(m='y&#

30、39;)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=Convert(a,b,&S,n+1);

31、 /*此时n的值为二维数组b的行数目*/ /*测试输出后序表达式*/ printf("nt"); for(i=0;i<n;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

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