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

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

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

3、stdio.h> #include #include #include #include 函數(shù)說明如下 SeqStack1; /*定義一個堆棧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; /*定義一個順序堆棧SeqStack2*/ void StackInitiate2(SeqStack2 *S) /*初始化堆棧2*/ BiTreeNode * StackPop2(SeqStack2 *S) /*從堆棧2中彈出棧頂元素*/ BiTreeNode;

5、 /*定義二叉樹的結(jié)點*/ void Initiate(BiTreeNode **root) /*初始化樹的根結(jié)點*/ void print(BiTreeNode *bt,int n) /*逆時針打印二叉樹*/ void StackPush2(SeqStack2 *S,BiTreeNode *x) /*將二叉樹結(jié)點壓入堆棧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)的二叉樹*/ LSNode; /*定義了鏈?zhǔn)蕉褩Ｓ糜谙旅鏅z測表達(dá)式的括號匹配*/ void StackInitiate(LSNode** head) /*初始化堆棧*/ int StackNotEmpty(LSNode* head) /*檢測堆棧是否為空的函數(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[]) /*檢測輸入表達(dá)式的括號匹配函數(shù)*/ i 3. 詳細(xì)設(shè)計 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; } /*檢測堆棧是否為空的函數(shù)，若為空，返回0，否則返回1*/ typedef struct snode { DataType data; struct snode* next; }LSNode; /*定義了鏈表的結(jié)點用于下面檢測表達(dá)式的括號匹配*/ int StackPop(LSNode* head,DataType* d) { LSNode* p=head

9、->next; if(p==NULL) { cout<<"堆棧已空出錯"<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)存空間不足無法插入!"<

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<<"堆棧已空出錯"<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)試分析 在運行程序的過程中，碰到了一些錯誤，其中有很多是括號和分號的問題，看來以后寫程序要更加細(xì)心才行。 四．用戶手冊 此程序中&|~分別代表代表與 或 非運算 首先輸入一個包含變量，運算符表達(dá)式，再按Enter執(zhí)行。再依次輸入各變量的值。如果不繼續(xù)輸入，按0退出。再按y繼續(xù)或者n退出。 五．測試數(shù)據(jù)及測試結(jié)果 輸入a&b&c 6． 源程序清單 typedef

12、struct { DataType stack[1000]; int top; }SeqStack1; //用來實現(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是否為運算符 */ { 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ōu)先級較高時，進(jìn)棧 break; } else if(character==(&&a[i]==)) //(和)相遇時，將(退棧，接著讀下面的

17、 { StackPop1(S,&character); break; } else { StackPop1(S,&character); //當(dāng)棧頂元素優(yōu)先級較高時，退棧 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ù)組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;//定義二叉樹的結(jié)點 typedef struct { BiTreeNode * address[1000]; //定義成樹結(jié)點的指針，方便下面構(gòu)造二叉樹時，對結(jié)點的保存 int top; }SeqStack2; void Initiate(BiTreeNode **root) //初始化樹的根結(jié)點 { *root

20、 = (BiTreeNode * ) malloc(sizeof(BiTreeNode)); (*root)->leftChild=NULL; (*root)->rightChild=NULL; (*root)->parent=NULL; } void print(BiTreeNode *bt,int n) //逆時針打印二叉樹 { 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) //將二叉樹結(jié)點壓入堆棧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é)點P的數(shù)據(jù)域 p->rightChild=NULL; //初始化左右子樹以及雙親指針 p->leftChild=NULL; p->parent=NULL; if(b[i][0]==~) { q=StackPop2(&s); p->rightChild=q; //將彈出后的結(jié)點作為右孩子 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é)點入棧 } else { Sta

26、ckPush2(&s,p); } } p=StackPop2(&s); //彈出構(gòu)造好的二叉數(shù)的根結(jié)點指針，并返回 return p; } int PostOrder(BiTreeNode *t,int c[500],char b[500][100],int n) //后序遍歷該樹 { 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]==&) //遇到&只有兩個都為真時才為真 { if(n1==1 && n2==1) return 1; else return 0; } else if

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

29、 return -1; } ypedef struct snode { DataType data; struct snode* next; }LSNode; //定義鏈?zhǔn)蕉褩５慕Y(jié)點，用于下面檢測表達(dá)式的括號匹配 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; }//檢測堆棧是否為空的函數(shù)，若為空，返回0，否則返回1 int StackPush(LSNode* head,DataType x) { LSNode* p; if((p=(LSNode*)malloc(sizeof(LSNode)))==NULL) { cout<<"內(nèi)存空間不足無法插入!"<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<<"堆棧已空出錯"<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<<"堆棧已空出錯"<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[]) //檢測輸入表達(dá)式的括號匹配函數(shù) { LSNode *head; int i=0; char c

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

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

35、 //此時若堆棧非空，則輸出左括號多于右括號，退出程序重新輸入 { cout<<"左括號多于右括號!"< #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ù)組用來存放變量的真值 char m=y; SeqStack1 S; BiTreeNode *P; cout<<"\t\t***************************

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

38、out<<"\t\t** &|~分別代表代表與 或 非運算 **"<>a; cout<<"\n檢測括號匹配:"; cout<<"\n-------------------------"<

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

40、 //測試打印二叉樹// cout<<"-------------------------"<

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

42、;j>>>>請輸入上述表達(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ù)下一個表達(dá)式的計算 n:退出程序"<>m; cout<<"\n\n"; } }