計(jì)算命題演算公式真值數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言實(shí)習(xí)報(bào)告

1、計(jì)算命題演算公式的真值 李仙偉 014072-281 需求分析1.1.命題演算公式由邏輯變量（其值為TRUE或FALSE）和邏輯運(yùn)算符（AND）、（OR）和（NOT）按一定規(guī)則所組成的公式。公式運(yùn)算的先后順序?yàn)?、，而括?hào)（）可以改變優(yōu)先次序。1.2.輸入輸出以人機(jī)對(duì)話的方式讓用戶輸入要計(jì)算的命題表達(dá)式；計(jì)算出最后的真值并輸?shù)狡聊簧稀?.3.測(cè)試數(shù)據(jù):(a&b)|c)&d(boy&girl）|father）&mother(5&99)|02概要設(shè)計(jì)2.1.基本思想：利用二叉樹計(jì)算公式的真值:第一步:利用堆棧將中綴形式的公式變?yōu)楹缶Y形式；第二步:根據(jù)后綴形式，

2、從葉結(jié)點(diǎn)開始構(gòu)造相應(yīng)的二叉樹；第三步:按后序遍歷該樹，求各子樹之值，即每到達(dá)一個(gè)結(jié)點(diǎn)，其子樹之值已經(jīng)計(jì)算出來(lái)，當(dāng)?shù)竭_(dá)根結(jié)點(diǎn)時(shí)，求得的值就是公式之真值；邏輯變?cè)臉?biāo)識(shí)符不限于單字母，而可以是任意長(zhǎng)的字母數(shù)字串；根據(jù)用戶的要求顯示表達(dá)式的真值表。2.2.程序設(shè)計(jì)的概要圖如下所示：2.3.抽象數(shù)據(jù)類型的定義及其相應(yīng)的操作函數(shù)定義如下：/*定義一個(gè)堆棧SeqStack1，用來(lái)實(shí)現(xiàn)將輸入的中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式*/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) /*定義鏈?zhǔn)蕉褩SNode，用于檢測(cè)表達(dá)式的括號(hào)匹配*/typedef struct snodeDataType data;Struct snode *next;L

4、SNode;/*初始化堆棧LSNode*/void StackInitiate(LSNode* head)/*判斷堆棧LSNode是否為空的函數(shù)，空返回0，否則返回1*/int StackNotEmpty(LSNode*head)/*LSNode入棧函數(shù)*/int StackPush(LSNode* head,DataType x)/*LSNode出棧函數(shù)*/int StackPop(LSNode* head,DataType* d)/*LSNode取棧頂元素*/int StackTop(LSNode* head,DataType *d)/*撤消LSNode動(dòng)態(tài)申請(qǐng)空間*/void Destr

5、oy(LSNode* head)/*檢測(cè)輸入表達(dá)式的括號(hào)匹配函數(shù)*/void ExpIsCorrect(char exp) /*定義二叉樹的結(jié)點(diǎn)BiTreeNode*/typedef struct Node DataType dataMaxStackSize; struct Node *leftChild; struct Node *rightChild; struct Node *parent;BiTreeNode;/*初始化BiTreeNode的根結(jié)點(diǎn)*/void Initiate(BiTreeNode *root) /*將BiTreeNode結(jié)點(diǎn)壓入堆棧2*/void StackPush

6、2(SeqStack2 *S,BiTreeNode *x)/*逆時(shí)針打印BiTreeNode */void print(BiTreeNode *bt,int n) /*定義一個(gè)順序堆棧SeqStack2，用于構(gòu)造二叉樹時(shí)對(duì)結(jié)點(diǎn)的保存*/typedef structBiTreeNode * SaveMaxStackSize; int top;SeqStack2;/*初始化SeqStack2*/void StackInitiate2(SeqStack2 *S) /*SeqStack2出棧*/ BiTreeNode * StackPop2(SeqStack2 *S) /*將待求表達(dá)式子轉(zhuǎn)換為后綴形式

7、*/int Convert(char aMaxSize1,char bMaxSize1MaxSize2,SeqStack1 *S,int n) /*根據(jù)上面轉(zhuǎn)換的表達(dá)式的后綴形式，構(gòu)造相應(yīng)的二叉樹*/BiTreeNode * BuildTree(char bMaxSize1MaxSize2,int n) /*后序遍歷該樹，并且每到達(dá)一個(gè)結(jié)點(diǎn)時(shí)候，計(jì)算其子樹之值，當(dāng)?shù)竭_(dá)根結(jié)點(diǎn)時(shí)，求得的值就是公式之真值。*/int PostOrder(BiTreeNode *t,int cMaxSize1,char bMaxSize1MaxSize2,int n) /*主函數(shù)*/void main() 3詳細(xì)設(shè)計(jì)

8、#include<stdafx.h>#include<malloc.h>#include<string.h>typedef char DataType;#include<stdlib.h> typedef struct snode /*定義鏈?zhǔn)蕉褩５慕Y(jié)點(diǎn)，用于檢測(cè)表達(dá)式的括號(hào)匹配*/ 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) /*檢測(cè)堆棧是否為空的函數(shù)，若為空，返回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èi)存空間不足無(wú)法插入!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堆棧空出錯(cuò)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堆棧已空出錯(cuò)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); /*檢測(cè)輸入表達(dá)式的括號(hào)匹配函數(shù)*/void ExplsCorrect(char exp) LSNode *head;int i=0;char c; StackInitiate(&head);while(expi) /*表達(dá)式?jīng)]讀完時(shí)，執(zhí)行'while'循環(huán)*/ if(expi='(&#

12、39;)StackPush(head,expi); /*遇到左括號(hào)'('將其進(jìn)棧*/ else if(expi=')'&&StackNotEmpty(head)&&StackTop(head,&c)&&c='(')StackPop(head,&c); /*棧頂元素為'('且當(dāng)前元素為')'時(shí)，出 棧，繼續(xù)讀下面的字符*/else if (expi=')'&&StackNotEmpty(head)&&Sta

13、ckTop(head,&c)&&c!='(')/*棧頂元素不為'('且當(dāng)前元素為')'時(shí)，輸出'左右括號(hào)不匹配'，退出重新輸入*/ printf("nt 左右括號(hào)配對(duì)次序不正確!n"); exit(1);else if(expi=')')&&!StackNotEmpty(head)/*當(dāng)前元素為')'但是堆棧已空時(shí)候，輸出'右括號(hào)多于左括號(hào)'，退出程序重新輸入*/printf("nt 右括號(hào)多于左括號(hào)!n"

14、;);exit(1);i+;if(StackNotEmpty(head) /*此時(shí)若堆棧非空，則輸出'左括號(hào)多于右括號(hào)'，退出程序重新輸入*/printf("nt 左括號(hào)多于右括號(hào)!n");exit(1);else printf("nt 左右括號(hào)匹配正確n"); /*若此時(shí)堆棧為空，表明輸入的表達(dá)式左右括號(hào)匹配正確，繼續(xù)執(zhí)行下面的程序*/printf("n"); printf("-n");printf("t其后綴表達(dá)式子為:n");typedef struct DataType

15、stack1000;int top;SeqStack1; /*用來(lái)實(shí)現(xiàn)將輸入的中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式*/typedef struct Node DataType data1000; struct Node *leftChild; struct Node *rightChild; struct Node *parent;BiTreeNode;/*定義二叉樹的結(jié)點(diǎn)*/ typedef structBiTreeNode * address1000; /*定義成樹結(jié)點(diǎn)的指針，方便下面構(gòu)造二叉樹時(shí)，對(duì)結(jié)點(diǎn)的保存*/ 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) /*初始化樹的根結(jié)點(diǎn)*/*root = (BiTreeNode * ) malloc(sizeof(BiTreeNode);(*root)->leftChild=NULL; (*root)->rightChild=NULL; (*root)->parent=NULL;void print(BiTreeNode *bt,int n) /*逆時(shí)針打印二叉樹

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) /*將二叉樹結(jié)點(diǎn)壓入堆棧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、待求表達(dá)式子轉(zhuǎn)換為后綴形式*/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; /*此時(shí)堆棧和當(dāng)前都為#時(shí)結(jié)束算法*/else if(character='#'&&ai!='#')|(character='|'&&ai='')|(character='|'&&ai='&') |(character='|'&&ai='(')|(character='&

22、;'&&ai='')|(character='&'&&ai='(') |(character=''&&ai='(')|(character='('&&ai!=')') StackPush1(S,ai); /*當(dāng)中綴表達(dá)式當(dāng)前運(yùn)算符優(yōu)先級(jí)較高時(shí)，進(jìn)棧*/break;else if(character='('&&ai=')') /*'('和

23、9;)'相遇時(shí)，將'('退棧，接著讀下面的*/StackPop1(S,&character);break;elseStackPop1(S,&character); /*當(dāng)棧頂元素優(yōu)先級(jí)較高時(shí)，退棧*/ 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; /*當(dāng)前為變量時(shí)，直接存入二維數(shù)組b中*/j+;i+;i-;bkj=0; /*表示該行結(jié)束*/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); /*將變量賦給結(jié)點(diǎn)P的數(shù)據(jù)域*/p->rightChild=NULL; /*初始化左右子樹以及雙親指針*/p->leftChild=NULL; p->parent=NULL;if(bi0='')q=StackPop2(&s);p->rightChild=q; /*將彈出后的

26、結(jié)點(diǎn)作為右孩子*/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); /*根結(jié)點(diǎn)入棧*/elseStackPush2(&s,p);p=StackPop2(&

27、s); /*彈出構(gòu)造好的二叉數(shù)的根結(jié)點(diǎn)指針，并返回*/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='&') /*遇到'&'只有兩個(gè)都為真時(shí)才為真*/if(n1=1 && n2=1) return 1;else return 0;else if(t->data0='|') /*遇到'|'只有兩個(gè)都為假時(shí)才為假*/if(n1=0 && n2=0) return 0;else return 1;elsefor(i=0;i<n;i+)if(!(strcmp( bi,t->data) break; /*當(dāng)該結(jié)點(diǎn)數(shù)據(jù)域?yàn)樽兞繒r(shí)*/return ci; /*直接返回

29、該變量的真值*/return -1;void main()char a500,b500100; int i,j,n,answer,flag,c500; /*c數(shù)組用來(lái)存放變量的真值*/char m='y'SeqStack1 S;BiTreeNode *P;printf("nn");printf("tttt計(jì)算命題演算公式");printf("nn");printf("ttt &、|、 分別代表 與、或、非 "); printf("n.");while(m='y&#

30、39;)Initiate(&P); StackInitiate1(&S);printf("nt請(qǐng)輸入待求表達(dá)式，例如：2(2&0)|5n"); printf(".");printf("nt用戶輸入為： "); scanf("%s",a);printf("n.");printf("nt現(xiàn)在檢測(cè)其括號(hào)匹配:n"); ExplsCorrect(a); n=strlen(a); an='#' n=Convert(a,b,&S,n+1);

31、 /*此時(shí)n的值為二維數(shù)組b的行數(shù)目*/ /*測(cè)試輸出后序表達(dá)式*/ printf("nt"); for(i=0;i<n;i+)for(j=0;bij!=0;j+) /*'0'為二維數(shù)組b每行的結(jié)束標(biāo)志*/printf("%c",bij);printf("n");P=BuildTree(b,n); /*測(cè)試打印二叉樹*/printf("n."); printf("t構(gòu)造的二叉樹結(jié)構(gòu)為:n"); print(P,0); printf(".n");while

32、(1) printf("nt請(qǐng)為變量賦值<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; /*有重復(fù)變量時(shí)flag為1，且找到第一個(gè)重復(fù)變量bj*/ if(flag=0)printf("t請(qǐng)?jiān)O(shè)定上述待求表達(dá)式中的變量%s的真值(0 or 1?)：nt"，bi); /*給變量賦真值0或1*/ scanf("%d",&ci); printf("n");elseci=cj; /*把重復(fù)出現(xiàn)的變量都用第一次的值賦值*/else ci=-1;answer=PostOrder(P,c,b,n); printf("nt該表達(dá)式的最后結(jié)果為： %dn",answer); printf("nnt0.退出該表達(dá)式子的真值計(jì)算 1.重新輸入表達(dá)式各變量的真值計(jì)算:nt"