计算命题演算公式的真值

四计算命题演算公式的真值一．实验题目所谓命题演算公式是指由逻辑变量（其值为TRUE或FALSE）和逻辑运算符∧（AND）、∨（OR）和┐（NOT）按一定规则所组成的公式（蕴含之类的运算可以用∧、∨和┐来表示）。公式运算的先后顺序为┐、∧、∨，而括号（）可以改变优先次序。已知一个命题演算公式及各变量的值，要求设计一个程序来计算公式的真值。要求：（1）利用二叉树来计算公式的真值。首先利用堆栈将中缀形式的公式变为后缀形式；然后根据后缀形式，从叶结点开始构造相应的二叉树；最后按后序遍历该树，求各子树之值，即每到达一个结点，其子树之值已经计算出来，当到达根结点时，求得的值就是公式之真值。（2）逻辑变元的标识符不限于单字母，而可以是任意长的字母数字串。（3）根据用户的要求显示表达式的真值表。二．实验设计1.设计思想（1）数据结构设计a建立一个链式堆栈，实现括号的匹配问题。b建立一个顺序堆栈，来实现中缀转后缀并实现二叉树的打印。（2）算法设计a.括号匹配b中缀转后缀c打印二叉树和真值表2.设计表示自定义和调用的函数如下所示：#includevalue.h#includeConvert.h#includestdio.h#includeiostream.h#includemalloc.h#includemath.h#includestring.h函数说明如下SeqStack1;/*定义一个堆栈SeqStack1*/voidStackInitiate1(SeqStack1*S)/*初始化堆栈1，栈底为‘#’*/voidStackPush1(SeqStack1*S,DataTypex)/*将元素压入堆栈1*/voidStackPop1(SeqStack1*S,DataType*x)/*弹出堆栈1的栈顶元素*/intStackTop1(SeqStack1S,DataType*d)/*取堆栈1的栈顶元素*/SeqStack2;/*定义一个顺序堆栈SeqStack2*/voidStackInitiate2(SeqStack2*S)/*初始化堆栈2*/BiTreeNode*StackPop2(SeqStack2*S)/*从堆栈2中弹出栈顶元素*/BiTreeNode;/*定义二叉树的结点*/voidInitiate(BiTreeNode**root)/*初始化树的根结点*/voidprint(BiTreeNode*bt,intn)/*逆时针打印二叉树*/voidStackPush2(SeqStack2*S,BiTreeNode*x)/*将二叉树结点压入堆栈2*/intConvert(chara[500],charb[500][100],SeqStack1*S,intn)/*将待求表达式转换为后缀形式*/BiTreeNode*BuildTree(charb[500][100],intn)/*根据表达式的后缀形式，构造相应的二叉树*/LSNode;/*定义了链式堆栈用于下面检测表达式的括号匹配*/voidStackInitiate(LSNode**head)/*初始化堆栈*/intStackNotEmpty(LSNode*head)/*检测堆栈是否为空的函数*/intStackPush(LSNode*head,DataTypex)/*将元素入栈*/intStackPop(LSNode*head,DataType*d)/*弹出栈顶元素*/intStackTop(LSNode*head,DataType*d)/*取栈顶元素*/voidDestroy(LSNode*head)/*撤消*/voidExplsCorrect(charexp[])/*检测输入表达式的括号匹配函数*/i3.详细设计voidStackInitiate(LSNode**head){if((*head=(LSNode*)malloc(sizeof(LSNode)))==NULL)exit(1);(*head)-next=NULL;}/*初始化堆栈*/intStackNotEmpty(LSNode*head){if(head-next==NULL)return0;elsereturn1;}/*检测堆栈是否为空的函数，若为空，返回0，否则返回1*/typedefstructsnode{DataTypedata;structsnode*next;}LSNode;/*定义了链表的结点用于下面检测表达式的括号匹配*/intStackPop(LSNode*head,DataType*d){LSNode*p=head-next;if(p==NULL){cout堆栈已空出错endl;return0;}head-next=p-next;*d=p-data;free(p);return1;}/*弹出栈顶元素*/intStackPush(LSNode*head,DataTypex){LSNode*p;if((p=(LSNode*)malloc(sizeof(LSNode)))==NULL){cout内存空间不足无法插入!endl;return0;}p-data=x;p-next=head-next;head-next=p;return1;}/*将元素入栈*/intStackTop(LSNode*head,DataType*d){LSNode*p=head-next;if(p==NULL){cout堆栈已空出错endl;return0;}*d=p-data;return1;}/*取栈顶元素*/voidDestroy(LSNode*head){LSNode*p,*p1;p=head;while(p!=NULL){p1=p;p=p-next;free(p1);}}/*撤消*/三．调试分析在运行程序的过程中，碰到了一些错误，其中有很多是括号和分号的问题，看来以后写程序要更加细心才行。四．用户手册此程序中'&''|''~'分别代表代表'与''或''非'运算首先输入一个包含变量，运算符表达式，再按Enter执行。再依次输入各变量的值。如果不继续输入，按0退出。再按y继续或者n退出。五．测试数据及测试结果输入a&b&c六．源程序清单typedefstruct{DataTypestack[1000];inttop;}SeqStack1;//用来实现将输入的中缀表达式转换为后缀表达式voidStackInitiate1(SeqStack1*S)//初始化，栈底为#{S-stack[0]='#';S-top=1;}voidStackPush1(SeqStack1*S,DataTypex)//将元素压入堆栈1{S-stack[S-top]=x;S-top++;}voidStackPop1(SeqStack1*S,DataType*x)//弹出堆栈1的栈顶元素{S-top--;*x=S-stack[S-top];}intStackTop1(SeqStack1S,DataType*d)//取堆栈1的栈顶元素{if(S.top=0){cout堆栈已空!\nendl;//printf(堆栈已空!\n);return0;}else{*d=S.stack[S.top-1];return1;}}intIsOptr(DataTypec)/*判断c是否为运算符*/{switch(c){case'&':case'|':case'~':case'(':case')':case'#':return1;default:return0;}}intConvert(chara[500],charb[500][100],SeqStack1*S,intn)//将待求表达式子转换为后缀形式{inti,j,k=0;charcharacter;for(i=0;in;i++){if(IsOptr(a[i])){while(IsOptr(a[i])){StackTop1(*S,&character);if(character=='#'&&a[i]=='#')returnk;//此时堆栈和当前都为‘#’时结束算法elseif((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]);//当中缀表达式当前运算符优先级较高时，进栈break;}elseif(character=='('&&a[i]==')')//'('和')'相遇时，将'('退栈，接着读下面的{StackPop1(S,&character);break;}else{StackPop1(S,&character);//当栈顶元素优先级较高时，退栈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];//当前为变量时，直接存入二维数组b中j++;i++;}i--;b[k][j]=0;//表示该行结束k++;}}return0;}#includestdlib.htypedefstructNode{DataTypedata[1000];structNode*leftChild;structNode*rightChild;structNode*parent;}BiTreeNode;//定义二叉树的结点typedefstruct{BiTreeNode*address[1000];//定义成树结点的指针，方便下面构造二叉树时，对结点的保存inttop;}SeqStack2;voidInitiate(BiTreeNode**root)//初始化树的根结点{*root=(BiTreeNode*)malloc(sizeof(BiTreeNode));(*root)-leftChild=NULL;(*root)-rightChild=NULL;(*root)-parent=NULL;}voidprint(BiTreeNode*bt,intn)//逆时针打印二叉树{inti,j,m;if(bt==NULL)return;print(bt-rightChild,n+1);for(i=0;in;i++)cout;if(n=0){cout---;m=strlen(bt-data);for(j=0;jm;j++)coutbt-data[j];coutendl;}print(bt-leftChild,n+1);}/////////////////////////////////////////////////////////////////////////////////////////////////////////voidStackInitiate2(SeqStack2*S)//初始化堆栈2{S-top=0;}voidStackPush2(SeqStack2*S,BiTreeNode*x)//将二叉树结点压入堆栈2{S-address[S-top]=x;S-top++;}BiTreeNode*StackPop2(SeqStack2*S)//从堆栈2中弹出栈顶元素{BiTreeNode*x;S-top--;x=S-address[S-top];returnx;}BiTreeNode*BuildTree(charb[500][100],intn){inti;BiTreeNode*p,*q,*o;