計算命題演算公式的真值Word版
傳播優(yōu)秀Word版文檔 ，希望對您有幫助，可雙擊去除！
四 計算命題演算公式的真值
一．實驗題目
所謂命題演算公式是指由邏輯變量（其值為TRUE或FALSE）和邏輯運算符∧（AND）、∨（OR）和┐（NOT）按一定規(guī)則所組成的公式（蘊(yùn)含之類的運算可以用∧、∨和┐來表示）。公式運算的先后順序為┐、∧、∨，而括號（）可以改變優(yōu)先次序。已知一個命題演算公式及各變量的值，要求設(shè)計一個程序來計算公式的真值。
要求：
（1）利用二叉樹來計算公式的真值。首先利用堆棧將中綴形式的公式變?yōu)楹缶Y形式；然后根據(jù)后綴形式，從葉結(jié)點開始構(gòu)造相應(yīng)的二叉樹；最后按后序遍歷該樹，求各子樹之值，即每到達(dá)一個結(jié)點，其子樹之值已經(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)蕉褩?，實現(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<stdio.h>
#include<iostream.h>
#include<malloc.h>
#include<math.h>
#include<string.h>
函數(shù)說明如下
SeqStack1; /*定義一個堆棧SeqStack1*/
void StackInitiate1(SeqStack1 *S) /*初始化堆棧1，棧底為‘#’*/
void StackPush1(SeqStack1 *S,DataType x) /*將元素壓入堆棧1*/
void StackPop1(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; /*定義二叉樹的結(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 * BuildTree(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) /*彈出棧頂元素*/
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;
} /*初始化堆棧*/
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->next;
if(p==NULL)
{
cout<<"堆棧已空出錯"<<endl;
return 0;
}
head->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)存空間不足無法插入!"<<endl;
return 0;
}
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<<"堆棧已空出錯"<<endl;
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);
}
}/*撤消*/
三．調(diào)試分析
在運行程序的過程中，碰到了一些錯誤，其中有很多是括號和分號的問題，看來以后寫程序要更加細(xì)心才行。
四．用戶手冊
此程序中'&''|''~'分別代表代表'與' '或' '非'運算
首先輸入一個包含變量，運算符表達(dá)式，再按Enter執(zhí)行。再依次輸入各變量的值。如果不繼續(xù)輸入，按0退出。再按y繼續(xù)或者n退出。
五．測試數(shù)據(jù)及測試結(jié)果
輸入a&b&c
六． 源程序清單
typedef 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 ;
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"<<endl;
//printf("堆棧已空!\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)//將待求表達(dá)式子轉(zhuǎn)換為后綴形式
{
int i,j,k=0;
char character;
for(i=0;i<n;i++)
{
if(IsOptr(a[i]))
{
while(IsOptr(a[i]))
{
StackTop1(*S,&character);
if(character=='#'&&a[i]=='#')return k; //此時堆棧和當(dāng)前都為‘#’時結(jié)束算法
else if
((character=='#'&&a[i]!='#')||(character=='|'&&a[i]=='~')||(character=='|'&&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]==')') //'('和')'相遇時，將'('退棧，接著讀下面的
{
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=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<stdlib.h>
typedef struct Node
{
DataType data[1000];
struct Node *leftChild;
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 = (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<n;i++)cout<<" ";
if(n>=0)
{
cout<<"---";
m=strlen(bt->data);
for(j=0;j<m;j++)cout<<bt->data[j];
cout<<endl;
}
print(bt->leftChild,n+1);
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////
void StackInitiate2(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;
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;i<n;i++)
{
p=(BiTreeNode *)malloc(sizeof(BiTreeNode));
strcpy(p->data,b[i]); //將變量賦給結(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][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
{
StackPush2(&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=PostOrder(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(t->data[0]=='|') //遇到'|'只有兩個都為假時才為假
{
if(n1==0 && n2==0) return 0;
else return 1;
}
else
{
for(i=0;i<n;i++)
{
if(!(strcmp( b[i],t->data))) break; //當(dāng)該結(jié)點數(shù)據(jù)域為變量時
}
return c[i]; //直接返回該變量的真值
}
}
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(head->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)存空間不足無法插入!"<<endl;
return 0;
}
p->data=x;
p->next=head->next;
head->next=p;
return 1;
}//將元素入棧
int StackPop(LSNode* head,DataType* d)
{
LSNode* p=head->next;
if(p==NULL)
{
cout<<"堆棧已空出錯"<<endl;
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)
{
cout<<"堆棧已空出錯"<<endl;
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[]) //檢測輸入表達(dá)式的括號匹配函數(shù)
{
LSNode *head;
int i=0;
char c;
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)&&StackTop(head,&c)&&c!='(')//棧頂元素不為'('且當(dāng)前元素為')'時，輸出'左右括號不匹配'，退出重新輸入
{
cout<<"左右括號配對次序不正確!"<<endl;
exit(1);
}
else if((exp[i]==')')&&!StackNotEmpty(head)) //當(dāng)前元素為')'但是堆棧已空時候，輸出
'右括號多于左括號'，退出程序重新輸入
{
cout<<"右括號多于左括號!"<<endl;
exit(1);
}
i++;
}
if(StackNotEmpty(head)) //此時若堆棧非空，則輸出'左括號多于右括號'，退出程序重新輸入
{
cout<<"左括號多于右括號!"<<endl;
exit(1);
}
else cout<<"左右括號匹配正確"<<endl; //若此時堆棧為空，表明輸入的表達(dá)式左右括號匹配正確，繼續(xù)執(zhí)行下面的程序
cout<<'\n'<<endl;
cout<<"其后綴表達(dá)式子為:"<<endl;
}
#include<iostream.h>
#include<malloc.h>
#include<stdio.h>
#include<math.h>
#include<string.h>
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*********************************************"<<endl;
cout<<"\t\t** **"<<endl;
cout<<"\t\t** * * * * * * * * * * **"<<endl;
cout<<"\t\t** * 計算命題演算公式* **"<<endl;
cout<<"\t\t** * * * * * * * * * * **"<<endl;
cout<<"\t\t** '&''|''~'分別代表代表'與' '或' '非'運算 **"<<endl;
cout<<"\t\t*********************************************"<<endl;
while(m=='y')
{
Initiate(&P);
StackInitiate1(&S);
cout<<"\n請輸入表達(dá)式:";
cin>>a;
cout<<"\n檢測括號匹配:";
cout<<"\n-------------------------"<<endl;
ExplsCorrect(a);
n=strlen(a);
a[n]='#';
n=Convert(a,b,&S,n+1);
//測試輸出后序表達(dá)式//
cout<<"-------------------------"<<endl;
for(i=0;i<n;i++)
{
for(j=0;b[i][j]!=0;j++) {
cout<<b[i][j];
}
}
cout<<endl;
P=BuildTree(b,n);
//測試打印二叉樹//
cout<<"-------------------------"<<endl;
cout<<"\n\n構(gòu)造的二叉樹結(jié)構(gòu)為:"<<endl;
cout<<"----------------------------------------------------------------------------"<<endl;
print(P,0);
cout<<"----------------------------------------------------------------------------"<<endl;
for (i=0;i<n;i++)
{
if(!IsOptr(b[i][0]))
{
num++;
}
}
while(1)
{
cout<<"\n\t\t 請為變量賦值<0:false or 1:true>\n"<<endl;
for(i=0;i<n;i++)
{
flag=0;
if(b[i][0]!='~'&&b[i][0]!='&'&&b[i][0]!='|')
{
for(j=0;j<i;j++)
{
if(!strcmp(b[i],b[j])){flag=1;break;} //有重復(fù)變量時flag為1，且找到第一個重復(fù)變量b[j]
}
if(flag==0)
{
cout<<">>>>>請輸入上述表達(dá)式中的變量“"<<b[i]<<"”的真值(0 or 1?)："; //給變量賦真值0或1
cin>>c[i];
cout<<endl;
}
else
{
c[i]=c[j]; //把重復(fù)出現(xiàn)的變量都用第一次的值賦值
}
}
else c[i]=-1;
}
End=PostOrder(P,c,b,n);
cout<<"\n>>>>>該表達(dá)式的最后結(jié)果為："<<End<<endl;
cout<<"\n\n（0.退出真值計算 1.重新輸入各變量的值）:";
cin>>i;
if(i==0) break;
}
int v[100],p;
printf("真值表如下：\n");
End=0;
long count=(int)pow(2,num);
for(p=0;p<num;p++)
{
v[p]=0;
}
for (long ii=0;ii<count;ii++)
{
j=0;
for(i=0;i<20;i++)
{
if(b[i][0]!='!'&& b[i][0]!='&'&& b[i][0]!='|')
c[i]=v[j++];
}
for (int jj=0;jj<num;jj++)
{
printf("%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<<"\n'y':繼續(xù)下一個表達(dá)式的計算 'n':退出程序"<<endl;
cout<<"\n'y' or 'n'?";
cin>>m;
cout<<"\n\n";
}
}
個人主頁