计算命题演算公式的真值
《计算命题演算公式的真值》由会员分享，可在线阅读，更多相关《计算命题演算公式的真值（19页珍藏版）》请在装配图网上搜索。
1、 四 计算命题演算公式的真值 一．实验题目 所谓命题演算公式是指由逻辑变量（其值为TRUE或FALSE）和逻辑运算符∧（AND）、∨（OR）和┐（NOT）按一定规则所组成的公式（蕴含之类的运算可以用∧、∨和┐来表示）。公式运算的先后顺序为┐、∧、∨，而括号（）可以改变优先次序。已知一个命题演算公式及各变量的值，要求设计一个程序来计算公式的真值。 要求： （1）利用二叉树来计算公式的真值。首先利用堆栈将中缀形式的公式变为后缀形式；然后根据后缀形式，从叶结点开始构造相应的二叉树；最后按后序遍历该树，求各子树之值，即每到达一个结点，其子树之值已经计算出来，当到达根结点时，求得的值就
2、是公式之真值。
（2）逻辑变元的标识符不限于单字母，而可以是任意长的字母数字串。
（3）根据用户的要求显示表达式的真值表。
二．实验设计
1. 设计思想
（1）数据结构设计
a 建立一个链式堆栈，实现括号的匹配问题。
b建立一个顺序堆栈，来实现中缀转后缀并实现二叉树的打印。
（2） 算法设计
a.括号匹配 b中缀转后缀 c打印二叉树和真值表
2. 设计表示
自定义和调用的函数如下所示：
#include"value.h"
#include"Convert.h"
#include 3、.h>
#include 4、) /*弹出堆栈1的栈顶元素*/
int StackTop1(SeqStack1 S,DataType *d) /*取堆栈1的栈顶元素*/
SeqStack2; /*定义一个顺序堆栈SeqStack2*/
void StackInitiate2(SeqStack2 *S) /*初始化堆栈2*/
BiTreeNode * StackPop2(SeqStack2 *S) /*从堆栈2中弹出栈顶元素*/
BiTreeNode; /*定义二叉树的结点*/
推 5、荐精选
void Initiate(BiTreeNode **root) /*初始化树的根结点*/
void print(BiTreeNode *bt,int n) /*逆时针打印二叉树*/
void StackPush2(SeqStack2 *S,BiTreeNode *x) /*将二叉树结点压入堆栈2*/
int Convert(char a[500],char b[500][100],SeqStack1 *S,int n) /*将待求表达式转换为后缀形式*/
BiTreeNode * BuildTree(char b[500][1 6、00],int n)/*根据表达式的后缀形式，构造相应的二叉树*/
LSNode; /*定义了链式堆栈用于下面检测表达式的括号匹配*/
void StackInitiate(LSNode** head) /*初始化堆栈*/
int StackNotEmpty(LSNode* head) /*检测堆栈是否为空的函数*/
int StackPush(LSNode* head,DataType x) /*将元素入栈*/
int StackPop(LSNode* head,DataType* d) /*弹出栈顶元素*/
int Stac 7、kTop(LSNode* head,DataType *d) /*取栈顶元素*/
void Destroy(LSNode* head) /*撤消*/
void ExplsCorrect(char exp[]) /*检测输入表达式的括号匹配函数*/
i
3. 详细设计
void StackInitiate(LSNode** head)
{
if((*head=(LSNode*)malloc(sizeof(LSNode)))==NULL)exit(1);
(*head)->next=NULL;
} /*初始化堆栈*/
int St 8、ackNotEmpty(LSNode* head)
{
if(head->next==NULL)return 0;
else return 1;
}
/*检测堆栈是否为空的函数，若为空，返回0，否则返回1*/
typedef struct snode
{
DataType data;
struct snode* next;
}LSNode;
/*定义了链表的结点用于下面检测表达式的括号匹配*/
int StackPop(LSNode* head,DataType* d)
{
LSNode* p=head->next;
if(p==NULL) 9、
{
推荐精选
cout<<"堆栈已空出错"< 10、ata=x;
p->next=head->next;
head->next=p;
return 1;
}
/*将元素入栈*/
int StackTop(LSNode* head,DataType *d)
{
LSNode* p=head->next;
if(p==NULL)
{
cout<<"堆栈已空出错"< 11、
p=head;
while(p!=NULL)
{
p1=p;
p=p->next;
free(p1);
}
}/*撤消*/
三．调试分析
在运行程序的过程中，碰到了一些错误，其中有很多是括号和分号的问题，看来以后写程序要更加细心才行。
四．用户手册
此程序中'&''|''~'分别代表代表'与' '或' '非'运算
首先输入一个包含变量，运算符表达式，再按Enter执行。再依次输入各变量的值。如果不继续输入，按0退出。再按y继续或者n退出。
五．测试数据及测试结果
输入a&b&c
推荐精选
六． 源程 12、序清单
typedef struct
{
DataType stack[1000];
int top;
}SeqStack1;
//用来实现将输入的中缀表达式转换为后缀表达式
void StackInitiate1(SeqStack1 *S) //初始化，栈底为#
推荐精选
{
S->stack[0]='#';
S->top = 1;
}
void StackPush1(SeqStack1 *S,DataType x) //将元素压入堆栈1
{ 13、
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"< 14、 15、[500],char b[500][100],SeqStack1 *S,int n)//将待求表达式子转换为后缀形式
{
int i,j,k=0;
char character;
for(i=0;i 16、cter=='#'&&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]); //当中缀表达式当前运算符优先级较高时，进栈
17、 break;
}
else if(character=='('&&a[i]==')') //'('和')'相遇时，将'('退栈，接着读下面的
{
StackPop1(S,&character);
break;
}
else
{
StackPop1(S,&character); //当栈顶元素优先级较高时，退栈
b[k][0]=character;
b[k][1]=0;
k++; 18、
continue;
}
}
推荐精选
continue;
}
if(!IsOptr(a[i]))
{
j=0;
while(!IsOptr(a[i]))
{
b[k][j]=a[i]; //当前为变量时，直接存入二维数组b中
j++;
i++;
}
i--;
b[k][j]=0; //表示该行结束
k++;
}
}
return 0;
19、
}
#include 20、top;
}SeqStack2;
void Initiate(BiTreeNode **root) //初始化树的根结点
{
*root = (BiTreeNode * ) malloc(sizeof(BiTreeNode));
(*root)->leftChild=NULL;
(*root)->rightChild=NULL;
推荐精选
(*root)->parent=NULL;
}
void print(BiTreeNode *bt,int n) //逆时针 21、打印二叉树
{
int i,j,m;
if(bt==NULL) return;
print(bt->rightChild,n+1);
for(i=0;i 22、/////////////////////////////////////////////////////////////////////////////////////////////
void StackInitiate2(SeqStack2 *S) //初始化堆栈2
{
S->top = 0;
}
void StackPush2(SeqStack2 *S,BiTreeNode *x) //将二叉树结点压入堆栈2
{
S->address[S->top] = x;
S-> 23、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);
24、
for(i=0;i 25、rightChild=q; //将弹出后的结点作为右孩子
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->paren 26、t=p;
p->leftChild=o;
p->rightChild=q;
StackPush2(&s,p); //根结点入栈
}
else
{
StackPush2(&s,p);
}
}
p=StackPop2(&s); //弹出构造好的二叉数的根结点指针，并返回
return p;
}
int PostOrder(BiTreeNode *t,int c[500],cha 27、r 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;
}
els 28、e 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 29、{
if(!(strcmp( b[i],t->data))) break; //当该结点数据域为变量时
}
return c[i]; //直接返回该变量的真值
}
}
return -1;
}
ypedef struct snode
{
DataType data;
struct snode* next;
}LSNode; //定义链式堆栈的结点，用于下面检测表达式的括号匹配
void StackInitiate(LSNode** head 30、)
{
推荐精选
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;
}//检测堆栈是否为空的函数，若为空，返回0，否则返回1
int StackPush(LSNode* head,DataType x)
{
LSNode* p;
if((p=(LSNode*)mal 31、loc(sizeof(LSNode)))==NULL)
{
cout<<"内存空间不足无法插入!"< 32、t=p->next;
*d=p->data;
free(p);
return 1;
}//弹出栈顶元素
int StackTop(LSNode* head,DataType *d)
{
推荐精选
LSNode* p=head->next;
if(p==NULL)
{
cout<<"堆栈已空出错"< 33、NULL)
{
p1=p;
p=p->next;
free(p1);
}
}
void ExplsCorrect(char exp[]) //检测输入表达式的括号匹配函数
{
LSNode *head;
int i=0;
char c;
StackInitiate(&head);
while(exp[i]) //表达式没读完时，执行'while'循环
{
if(exp[i]=='(')StackPush(head,exp[i]); //遇到左括号'('将其进栈
34、 else if(exp[i]==')'&&StackNotEmpty(head)&&StackTop(head,&c)&&c=='(')StackPop(head,&c); //栈顶元素为'('且当前元素为')'时，出栈，继续读下面的字符
else if (exp[i]==')'&&StackNotEmpty(head)&&StackTop(head,&c)&&c!='(')//栈顶元素不为'('且当前元素为')'时，输出'左右括号不匹配'，退出重新输入
{
cout<<"左右括号配对次序不正确!"< 35、 if((exp[i]==')')&&!StackNotEmpty(head)) //当前元素为')'但是堆栈已空时候，输出
推荐精选
'右括号多于左括号'，退出程序重新输入
{
cout<<"右括号多于左括号!"< 36、正确"< 37、in()
{
char a[500],b[500][100];
int i,j,n,End,flag,c[500],num=0; //c数组用来存放变量的真值
char m='y';
SeqStack1 S;
BiTreeNode *P;
cout<<"\t\t*********************************************"< 38、t<<"\t\t** * * * * * * * * * * **"< 39、******************************"< 40、
//测试输出后序表达式//
cout<<"-------------------------"< 41、dl;
cout<<"\n\n构造的二叉树结构为:"< 42、][0]))
推荐精选
{
num++;
}
}
while(1)
{
cout<<"\n\t\t 请为变量赋值<0:false or 1:true>\n"< 43、} //有重复变量时flag为1，且找到第一个重复变量b[j]
}
if(flag==0)
{
cout<<">>>>>请输入上述表达式中的变量“"< 44、把重复出现的变量都用第一次的值赋值
}
}
else c[i]=-1;
}
End=PostOrder(P,c,b,n);
cout<<"\n>>>>>该表达式的最后结果为："< 45、;
for(p=0;p 46、nd=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':继续下一个表达式的计算 'n':退出程序"<
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
