重言式判别源码及课程设计-c语言版

重言式的判别题目：一个逻辑表达式如果对于其変元的任一种取值都为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式；然而，更多的情况下，既非重言式，也非矛盾式。试写一程序，通过真值表判别一个逻辑表达式属于上述哪一类。一、需求分析1、逻辑表达式从终端输入，长度不超过一行。2、逻辑运算符包括“|”“&”“~”表示或与非。运算符优先程度递增，但是可由括号改变。3、逻辑变元为大写字母表达式中任何地方都可以含有多个空格符。4、运用自底向上的算符优先法5、重言式显示“trueforever”;矛盾式显示“falseforever”；否则显示“satisfactible”。二、概要设计为实现上述需求需要用到自底向上的算符优先法，和自顶向下分割，先序遍历建立二叉树的方法。自底向上的算符优先法：charOPTRCHART[7][7]={'','|','&','~','(',')','#','|','','','','','','','&','','','','','','','~','','','','','','','(','','','','','=','',')','','','','','','','#','','','','','','='};switch(cmp(GetTop(&OPTR)-data,*p)){case'':break;case'=':break;case'':break;}/*switch*/建立二叉树：typedefstructBiTNode{structBiTNode*Lchild;structBiTNode*Rchild;ElemTypedata;}BiTNode,*BiTree;栈中的操作：typedefstructNode{BiTree*base;BiTree*top;intstacksize;}SqStack;入栈操作及出栈销毁栈的操作：intInitStack(SqStack*stack){stack-base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree));if(!stack-base)exit(OVERFLOW);stack-top=stack-base;stack-stacksize=STACK_INIT_SIZE;returnOK;}BiTreeGetTop(SqStack*stack){if(stack-top==stack-base)returnNULL;return*(stack-top-1);}intPush(SqStack*stack,BiTreeBitnode){if(stack-top-stack-base=stack-stacksize){stack-base=(BiTree*)realloc(stack-base,(stack-stacksize+STACKINCREAMENT)*sizeof(BiTree));if(!stack-base)exit(OVERFLOW);stack-top=stack-base+stack-stacksize;stack-stacksize+=STACKINCREAMENT;}*(stack-top)=Bitnode;stack-top++;returnOK;}BiTreePop(SqStack*stack){if(stack-top==stack-base)returnERROR;return*(--stack-top);}intDestroyStack(SqStack*stack){free(stack-base);returnOK;}三、详细设计详细程序如下：#includestdio.h#includemalloc.h#includemath.h#includestdlib.h#defineOK1#defineERROR0#defineVARIMAXNUM20#defineSTARMAXLEN100#defineSTACK_INIT_SIZE100//栈的最大长度#defineSTACKINCREAMENT10//每次增加的栈的长度#defineElemTypechar将elemtype定义为char型typedefstructBiTNode//创建树节点按照书上原样创建{structBiTNode*Lchild;structBiTNode*Rchild;ElemTypedata;//字符型}BiTNode,*BiTree;typedefstructNode//栈{BiTree*base;BiTree*top;intstacksize;}SqStack;charOPTRCHART[7][7]=//此举是为了后面的优先级考虑{'','|','&','~','(',')','#','|','','','','','','','&','','','','','','','~','','','','','','','(','','','','','=','',')','','','','','','','#','','','','','','='};intInitStack(SqStack*stack)//初始化栈{stack-base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree));if(!stack-base)exit(OVERFLOW);stack-top=stack-base;stack-stacksize=STACK_INIT_SIZE;returnOK;}BiTreeGetTop(SqStack*stack)//返回值为BiTree类型的取栈头{if(stack-top==stack-base)returnNULL;return*(stack-top-1);}intPush(SqStack*stack,BiTreeBitnode)//将树的节点放进栈的操作，入栈{if(stack-top-stack-base=stack-stacksize){stack-base=(BiTree*)realloc(stack-base,(stack-stacksize+STACKINCREAMENT)*sizeof(BiTree));if(!stack-base)exit(OVERFLOW);stack-top=stack-base+stack-stacksize;stack-stacksize+=STACKINCREAMENT;}*(stack-top)=Bitnode;stack-top++;returnOK;}BiTreePop(SqStack*stack)//取值指针后移{if(stack-top==stack-base)returnERROR;return*(--stack-top);}intDestroyStack(SqStack*stack)//毁栈{free(stack-base);returnOK;}charstr[STARMAXLEN];intvaritab[VARIMAXNUM+1];intsum;BiTreeroot;SqStackOPTR,OPND;charcmp(chara,charb)//取左右交叉的符号即“”“”“=”{inti,j;for(i=0;i=6;i++){if(OPTRCHART[i][0]==a)break;}for(j=0;j=6;j++){if(OPTRCHART[0][j]==b)break;}returnOPTRCHART[i][j];}voidCreatBiTree()//建树{BiTreetemp,a,b;char*p=str;temp=(BiTree)malloc(sizeof(BiTNode));temp-data='#';Push(&OPTR,temp);while((*p!='#')||(GetTop(&OPTR)-data!='#')){if((*p=65)&&(*p=90)||(*p=97)&&(*p=122)){temp=(BiTree)malloc(sizeof(BiTNode));temp-data=*p;temp-Lchild=NULL;temp-Rchild=NULL;Push(&OPND,temp);p++;}else{switch(cmp(GetTop(&OPTR)-data,*p))//开始判断优先级{case'':temp=(BiTree)malloc(sizeof(BiTNode));temp-data=*p;temp-Lchild=NULL;temp-Rchild=NULL;Push(&OPTR,temp);p++;break;case'=':temp=Pop(&OPTR);free(temp);p++;break;case'':temp=Pop(&OPTR);b=Pop(&OPND);temp-Rchild=b;if(temp-data!='~'){a=Pop(&OPND);temp-Lchild=a;}Push(&OPND,temp);break;}/*switch*/}/*else*/}/*while*/root=Pop(&OPND);temp=Pop(&OPTR);free(temp);}voidDestroyBiTree(BiTreetree){//销毁树并取出需要的值if(!tree){return;}elseif((tree-Lchild==NULL)&&(tree-Rchild==NULL)){free(tree);return;}else{DestroyBiTree(tree-Lchild);DestroyBiTree(tree-Rchild);free(tree);}}intGetValue(BiTreetree){if(!tree){return0;}elseif((tree-data=65)&&(tree-data=90)){returnvaritab[tree-data-64];}elseif((tree-data=97)&&(tree-data=122)){returnvaritab[tree-data-96];}else{switch(tree-data){case'|':return(GetValue(tree-Lchild)||GetValue(tree-Rchild));case'&':return(GetValue(tree-Lchild)&&GetValue(tree-Rchild));case'~':return(!GetValue(tree-Rchild));}}}voiddestroy()//销毁栈{DestroyStack(&OPTR);DestroyStack(&OPND);}voidinit(){InitStack(&OPTR);InitStack(&OPND);*varitab=0;sum=(int)pow(2.0,*varitab);root=NULL;str[0]='#';}voidinput(){//为了能继续输入需要判别的式子char*p,*q;printf(请输入要判断的式子中变量的数目\n);scanf(%d,varitab);while(*varitab0){printf(错误，请重新输入数字！\n);printf(请输入要判断的式子中变量的数目:\n);scanf(%d,varitab);}getchar();sum=(int)pow(2.0,*varitab);printf(输入要判别的式子：\n);gets(st