搜索
合肥学院计算机科学与技术系课程设计报告2016～2017学年第1学期课程数据结构与算法课程设计题目名称重言式的判别学生姓名王芳学号1404011018专业班级计算机科学与技术14级1班指导教师李红何立新2016年9月一、题目【问题描述】一个逻辑表达式如果对于其变元的任一种取值都为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式；然而，更多的情况下，既非重言式，也非矛盾式。试写一个程序，通过真值表判别一个逻辑表达式属于上述哪一类。【基本要求】(1)逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括|，&和~，分别表示或、与和非，运算优先程度递增，但可由括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。(2)若是重言式或矛盾式，可以只显示Trueforever，或Falseforever，否则显示Satisfactible以及变量名序列，与用户交互。若用户对表达式中变元取定一组值，程序就求出并显示逻辑表达式的值。【测试数据】(1)(A|~A)&(B|~B)(2)(A&~A)&C(3)A|B|C|D|E|~A(4)A&B&C&~B(5)(A|B)&(A|~B)(6)A&~B|~A&B;O,0;0,1;1,0;1,1。二、问题分析1、一个逻辑表达式如果对于其变元的任一种取值均为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式，若对于其变元的任一种取值既有真，又有假，则称其为可满足式。写一个程序通过真值表判别一个逻辑表达式属于上述哪一类。基本要求如下：1)逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括“|”、“&”、“~”，分别表示或、与、非，运算优先程度递增，但可有括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。2)若是重言式或矛盾式，可以只显示“TrueForever”或“FalseForever”，否则显示运算中每种赋值和与其相对应的表达式的值。2、通过真值表判别逻辑表达式是否为重言式，需解决以下问题：1)对逻辑表达式中空格符的处理。为了方便对逻辑表达式进行扫描判断，应先去掉表达式中的空格符。2)算符的优先级问题在带括号的表达式中，界限符包括左右括号以及表达式起始、结束符“#”。对于一个简单的表达式求值运算规则如下：（1）从左至右依次计算。（2）先取反，然后相与，后相或。（3）先括号内，后括号外。为统一算法的描述，将运算符和界限符统称为算符。这样，算符集为{~，&，|，（，），#}。根据上述3条规则，两个前后相继出现的算符a1，a2间的优先关系可以归纳如下：（1）若a1,a2同为“&”或同为“|”，则算符a1的优先级大于a2。（2）“~”、“&”、“|”的优先级依次减小。（3）由于先括号内，后括号外，若a1为“|”、“&”、“~”，a2为“（”；或者，a1为“（”，而a2为“|”、“&”、“~”，则a1的优先级小于a2。（4）同理，若a1为“|”、“&”、“~”，a2为“）”；或者，a1为“）”，而a2为“|”、“&”、“~”，则a1的优先级大于a2。（5）若a1、a2同为“（”，则a1的优先级小于a2；若a1、a2同为“）”，则a1的优先级大于a2。（6）表达式的起始、结束符“#”的优先级小于其他所有合法出现的算符。（7）若a1为“（”，a2为“）”；或者，a1、a2同为“#”，则a1、a2优先级相同。综上所述，将两个相继出现的算符a1、a2的优先关系进行归纳如表1所示。表1算符a1和a2间的优先关系a1a2|&~()#|&~(=___)___#___=我们可以将逻辑表达式的计算类比算术表达式的计算，通常借助堆栈来实现按运算符的优先级完成表达式的求值计算。一个是存放运算符栈，另一个是存放变量或中间结果栈。（1）首先初始化算符栈logic和变量栈，并将表达式的起始符“#”压入算符栈logic。（2）依次读入表达式中的每个字符。若是变量，则为其分配结构node的size大小的内存,强制转换为bitree类型，并将其压入变量栈variable；若是运算符，则为其分配结构node的size大小的内存,强制转换为bitree类型，并与运算符栈logic的栈顶算符进行优先级比较，并作如下处理：①若栈顶算符a1的优先级低于刚读入的算符a2，则将a2压入运算符栈logic。②若栈顶算符a1的优先级高于刚读入的算符a2，则将a1出栈，同时将变量栈variable出栈一次，得到变量A，再判断栈顶算符a1是否为“~”，如果a1不是“~”，则继续出栈变量栈variable一次，得到变量B，将a1作为根结点，B作为a1的左孩子，A作为a1的右孩子，并将根结点a1压入变量栈variable；如果栈顶算符a1是“~”，则将a1作为根结点，A作为a1的右孩子，a1的左孩子则为空，并将根结点a1压入变量栈。③若栈顶算符a1优先级与刚读入的算符a2的优先级相同，说明左右括号相遇，或者是表达式的起始、结束符相遇，只需将栈顶算符（左括号或起始符）出栈即可；当运算符栈logic空时，算法结束这样就可以将逻辑表达式构造成一棵完整二叉树，根结点是优先级最小的算符（除了括号和起始结束符，在构造二叉树的过程中已被脱去）。如(A|~A)&(B|~B)构造成的二叉树如图1所示图1表达式构造的二叉树1)变量的赋值问题若只有1个变量，则有21种情况的赋值；若有2个变量，易知有22种情况的赋值；若有3各变量，则有23种情况的赋值，那么如果有n个变量，就有2n种情况的赋值。既然要对变量进行赋值，首先要找到逻辑表达式中的变量，并确定变量的个数。2)逻辑表达式取值的判断由上述对运算符的优先级的分析可知，对逻辑表达式的计算，就是中序遍历由优先级确定的逻辑表达式构成的二叉树。5）重言式的判别可以将给变量的所有赋值的逻辑表达式的逻辑值相加，如果相加结果与2n相等，则为重言式；若相加结果为0，则为矛盾式；否则为可满足式。本问题的关键和难点在于算符优先级的判断和二叉树的构造。三、数据结构的选择和概要设计1、数据结构的选择通过问题分析可知，需要用到的数据结构有堆栈和二叉树。1)对于堆栈选用顺序栈结构来进行存放算符或变量，存放的都是二叉树的结点。设有两个堆栈，一个是存放运算符栈，另一个是存放变量或中间结果栈。2)对于二叉树，选用二叉树的链接存储结构，其结点存放得都是表达式中的元素。将表达式构造成一棵二叉树。2、概要设计从整体上可以分为三个模块：第一个模块：属于堆栈和二叉树结点类型的定义typedefstructstack//识别表达式使用的堆栈定义,它存放的都是树的结构{//栈中的元素都是树的结点结构bitree*base;//栈底指针bitree*top;//栈顶指针intstacksize;//栈容量}seqstack;typedefstructnode//根据表达式建立的二叉树的结点定义{chardata;structnode*lchild;structnode*rchild;}BiTNode,*bitree;第二个模块：主要函数及其功能。堆栈的创建voidcreatstack(sqstack&st){}；初始化栈voidsetstack(seqstack&st){}；进栈voidpush(sqstack&st,bitreee){}；出栈voidpop(sqstack&st,bitree&e){}；将逻辑表达式中的元素转换为二叉树结点的形式，使栈中存储的都是二叉树的结点。voidcreattree(chars[],bitree&tree){}；通过优先级将逻辑表达式构造成一颗完整的二叉树voidcreate(bitree&zigen,bitreel,bitreer){}；对逻辑表达式求值intvaluetree(bitreetree){}；生成变量的各种取值组合voidcreatzuhe(intn,intm,chara[]){}；逻辑运算符的优先级判别，返回值为“”、“”、“=”charyouxianji(charm,charn){}；第四个模块为于用户的交互voiduser(){}；流程图：图2程序流程图四、算法思想1、穷举法思想通过真值表来判断重言式，需要一一给变量赋值，共有2^n中情况（n表示变量的个数），这里用到穷举的思想。2、递归与分治思想每给变量赋一组值，通过递归中序遍历二叉树求值，这里用到了递归与分治开始mainmeun输入表达式1.计算机2.用户3.3.返回建树建树计算机穷举用户输入变量值输出结果继续结束213NY思想。3、运算符的优先级判断思想（见问题分析算符的优先级问题分析第5页）五、详细设计和主要编码段首先将用户输入的逻辑表达式存到char*str当中，然后去除逻辑表达式中的空格符。for(;*pstr!=NULL;pstr++,n++){if(str[n]!='')stri[i++]=*pstr;//去除表达式中的空格}此时stri当中存储的就是没有空格符的逻辑表达式。通过问题分析，需找到表达式中的变量，并确定变量的个数。下面的代码就是实现此功能。for(intk=0;kstrlen(stri);k++)if(stri[k]=65&&stri[k]=90)//找到变量{intmark=0;//标记变量for(intj=0;jm;j++){if(bl[j]==stri[k])//将找到的变量与bl[]中已找到过的变量比较，若相等则将变量标记置为1，表示找到的变量在前面已出现过{mark=1;break;}}if(mark==0)//若标记为0，表示找到的变量没有重复，并将其记录到bl[]中，变量个数m加1。{bl[m]=str[k];m++;//m是变量个数}}此时bl[]当中存储的就是变量，m就是变量个数，那么变量赋值的情况就有2m种。下面对生成变量的各种取值组合的算法进行分析和说明。intzuhe[30]用来存储变量的取值组合，为了方便说明，采用两个变量进行算法叙述。AB第n次数000011102113表2变量赋值实例从表2可以发现给变量赋值的次数n与变量的取值组合成的二进制数相等，能得到一个规律：变量的取值组合zuhe[]二进制数（从低位到高位）的第i位数取值等于(ni)%2。用一下代码可以实现第n次对变量的赋值组合intlzp=m;for(inti=0;im;i++){zuhe[bl[lzp]-65]=(ni)%2;lzp--;}下面说明优先级的判断。charbijiao[7][7]用来存放算符间的优先关系表中的数据。inti,j;bijiao[7][7]={'','|','&','~','(',')','#',//二维数组比较优先级先后'|','','','','','','','&','','','','','','','~','','','','','','','(','','','','','=','',')','','','','','','','#','','','','','','='};for(i=0;i7;i++)if(bijiao[0][i]==a2)//找到a2运算符的列号break;for(j=0;j7;j++)//找到a1运算符的行号if(bijiao[j][0]==a1)break;returnbijiao[j][i];//返回优先级的符号:、、=下面说明将表达式构成二叉树的过程。s=stri是逻辑表达式的首地址。while(*s!=NULL)//循环条件，为空则扫描结束{if(int(*s)=65&&int(*s)=90)//读取的是变量{variables=(bitree)malloc(sizeof(node));//分配结构node的size大小的内存,强制转换为bitree类型variables-data=*s;push(variab