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

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

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

3、tackSize;int top;SeqStack1;/*初始化SeqStack1，栈底为 #' */void StackI nitiate1(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 s

4、truct snodeDataType data;Struct snode *n ext;LSNode;/*初始化堆栈LSNode*/void Stackl nitiate(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

5、* head,DataType *d)/*撤消LSNode动态申请空间*/void Destroy(LSNode* head) /*检测输入表达式的括号匹配函数*/void ExplsCorrect(char exp) /*定义二叉树的结点BiTreeNode*/typedef struct NodeDataType dataMaxStackSize;struct Node *leftChild;struct Node *rightChild;struct Node *pare nt;BiTreeNode;/*初始化BiTreeNode的根结点*/void Initiate(BiTreeNod

6、e *root)/*将BiTreeNode结点压入堆栈2*/void StackPush2(SeqStack2 *S,BiTreeNode *x)/*逆时针打印BiTreeNode */void prin t(BiTreeNode *bt, int n) /*定义一个顺序堆栈SeqStack2，用于构造二叉树时对结点的保存*/typedef structBiTreeNode * SaveMaxStackSize;int top;SeqStack2;/* 初始化 SeqStack2*/void StackInitiate2(SeqStack2 *S)/*SeqStack2 出栈 */BiTree

7、Node * StackPop2(SeqStack2 *S) /*将待求表达式子转换为后缀形式*/int Co nvert(char aMaxSize1,char bMaxSize1MaxSize2,SeqStack1*S,i nt n) /*根据上面转换的表达式的后缀形式，构造相应的二叉树*/BiTreeNode * BuildTree(char bMaxSize1MaxSize2,i nt n) /*后序遍历该树，并且每到达一个结点时候，计算其子树之值，当到达根结点时，求得的值就是公式之真值。*/cMaxSize1,charintPostOrder(BiTreeNode*t,i ntbMa

8、xSize1MaxSize2,int n) /*主函数*/void mai n()3 详细设计#in clude<>#in clude<>#in clude<>typedef char DataType;#in clude<>定义链式堆栈的结点，用于检测表达式的括号匹配*/typedef struct snode /*DataType data; struct sno de* n ext;LSNode;void StackInitiate(LSNode* head) /*初始化堆栈 */ if(*head=(LSNode*)malloc(size

9、of(LSNode)=NULL)exit(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)=prin tf("t内存空间不足无法插入return 0;NULL)!n");

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

11、head-> next;if(p=NULL)堆栈已空出错n");prin tf("t return 0;*d=p->data;return 1;void Destroy(LSNode* head) LSNode* p,*p1;p=head;while(p!=NULL)p仁p； p=p->n ext;free(pl);/*检测输入表达式的括号匹配函数*/void ExplsCorrect(char exp)LSNode *head;int i=0;char c;StackI ni tiate(&head);while(expi) /*表达式没读完时，

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

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

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

15、Type stack1000;int top;SeqStack1; /*用来实现将输入的中缀表达式转换为后缀表达式*/typedef struct NodeDataType data1000;struct Node *leftChild;struct Node *rightChild;struct Node *pare nt;BiTreeNode;/* 定义二叉树的结点 */typedef structBiTreeNode * address1000; /*结点的保存*/int top;SeqStack2;void StackI nitiate1(SeqStack1 *S)/*S->st

16、ack0='#'S->top = 1;void StackPush1(SeqStack1 *S,DataType x) /*S->stackS->top = x ;S_>top+;void StackPop1(SeqStack1 *S,DataType *x)/*定义成树结点的指针，方便下面构造二叉树时，对初始化，栈底为#*/将元素压入堆栈1*/弹出堆栈1的栈顶元素*/取堆栈1的栈顶元素*/初始化树的根结点*/S->top-;*x = S->stackS->top;int StackTop1(SeqStack1 SQataType *d

17、)/*if<=0)printf("t堆栈已空!n");return 0;else*d=;return 1; void Ini tiate(BiTreeNode *root) /*root = (BiTreeNode * ) malloc(sizeof(BiTreeNode);(*root)->leftChild=NULL;(*root)->rightChild=NULL;(*root)->pare nt=NULL;逆时针打印二叉树*/void print(BiTreeNode *bt,int n) /* int i,j,m;if(bt=NULL) r

18、eturn;prin t(bt->rightChild, n+1);for(i=0;i< n; i+)pri ntf("");if(n >=0)prin tf("-");m=strle n(bt->data);for(j=0;j<m;j+)pri ntf("%c",bt->dataj);prin tf("n");prin t(bt->leftChild, n+1);void StackInitiate2(SeqStack2 *S)/*初始化堆栈 2*/S->top =

19、 0;void StackPush2(SeqStack2 *S,BiTreeNode *x)/*将二叉树结点压入堆栈2 */S->addressS->top = x;v1.0可编辑可修改25S->top+;BiTreeNode * StackPop2(SeqStack2 *S)/*BiTreeNode *x;S->top-;x = S_>addressS_>top;return x;从堆栈2中弹出栈顶元素*/int Convert(char a500,char b500100,SeqStack1 *S,int n) /*转换为后缀形式*/int i,j,k=

20、0;char character;for(i=0;i< n; i+)if(ai=''| ai=T| ai=&|ai='('while(ai=''|ai='|'|l|ai=')'|ai='#')StackTop1(*S，& character);if(character='#'&&,ai='#')return k;/* # '时结束算法*/将待求表达式子|ai=')'|ai='#')ai=&#

21、39;&'|ai='('此时堆栈和当前都为else if(character='#'&&ai!='#')| (character=T&&ai='')|(character='|'& & ai='&')|(character=T&&ai='(')|(character='&'&&ai='')|(character=&&&

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

23、 StackPop1(S,&character); /*当栈顶元素优先级较高时，退栈*/bkO=character;bk1=0;k+;con ti nue;con ti nue;if(ai!='' && ai!=T && ai!=& && ai!='(' && ai!=')' &&ai!='#')j=0;&&while(ai!=''&& ai!='|'&&

24、ai!='&'&& ai!='('&& ai!=')'ai!='#')bkj=ai;/*当前为变量时，直接存入二维数组b中*/j+；i+;i-;bkj=0;/*表示该行结束*/k+;return 0;BiTreeNode * BuildTree(char b500100,int n)int i;BiTreeNode *p,*q,*o;v1.0可编辑可修改else27SeqStack2 s;Stackl ni tiate2( &s);for(i=0;i< n;i+)p=(BiTr

25、eeNode *)malloc(sizeof(BiTreeNode);/*/*strcpy(p->data,bi); p->rightChild=NULL; p->leftChild=NULL; p->pare nt=NULL; if(biO='') q=StackPop2(&s); p->rightChild=q; /* q->pare nt=p; StackPush2(&s,p);else if(biO=T | bi0='&') q=StackPop2(&s);/*o=StackPop2(&

26、amp;s);/*q->pare nt=p;o->pare nt=p; p->leftChild=o; p->rightChild=q;StackPush2(&s,p);/*将变量赋给结点P的数据域*/初始化左右子树以及双亲指针*/将弹出后的结点作为右孩子 */弹出q作为右孩子*/弹出0作为左孩子*/根结点入栈*/v1.0可编辑可修改StackPush2(&s,p);p=StackPop2(&s);/*弹出构造好的二叉数的根结点指针，并返回*/return p;int PostOrder(BiTreeNode *t,i nt c500,char

27、b500100,i nt n) /*后序遍历该树*/int n1, n2,i;if(t!=NULL)n1= PostOrder(t->leftChild,c,b ,n);遇到''将值置反*/遇到&只有两个都为真时才为真*/n 2=PostOrder(t->rightChild,c,b, n);if(t->data0='')/*if(n 2=0) return 1;if(n 2=1) return 0;else if(t->data0='&')/* if(n 1=1 && n2=1) retu

28、rn 1;else return 0;else if(t->dataO=T)/*遇到T 只有两个都为假时才为假*/if(n仁=0 && n2=0) return 0;else return 1;elsefor(i=0;i< n;i+)if(!(strcmp( bi,t->data) break; /*当该结点数据域为变量时*/41return ci;/*return -1;直接返回该变量的真值*/void mai n()char a500,b500100;数组用来存放变量的真值*/int i,j, n,an swer,flag,c500;/*cchar m=&

29、#39;y'SeqStackl S;BiTreeNode *P;prin tf("nn");prin tf("tttt计算命题演算公式”)；prin tf("nn");printf("ttt &、|、 分别代表 与、或、printf("n");非");while(m='y')In itiate(&P);StackI ni tiate1(&S);prin tf("nt请输入待求表达式，例如:printf(”");prin tf("

30、nt用户输入为：”)；sca nf("%s",a);2(2&0)|5n");printf("n");prin tf("nt现在检测其括号匹配:n");ExplsCorrect(a);n=strle n( a);a n=#;n=Co nvert(a,b,&S,n+1);/*此时n的值为二维数组b的行数目*/*测试输出后序表达式*/prin tf("nt");for(i=0;i <n ;i+)b每行的结束标志*/for(j=0;bij!=0；j+)/*'0'为二维数组pr

31、in tf("%c",bij);prin tf("n ”);P=BuildTree(b ,n);/*测试打印二叉树*/printf("n");prin tf("t构造的二叉树结构为:n");prin t(P,0);printf(”n");while(1)printf("nt请为变量赋值 <0:false or 1:true>nn");for(i=0;i< n;i+)flag=0;if(biO!=''&&bi0!=&&&bi

32、0!=T)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*/scan f("%d",&ci);prin tf("n");elseci=cj; /*把重复出现的变量都用第一次的值赋值*/else ci=-1; an swer=PostOrder(P,c,b, n);prin tf(&qu

33、ot;nt该表达式的最后结果为：dn",a nswer);prin tf("nnt0.退出该表达式子的真值计算1.重新输入表达式各变量的真值计算:nt");scan f("%d",&i);if(i=0) break;printf("nt'y':继续下一个表达式的计算'n': 退出程序bt");prin tf("nt'y' or ' n'nt");sca nf("%c",&m);while(m!='y'&&m!=' n')printf("twrong input!n");prin t