《計(jì)算命題演算公式的真值Word版》由會(huì)員分享，可在線閱讀，更多相關(guān)《計(jì)算命題演算公式的真值Word版（19頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、傳播優(yōu)秀Word版文檔 ，希望對(duì)您有幫助，可雙擊去除！ 四 計(jì)算命題演算公式的真值 一．實(shí)驗(yàn)題目 所謂命題演算公式是指由邏輯變量（其值為T(mén)RUE或FALSE）和邏輯運(yùn)算符∧（AND）、∨（OR）和┐（NOT）按一定規(guī)則所組成的公式（蘊(yùn)含之類的運(yùn)算可以用∧、∨和┐來(lái)表示）。公式運(yùn)算的先后順序?yàn)椹?、∧、∨，而括?hào)（）可以改變優(yōu)先次序。已知一個(gè)命題演算公式及各變量的值，要求設(shè)計(jì)一個(gè)程序來(lái)計(jì)算公式的真值。 要求： （1）利用二叉樹(shù)來(lái)計(jì)算公式的真值。首先利用堆棧將中綴形式的公式變?yōu)楹缶Y形式；然后根據(jù)后綴形式，從葉結(jié)點(diǎn)開(kāi)始構(gòu)造相應(yīng)的二叉樹(shù)；最后按后序遍歷該樹(shù)，求各子樹(shù)之值，即每到達(dá)一個(gè)結(jié)

2、點(diǎn)，其子樹(shù)之值已經(jīng)計(jì)算出來(lái)，當(dāng)?shù)竭_(dá)根結(jié)點(diǎn)時(shí)，求得的值就是公式之真值。 （2）邏輯變?cè)臉?biāo)識(shí)符不限于單字母，而可以是任意長(zhǎng)的字母數(shù)字串。 （3）根據(jù)用戶的要求顯示表達(dá)式的真值表。 二．實(shí)驗(yàn)設(shè)計(jì) 1. 設(shè)計(jì)思想 （1）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) a 建立一個(gè)鏈?zhǔn)蕉褩?，?shí)現(xiàn)括號(hào)的匹配問(wèn)題。 b建立一個(gè)順序堆棧，來(lái)實(shí)現(xiàn)中綴轉(zhuǎn)后綴并實(shí)現(xiàn)二叉樹(shù)的打印。 （2） 算法設(shè)計(jì) a.括號(hào)匹配 b中綴轉(zhuǎn)后綴 c打印二叉樹(shù)和真值表 2. 設(shè)計(jì)表示 自定義和調(diào)用的函數(shù)如下所示： #include"value.h" #include"Convert.h" #include<

3、stdio.h> #include #include #include #include 函數(shù)說(shuō)明如下 SeqStack1; /*定義一個(gè)堆棧SeqStack1*/ void StackInitiate1(SeqStack1 *S) /*初始化堆棧1，棧底為‘#’*/ void StackPush1(SeqStack1 *S,DataType x) /*將元素壓入堆棧1*/ void StackPo

4、p1(SeqStack1 *S,DataType *x) /*彈出堆棧1的棧頂元素*/ int StackTop1(SeqStack1 S,DataType *d) /*取堆棧1的棧頂元素*/ SeqStack2; /*定義一個(gè)順序堆棧SeqStack2*/ void StackInitiate2(SeqStack2 *S) /*初始化堆棧2*/ BiTreeNode * StackPop2(SeqStack2 *S) /*從堆棧2中彈出棧頂元素*/ BiTreeNode;

5、 /*定義二叉樹(shù)的結(jié)點(diǎn)*/ void Initiate(BiTreeNode **root) /*初始化樹(shù)的根結(jié)點(diǎn)*/ void print(BiTreeNode *bt,int n) /*逆時(shí)針打印二叉樹(shù)*/ void StackPush2(SeqStack2 *S,BiTreeNode *x) /*將二叉樹(shù)結(jié)點(diǎn)壓入堆棧2*/ int Convert(char a[500],char b[500][100],SeqStack1 *S,int n) /*將待求表達(dá)式轉(zhuǎn)換為后綴形式*/ BiTreeNode * Bu

6、ildTree(char b[500][100],int n)/*根據(jù)表達(dá)式的后綴形式，構(gòu)造相應(yīng)的二叉樹(shù)*/ LSNode; /*定義了鏈?zhǔn)蕉褩Ｓ糜谙旅鏅z測(cè)表達(dá)式的括號(hào)匹配*/ void StackInitiate(LSNode** head) /*初始化堆棧*/ int StackNotEmpty(LSNode* head) /*檢測(cè)堆棧是否為空的函數(shù)*/ int StackPush(LSNode* head,DataType x) /*將元素入棧*/ int StackPop(LSNode* head,DataType* d)

7、 /*彈出棧頂元素*/ int StackTop(LSNode* head,DataType *d) /*取棧頂元素*/ void Destroy(LSNode* head) /*撤消*/ void ExplsCorrect(char exp[]) /*檢測(cè)輸入表達(dá)式的括號(hào)匹配函數(shù)*/ i 3. 詳細(xì)設(shè)計(jì) void StackInitiate(LSNode** head) { if((*head=(LSNode*)malloc(sizeof(LSNode)))==NULL)exit(1); (*head)->next=NULL;

8、} /*初始化堆棧*/ int StackNotEmpty(LSNode* head) { if(head->next==NULL)return 0; else return 1; } /*檢測(cè)堆棧是否為空的函數(shù)，若為空，返回0，否則返回1*/ typedef struct snode { DataType data; struct snode* next; }LSNode; /*定義了鏈表的結(jié)點(diǎn)用于下面檢測(cè)表達(dá)式的括號(hào)匹配*/ int StackPop(LSNode* head,DataType* d) { LSNode* p=head

9、->next; if(p==NULL) { cout<<"堆棧已空出錯(cuò)"<next=p->next; *d=p->data; free(p); return 1; } /*彈出棧頂元素*/ int StackPush(LSNode* head,DataType x) { LSNode* p; if((p=(LSNode*)malloc(sizeof(LSNode)))==NULL) { cout<<"內(nèi)存空間不足無(wú)法插入!"<

10、 } p->data=x; p->next=head->next; head->next=p; return 1; } /*將元素入棧*/ int StackTop(LSNode* head,DataType *d) { LSNode* p=head->next; if(p==NULL) { cout<<"堆棧已空出錯(cuò)"<data; return 1; } /*取棧頂元素*/ void Destroy(LSNode* head) { LSNode* p,

11、*p1; p=head; while(p!=NULL) { p1=p; p=p->next; free(p1); } }/*撤消*/ 三．調(diào)試分析 在運(yùn)行程序的過(guò)程中，碰到了一些錯(cuò)誤，其中有很多是括號(hào)和分號(hào)的問(wèn)題，看來(lái)以后寫(xiě)程序要更加細(xì)心才行。 四．用戶手冊(cè) 此程序中&|~分別代表代表與 或 非運(yùn)算 首先輸入一個(gè)包含變量，運(yùn)算符表達(dá)式，再按Enter執(zhí)行。再依次輸入各變量的值。如果不繼續(xù)輸入，按0退出。再按y繼續(xù)或者n退出。 五．測(cè)試數(shù)據(jù)及測(cè)試結(jié)果 輸入a&b&c 6． 源程序清單 typedef

12、struct { DataType stack[1000]; int top; }SeqStack1; //用來(lái)實(shí)現(xiàn)將輸入的中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式 void StackInitiate1(SeqStack1 *S) //初始化，棧底為# { S->stack[0]=#; S->top = 1; } void StackPush1(SeqStack1 *S,DataType x) //將元素壓入堆棧1 { S->stack[S->top] = x ;

13、 S->top++; } void StackPop1(SeqStack1 *S,DataType *x) //彈出堆棧1的棧頂元素 { S->top--; *x = S->stack[S->top]; } int StackTop1(SeqStack1 S,DataType *d) //取堆棧1的棧頂元素 { if(S.top<=0) { cout<<"堆棧已空!\n"<

14、\n"); return 0; } else { *d=S.stack[S.top-1]; return 1; } } int IsOptr(DataType c)/* 判斷c是否為運(yùn)算符 */ { switch(c) { case&: case|: case~: case(: case): case#:return 1; default:return 0; } } int Convert(char a[500],char b[500][100],SeqStack1 *S,int n)//將

15、待求表達(dá)式子轉(zhuǎn)換為后綴形式 { int i,j,k=0; char character; for(i=0;i

16、acter==|&&a[i]==&) ||(character==|&&a[i]==()||(character==&&&a[i]==~)||(character==&&&a[i]==() ||(character==~&&a[i]==()||(character==(&&a[i]!=))) { StackPush1(S,a[i]); //當(dāng)中綴表達(dá)式當(dāng)前運(yùn)算符優(yōu)先級(jí)較高時(shí)，進(jìn)棧 break; } else if(character==(&&a[i]==)) //(和)相遇時(shí)，將(退棧，接著讀下面的

17、 { StackPop1(S,&character); break; } else { StackPop1(S,&character); //當(dāng)棧頂元素優(yōu)先級(jí)較高時(shí)，退棧 b[k][0]=character; b[k][1]=0; k++; continue; } } continue; } if(!IsOptr(a[i])) { j

18、=0; while(!IsOptr(a[i])) { b[k][j]=a[i]; //當(dāng)前為變量時(shí)，直接存入二維數(shù)組b中 j++; i++; } i--; b[k][j]=0; //表示該行結(jié)束 k++; } } return 0; } #include typedef struct Node { DataType data[1000]; struct Node *l

19、eftChild; struct Node *rightChild; struct Node *parent; }BiTreeNode;//定義二叉樹(shù)的結(jié)點(diǎn) typedef struct { BiTreeNode * address[1000]; //定義成樹(shù)結(jié)點(diǎn)的指針，方便下面構(gòu)造二叉樹(shù)時(shí)，對(duì)結(jié)點(diǎn)的保存 int top; }SeqStack2; void Initiate(BiTreeNode **root) //初始化樹(shù)的根結(jié)點(diǎn) { *root

20、 = (BiTreeNode * ) malloc(sizeof(BiTreeNode)); (*root)->leftChild=NULL; (*root)->rightChild=NULL; (*root)->parent=NULL; } void print(BiTreeNode *bt,int n) //逆時(shí)針打印二叉樹(shù) { int i,j,m; if(bt==NULL) return; print(bt->rightChild,n+1); for(i=0;i

21、" "; if(n>=0) { cout<<"---"; m=strlen(bt->data); for(j=0;jdata[j]; cout<leftChild,n+1); } ///////////////////////////////////////////////////////////////////////////////////////////////////////// void Stack

22、Initiate2(SeqStack2 *S) //初始化堆棧2 { S->top = 0; } void StackPush2(SeqStack2 *S,BiTreeNode *x) //將二叉樹(shù)結(jié)點(diǎn)壓入堆棧2 { S->address[S->top] = x; S->top++; } BiTreeNode * StackPop2(SeqStack2 *S) //從堆棧2中彈出棧頂元素 { BiTreeNode *x;

23、 S->top--; x = S->address[S->top]; return x; } BiTreeNode * BuildTree(char b[500][100],int n) { int i; BiTreeNode *p,*q,*o; SeqStack2 s; StackInitiate2(&s); for(i=0;idata,b[i]);

24、 //將變量賦給結(jié)點(diǎn)P的數(shù)據(jù)域 p->rightChild=NULL; //初始化左右子樹(shù)以及雙親指針 p->leftChild=NULL; p->parent=NULL; if(b[i][0]==~) { q=StackPop2(&s); p->rightChild=q; //將彈出后的結(jié)點(diǎn)作為右孩子 q->parent=p; StackPush2(&s,p); } else if(b[i

25、][0]==| || b[i][0]==&) { 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)入棧 } else { Sta

26、ckPush2(&s,p); } } p=StackPop2(&s); //彈出構(gòu)造好的二叉數(shù)的根結(jié)點(diǎn)指針，并返回 return p; } int PostOrder(BiTreeNode *t,int c[500],char b[500][100],int n) //后序遍歷該樹(shù) { int n1,n2,i; if(t!=NULL) { n1=PostOrder(t->leftChild,c,b,n); n2=Post

27、Order(t->rightChild,c,b,n); if(t->data[0]==~) //遇到~將值置反 { if(n2==0) return 1; if(n2==1) return 0; } else if(t->data[0]==&) //遇到&只有兩個(gè)都為真時(shí)才為真 { if(n1==1 && n2==1) return 1; else return 0; } else if

28、(t->data[0]==|) //遇到|只有兩個(gè)都為假時(shí)才為假 { if(n1==0 && n2==0) return 0; else return 1; } else { for(i=0;idata))) break; //當(dāng)該結(jié)點(diǎn)數(shù)據(jù)域?yàn)樽兞繒r(shí) } return c[i]; //直接返回該變量的真值 } }

29、 return -1; } ypedef struct snode { DataType data; struct snode* next; }LSNode; //定義鏈?zhǔn)蕉褩５慕Y(jié)點(diǎn)，用于下面檢測(cè)表達(dá)式的括號(hào)匹配 void StackInitiate(LSNode** head) { if((*head=(LSNode*)malloc(sizeof(LSNode)))==NULL)exit(1); (*head)->next=NULL; }//初始化堆棧 int StackNotEmpty(LSNode* head) { if(h

30、ead->next==NULL)return 0; else return 1; }//檢測(cè)堆棧是否為空的函數(shù)，若為空，返回0，否則返回1 int StackPush(LSNode* head,DataType x) { LSNode* p; if((p=(LSNode*)malloc(sizeof(LSNode)))==NULL) { cout<<"內(nèi)存空間不足無(wú)法插入!"<data=x; p->next=head->next; head->next=p; return 1; }//

31、將元素入棧 int StackPop(LSNode* head,DataType* d) { LSNode* p=head->next; if(p==NULL) { cout<<"堆棧已空出錯(cuò)"<next=p->next; *d=p->data; free(p); return 1; }//彈出棧頂元素 int StackTop(LSNode* head,DataType *d) { LSNode* p=head->next; if(p==NULL) {

32、 cout<<"堆棧已空出錯(cuò)"<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[]) //檢測(cè)輸入表達(dá)式的括號(hào)匹配函數(shù) { LSNode *head; int i=0; char c

33、; StackInitiate(&head); while(exp[i]) //表達(dá)式?jīng)]讀完時(shí)，執(zhí)行while循環(huán) { if(exp[i]==()StackPush(head,exp[i]); //遇到左括號(hào)(將其進(jìn)棧 else if(exp[i]==)&&StackNotEmpty(head)&&StackTop(head,&c)&&c==()StackPop(head,&c); //棧頂元素為(且當(dāng)前元素為)時(shí)，出棧，繼續(xù)讀下面的字符 else if (exp[i]==)&&StackNotEmpty(head)&&Stack

34、Top(head,&c)&&c!=()//棧頂元素不為(且當(dāng)前元素為)時(shí)，輸出左右括號(hào)不匹配，退出重新輸入 { cout<<"左右括號(hào)配對(duì)次序不正確!"<

35、 //此時(shí)若堆棧非空，則輸出左括號(hào)多于右括號(hào)，退出程序重新輸入 { cout<<"左括號(hào)多于右括號(hào)!"< #include #include #include #include

36、 typedef char DataType; #include"value.h" #include"Convert.h" #include"ExplsCorrect.h" void main() { char a[500],b[500][100]; int i,j,n,End,flag,c[500],num=0; //c數(shù)組用來(lái)存放變量的真值 char m=y; SeqStack1 S; BiTreeNode *P; cout<<"\t\t***************************

37、******************"<

38、out<<"\t\t** &|~分別代表代表與 或 非運(yùn)算 **"<>a; cout<<"\n檢測(cè)括號(hào)匹配:"; cout<<"\n-------------------------"<

39、ExplsCorrect(a); n=strlen(a); a[n]=#; n=Convert(a,b,&S,n+1); //測(cè)試輸出后序表達(dá)式// cout<<"-------------------------"<

40、 //測(cè)試打印二叉樹(shù)// cout<<"-------------------------"<

41、--------------------"<\n"<

42、;j>>>>請(qǐng)輸入上述表達(dá)式中的變量“"<>c[i]; cout<

43、]=c[j]; //把重復(fù)出現(xiàn)的變量都用第一次的值賦值 } } else c[i]=-1; } End=PostOrder(P,c,b,n); cout<<"\n>>>>>該表達(dá)式的最后結(jié)果為："<>i; if(i==0) break; } int v[100],p; printf

44、("真值表如下：\n"); End=0; long count=(int)pow(2,num); for(p=0;p

45、d ",v[jj]); } printf("真值為：%ld\n",End=PostOrder(P,c,b,n)); printf("\n"); v[num-1]++; p=num-1; while(v[p]>=2) { v[p]%=2; v[p-1]++; p--; } } cout<<"\ny:繼續(xù)下一個(gè)表達(dá)式的計(jì)算 n:退出程序"<>m; cout<<"\n\n"; } }