计算命题演算公式真值(数据结构C语言版)实习报告

计算命题演算公式的真值李仙伟014072-281．需求分析1.1.命题演算公式由逻辑变量（其值为TRUE或FALSE）和逻辑运算符∧（AND）、∨（OR）和┐（NOT）按一定规则所组成的公式。公式运算的先后顺序为┐、∧、∨，而括号（）可以改变优先次序。1.2.输入输出以人机对话的方式让用户输入要计算的命题表达式；计算出最后的真值并输到屏幕上。1.3.测试数据:①~((~a&b)|c)&d②~(boy&girl）|father）&mother③(5&~99)|02．概要设计2.1.基本思想：①利用二叉树计算公式的真值:第一步:利用堆栈将中缀形式的公式变为后缀形式；第二步:根据后缀形式，从叶结点开始构造相应的二叉树；第三步:按后序遍历该树，求各子树之值，即每到达一个结点，其子树之值已经计算出来，当到达根结点时，求得的值就是公式之真值；②逻辑变元的标识符不限于单字母，而可以是任意长的字母数字串；③根据用户的要求显示表达式的真值表。2.2.程序设计的概要图如下所示：2.3.抽象数据类型的定义及其相应的操作函数定义如下：①/*定义一个堆栈SeqStack1，用来实现将输入的中缀表达式转换为后缀表达式*/typedefcharDataType；typedefstruct{DataTypestack[MaxStackSize];inttop;}SeqStack1;/*初始化SeqStack1，栈底为‘#’*/voidStackInitiate1(SeqStack1*S)/*将元素压入SeqStack1*/voidStackPush1(SeqStack1*S,DataTypex)/*SeqStack1出栈*/voidStackPop1(SeqStack1*S,DataType*x)/*取SeqStack1的栈顶元素*/intStackTop1(SeqStack1S,DataType*d)②/*定义链式堆栈LSNode，用于检测表达式的括号匹配*/typedefstructsnode{DataTypedata;Structsnode*next;}LSNode;/*初始化堆栈LSNode*/voidStackInitiate(LSNode**head)/*判断堆栈LSNode是否为空的函数，空返回0，否则返回1*/intStackNotEmpty(LSNode*head)/*LSNode入栈函数*/intStackPush(LSNode*head,DataTypex)/*LSNode出栈函数*/intStackPop(LSNode*head,DataType*d)/*LSNode取栈顶元素*/intStackTop(LSNode*head,DataType*d)/*撤消LSNode动态申请空间*/voidDestroy(LSNode*head)③/*检测输入表达式的括号匹配函数*/voidExpIsCorrect(charexp[])④/*定义二叉树的结点BiTreeNode*/typedefstructNode{DataTypedata[MaxStackSize];structNode*leftChild;structNode*rightChild;structNode*parent;}BiTreeNode;/*初始化BiTreeNode的根结点*/voidInitiate(BiTreeNode**root)/*将BiTreeNode结点压入堆栈2*/voidStackPush2(SeqStack2*S,BiTreeNode*x)/*逆时针打印BiTreeNode*/voidprint(BiTreeNode*bt,intn)⑤/*定义一个顺序堆栈SeqStack2，用于构造二叉树时对结点的保存*/typedefstruct{BiTreeNode*Save[MaxStackSize];inttop;}SeqStack2;/*初始化SeqStack2*/voidStackInitiate2(SeqStack2*S)/*SeqStack2出栈*/BiTreeNode*StackPop2(SeqStack2*S)⑥/*将待求表达式子转换为后缀形式*/intConvert(chara[MaxSize1],charb[MaxSize1][MaxSize2],SeqStack1*S,intn)⑦/*根据上面转换的表达式的后缀形式，构造相应的二叉树*/BiTreeNode*BuildTree(charb[MaxSize1][MaxSize2],intn)⑧/*后序遍历该树，并且每到达一个结点时候，计算其子树之值，当到达根结点时，求得的值就是公式之真值。*/intPostOrder(BiTreeNode*t,intc[MaxSize1],charb[MaxSize1][MaxSize2],intn)⑨/*主函数*/voidmain()3．详细设计#includestdafx.h#includemalloc.h#includestring.htypedefcharDataType;#includestdlib.htypedefstructsnode/*定义链式堆栈的结点，用于检测表达式的括号匹配*/{DataTypedata;structsnode*next;}LSNode;voidStackInitiate(LSNode**head)/*初始化堆栈*/{if((*head=(LSNode*)malloc(sizeof(LSNode)))==NULL)exit(1);(*head)-next=NULL;}intStackNotEmpty(LSNode*head)/*检测堆栈是否为空的函数，若为空，返回0，否则返回1*/{if(head-next==NULL)return0;elsereturn1;}intStackPush(LSNode*head,DataTypex)/*将元素入栈*/{LSNode*p;if((p=(LSNode*)malloc(sizeof(LSNode)))==NULL){printf(\t内存空间不足无法插入!\n);return0;}p-data=x;p-next=head-next;head-next=p;return1;}intStackPop(LSNode*head,DataType*d)/*出栈*/{LSNode*p=head-next;if(p==NULL){printf(\t堆栈空出错\n);return0;}head-next=p-next;*d=p-data;free(p);return1;}intStackTop(LSNode*head,DataType*d)/*取栈顶元素*/{LSNode*p=head-next;if(p==NULL){printf(\t堆栈已空出错\n);return0;}*d=p-data;return1;}voidDestroy(LSNode*head){LSNode*p,*p1;p=head;while(p!=NULL){p1=p;p=p-next;free(p1);}}/*检测输入表达式的括号匹配函数*/voidExplsCorrect(charexp[]){LSNode*head;inti=0;charc;StackInitiate(&head);while(exp[i])/*表达式没读完时，执行'while'循环*/{if(exp[i]=='(')StackPush(head,exp[i]);/*遇到左括号'('将其进栈*/elseif(exp[i]==')'&&StackNotEmpty(head)&&StackTop(head,&c)&&c=='(')StackPop(head,&c);/*栈顶元素为'('且当前元素为')'时，出栈，继续读下面的字符*/elseif(exp[i]==')'&&StackNotEmpty(head)&&StackTop(head,&c)&&c!='(')/*栈顶元素不为'('且当前元素为')'时，输出'左右括号不匹配'，退出重新输入*/{printf(\n\t左右括号配对次序不正确!\n);exit(1);}elseif((exp[i]==')')&&!StackNotEmpty(head))/*当前元素为')'但是堆栈已空时候，输出'右括号多于左括号'，退出程序重新输入*/{printf(\n\t右括号多于左括号!\n);exit(1);}i++;}if(StackNotEmpty(head))/*此时若堆栈非空，则输出'左括号多于右括号'，退出程序重新输入*/{printf(\n\t左括号多于右括号!\n);exit(1);}elseprintf(\n\t左右括号匹配正确\n);/*若此时堆栈为空，表明输入的表达式左右括号匹配正确，继续执行下面的程序*/printf(\n);printf(----------------------------------------------------------------------------\n);printf(\t其后缀表达式子为:\n);}typedefstruct{DataTypestack[1000];inttop;}SeqStack1;/*用来实现将输入的中缀表达式转换为后缀表达式*/typedefstructNode{DataTypedata[1000];structNode*leftChild;structNode*rightChild;structNode*parent;}BiTreeNode;/*定义二叉树的结点*/typedefstruct{BiTreeNode*address[1000];/*定义成树结点的指针，方便下面构造二叉树时，对结点的保存*/inttop;}SeqStack2;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){printf(\t堆栈已空!\n);return0;}else{*d=S.stack[S.top-1];return1;}}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++)printf();if(n=0){printf(---);m=strlen(bt-data);for(j=0;jm;j++)printf(%c,bt-data[j]);printf(\n);}print(bt-leftChild,n+1);}voidStackInitiate2(SeqStack2*S)/*初始化堆栈2*/{S-top=0;}voidStackPush2(SeqStack2*S,BiTreeNode*x)/*将二叉树结点压入堆栈2*/{S-address[S-top]=x;S-