重言式判别-课程设计报告

1、重视服务群众的最后一公里"（声音）合肥学院计算机科学与技术系课程设计报告20162017学年第1学期页脚内容3课程课程设计题目数据结构与算法名称学生姓名学号专业班级指导教师王芳1404011018计算机科学与技术14级1班李红 何立新2016年9月一、题目【问题描述】一个逻辑表达式如果对于其变元的任一种取值都为真，则称为重言式；反之,如果对于其变元的任一种取值都为假，则称为矛盾式；然而，更多的情况下，既 非重言式，也非矛盾式。试写一个程序，通过真值表判别一个逻辑表达式属于上 述哪一类。【基本要求】(1)逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括"|",

2、"&"和 "”,分别表示或、与和非，运算优先程度递增，但可由括号改变，即括号内的 运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。(2)若是重言式或矛盾式，可以只显示 "True forever",或"False forever", 否则显示"Satisfactible”以及变量名序列，与用户交互。若用户对表达式中变元 取定一组值，程序就求出并显示逻辑表达式的值。【测试数据】(1) (A卜A)&(B卜B)(2) (A&A)&C(3) A|B|C|D|E卜A(4)

3、A&B&C&B(5) (A|B)&(AkB)(6) A&B|A&B;O ,0;0,1;1,0;1,1。二、问题分析(7) 个逻辑表达式如果对于其变元的任一种取值均为真，则称为重言式； 反之，如果对于其变元的任一种取值都为假，则称为矛盾式，若对于其变元的任一种取值既有真，又有假，则称其为可满足式。写一个程序通过真值表判别一个 逻辑表达式属于上述哪一类。基本要求如下：(8) 辑表达式从终端输入，长度不超过一行。逻辑运算符包括“广、”&”、“”，分别表示或、与、非，运算优先程度递增，但可有括号改变，即括号内的 运算优先。逻辑变元为大写字母。表达

4、式中任何地方都可以含有多个空格符。2） 若是重言式或矛盾式，可以只显示 “ True Forever” 或 “False Forever", 否则显示运算中每种赋值和与其相对应的表达式的值。2、通过真值表判别逻辑表达式是否为重言式，需解决以下问题：1）对逻辑表达式中空格符的处理。为了方便对逻辑表达式进行扫描判断，应先去掉表达式中的空格符。2）算符的优先级问题在带括号的表达式中，界限符包括左右括号以及表达式起始、结束符“#"。对于一个简单的表达式求值运算规则如下：（1）从左至右依次计算。（2）先取反， 然后相与，后相或。（3）先括号内，后括号外。为统一算法的描述，将运算符和界

5、限符统称为算符。这样，算符集为 , &, |, （,）, #。根据上述3条规则，两个前后相继出现的算符 al, a2间的优先关系 可以归纳如下：（1） 若a1,a2同为“&”或同为“ |”，则算符al的优先级大于a2。（2） “”、“&”、“|”的优先级依次减小。（3） 由于先括号内，后括号外，若al为“|"、“&”、“”，a2为“（”；或 者，al为“（”，而a2为“'、”&”、，”，则al的优先级小于a2。（4） 同理，若ai为“广、“&”、，”，a2为“）”；或者，al为“）”，而a2 为”、“&”、，”，则ai的

6、优先级大于a20（5） 若ai、a2同为“（”，则ai的优先级小于a2；若ai、a2同为“）”， 则ai的优先级大于a20（6） 表达式的起始、结束符“#"的优先级小于其他所有合法出现的算符。（7） 若ai为“（”，a2为“）”；或者，ai、a2同为“#"，则ai、a2优先 级相同。综上所述，将两个相继出现的算符ai、a2的优先关系进行归纳如表i所示表i算符ai和a2间的优先关系a2I&()#1><<<>>重视服务群众的最后一公里"（声音）&>><<>>>>>

7、<>>(<<<<=_)>>>>>#<<<<=我们可以将逻辑表达式的计算类比算术表达式的计算， 通常借助堆栈来实现 按运算符的优先级完成表达式的求值计算。 一个是存放运算符栈，另一个是存放 变量或中间结果栈。（8） 首先初始化算符栈logic和变量栈，并将表达式的起始符" #"压入算符栈logic。（9） 依次读入表达式中的每个字符。若是变量，则为其分配结构node的 size大小的内存，强制转换为bitree类型，并将其压入变量栈variable；若是运算 符，则为其分配结构no

8、de的size大小的内存，强制转换为bitree类型，并与运算 符栈logic的栈顶算符进行优先级比较，并作如下处理：若栈顶算符al的优先级低于刚读入的算符a2,则将a2压入运算符栈logic o若栈顶算符al的优先级高于刚读入的算符a2,则将al出栈，同时将变 量栈variable出栈一次，得到变量 A,再判断栈顶算符al是否为“"，如果al 不是“”，则继续出栈变量栈variable一次，得到变量B,将al作为根结点，B 作为al的左孩子，A作为al的右孩子，并将根结点al压入变量栈variable；如 果栈顶算符al是“”，则将al作为根2点，A作为al的右孩子，al的左孩子则

9、 为空，并将根结点al压入变量栈。 若栈顶算符al优先级与刚读入的算符a2的优先级相同，说明左右括号 相遇，或者是表达式的起始、结束符相遇，只需将栈顶算符（左括号或起始符） 出栈即可；当运算符栈logic空时，算法结束这样就可以将逻辑表达式构造成一棵完整二叉树，根结点是优先级最小的算 符（除了括号和起始结束符，在构造二叉树的过程中已被脱去）。如（A卜A）&（B卜B） 构造成的二叉树如图1所示图1表达式构造的二叉树1）变量的赋值问题若只有1个变量，则有21种情况的赋值；若有2个变量，易知有22种情况的赋值；若有3各变量，则有23种情况的赋值，那么如果有n个变量，就有2n 种情况的赋值。既

10、然要对变量进行赋值，首先要找到逻辑表达式中的变量， 并确 定变量的个数。2）逻辑表达式取值的判断由上述对运算符的优先级的分析可知， 对逻辑表达式的计算，就是中序遍历 由优先级确定的逻辑表达式构成的二叉树。5）重言式的判别可以将给变量的所有赋值的逻辑表达式的逻辑值相加，如果相加结果与2n相等，则为重言式；若相加结果为 0,则为矛盾式；否则为可满足式。本问题的关键和难点在于算符优先级的判断和二叉树的构造。三、数据结构的选择和概要设计1、数据结构的选择通过问题分析可知，需要用到的数据结构有堆栈和二叉树。1）对于堆栈选用顺序栈结构来进行存放算符或变量，存放的都是二叉树的 结点。设有两个堆栈，一个是存放

11、运算符栈，另一个是存放变量或中间结果栈。2）对于二叉树，选用二叉树的链接存储结构，其结点存放得都是表达式中的元素。将表达式构造成一棵二叉树。2、概要设计从整体上可以分为三个模块:第一个模块：属于堆栈和二叉树结点类型的定义/识别表达式使用的堆栈定义，它存放的都是/栈中的元素都是树的结点结构/栈底指针/栈顶指针/栈容量/根据表达式建立的二叉树的结点定义typedef struct stack树的结构bitree *base;bitree *top;int stacksize;seqstack;typedef struct nodechar data;struct node *lchild;stru

12、ct node *rchild;BiTNode,*bitree;第二个模块：主要函数及其功能。堆栈的创建void creatstack(sqstack &st)；初始化栈void setstack(seqstack &st)；进栈void push(sqstack &st,bitree e);出栈void pop(sqstack &st,bitree &e)；将逻辑表达式中的元素转换为二叉树结点的形式，使栈中存储的都是二叉树的结点。void creattree(char s口,bitree &tree)；通过优先级将逻辑表达式构造成一颗完整的二叉

13、树void create(bitree &zigen,bitree l,bitree r)；页脚内容5重视服务群众的最后一公里"(声音)对逻辑表达式求值int valuetree(bitree tree)；生成变量的各种取值组合void creatzuhe(int n,int m,char a)；逻辑运算符的优先级判别，返回值为“<”、">"、“=”char youxianji(char m,char n)；第四个模块为于用户的交互void user();流程图：图2程序流程图四、算法思想1、穷举法思想通过真值表来判断重言式，需要一一给变量赋值

14、，共有 2An中情况(n表示 变量的个数)，这里用到穷举的思想。2、递归与分治思想每给变量赋一组值，通过递归中序遍历二叉树求值， 这里用到了递归与分治思想3、运算符的优先级判断思想(见问题分析算符的优先级问题分析第5页)五、详细设计和主要编码段首先将用户输入的逻辑表达式存到char *str当中，然后去除逻辑表达式中的空格符。for(;*pstr!=NULL;pstr+,n+) if(strn!=' ') strii+=*pstr;/去除表达式中的空格此时stri当中存储的就是没有空格符的逻辑表达式。通过问题分析，需找到 表达式中的变量，并确定变量的个数。下面的代码就是实现此功

15、能。for(int k=0;k< strlen(stri);k+) if(strik>=65&&strik<=90)/ 找到变量 int mark=0;/标记变量for(int j=0;j<m;j+)if(blj=strik)/将找到的变量与bl口中已找到过的变量比较，若相等则将变量标记置为1,表示找到的变量在前面已出现过mark=1;break;if(mark=0)若标记为0,表示找到的变量没有重复，并将其记 录到bl口中，变量个数m加1。blm=strk;m+;/m是变量个数页脚内容7重视服务群众的最后一公里"（声音）此时bl口当中存储的就

16、是变量，m就是变量个数，那么变量赋值的情况就有2m种。卜面对生成变量的各种取值组合的算法进行分析和说明。int zuhe30用来存储变量的取值组合，为了方便说明，采用两个变量进行算法叙述AB第n次数000011102113表2变量赋值实例从表2可以发现给变量赋值的次数n与变量的取值组合成的二进制数相等， 能得到一个规律：变量的取值组合 zuhe二进制数（从低位到高位）的第i位数 取值等于（n>>i）%2用一下代码可以实现第n次对变量的赋值组合int lzp=m;for(int i=0;i<m;i+)zuhebllzp-65=(n>>i)%2;lzp-；下面说明优先

17、级的判断。char bijiao7口用来存放算符间的优先关系表中的 数据。int i,j;bijiao77=','|','&','','(',')','#',/二维数组比较优先级先后'|','>','<','<','<','>','>','&','>','>','

18、<','<','>','>','','>','>','>','<','>','>','(','<','<','<','<','=','',')','>','>','&g

19、t;',' ','>','>','#'<'<'<'< ','='for(i=0;i<7;i+)if(bijiao0i=a2)找至U a2运算符的列号break;for(j=0;j<7;j+)/找到al运算符的行号if(bijiao皿0=a1) break;return bijiaoji;/返回优先级的符号：>、<、=下面说明将表达式构成二叉树的过程。s=stri是逻辑表达式的首地址。while(*s!=NULL) 循

20、环条件，为空则扫描结束if(int(*s)>=65&&int(*s)<=90)/读取的是变量variables=(bitree)malloc(sizeof(node);/分配结构node的size大小的内存，强制转换为bitree类型 variables->data=*s;push(variable,variables);/入变量栈else if(int(*s)>90|int(*s)<65)/读取的逻辑运算符 gettop(logic,e);/取运算符栈的栈顶元素进行优先级比较switch(youxianji(*s,e->data) case

21、 '<':/栈顶的运算符优先级低，逻辑运算符进栈logics=(bitree)malloc(sizeof(node);/分配2构node的size大小的内存，强制转换为bitree类型 logics->data=*s;push(logic,logics);break;case '=':pop(logic,kuohao);/括号并接受下一个字符页脚内容9重视服务群众的最后一公里"(声音)break;case '>':/栈顶的运算符优先级高，变量出栈运算pop(logic,g)；/弹出逻辑运算符gpop(variable,

22、a); /弹出变量 ab=NULL;/''只有右子树if(g->data!='')pop(variable,b); / 出栈变量 bcreate(g,b,a);/将变量b作为g的左子树，a作为g的右子树，若a是变量，将其左、右孩子置空，若 b是变量，将其左、右孩子置空push(variable,g);将临时的根g作为新的变量压入变量栈中gettop(logic,e);/取变量栈栈顶算符eif(*s!='#'&&*s!=')'&&youxianji(*s,e->data)!='&g

23、t;')/如果读入算符*s不是结束符也不是右括号，并且栈顶算符优先级小于读入算符优先级将读 入的算符入栈logics=(bitree)malloc(sizeof(node);/ 分配结构 node 的size大小的内存，强制转换为bitree类型logics->data=*s;push(logic,logics);/逻辑运算符入栈else s=s-1;偌栈顶算符优先级大于读入算符优先级或读入算 符为“#”或“)”break;s+;tree=g;下面说明对逻辑表达式的求值过程。中序遍历二叉树int valuetree(bitree tree)/根据变量的取值组合并利用逻辑表达式的性

24、质对树进行求值if(!tree) return 0;遇到空的结点else if(tree->data!=T&&tree->data!='&'&&tree->data!='')找到的是变量return zuheint(tree->data)-65;/ 返回对应变量赋予的值(0或1)else if(int(tree->data)<65|int(tree->data)>90)找到的是运算符switch(tree->data)case '|':return(va

25、luetree(tree->lchild)|valuetree(tree->rchild); / 递归调用 break;case '&':return(valuetree(tree->lchild)&&valuetree(tree->rchild); 递归调 用break;case ''：return(!valuetree(tree->rchild);递归调用break;default: return 0;else return 0;最后说明判断逻辑表达式或为重言式，或为矛盾式或为可满足式。每给变量 一组值，

26、调用一次int valuetree(bitree tree)函数求其逻辑值，需要给变量2n组值，则需求其逻辑值2n次,把每次求得的逻辑值相加，得到数字SUM,若SUM=2n, 则逻辑表达式为重言式；若 SUM=0,则逻辑表达式为矛盾式；若0<SUM<2n,则逻辑表达式为可满足式。若表达式为可满足式，则输出运算中每种赋值和与其相 对应的表达式的值。页脚内容11重视服务群众的最后一公里"（声音）六、上机调试情况记录出现的问题及解决方法问题：a）测试题目给定的数据 A&B|A&B,发现其结果不正确，原因是没有正确的解决优先级，建树的过程中，运算符入栈时，如果检测

27、到 的表达式中的算符优先级低于栈顶的优先级，则应出栈运算符，在出栈运算符后，如果检测到的表达式中的算符（并且算符不是结束符#也不是）'）的优先级依旧低于栈顶算符，应该继续算符出栈，而不是算符入栈。解决方法：将算符入栈条件if（*s!='#'&&*s!='）'）改为if（*s!='#'&&*s!='）'&&youxianji（*s,e->data）!='>'）b）测试数据时如果逻辑表达式的变量不是递增按顺序输入（如： A&B&F&am

28、p;G）,结果会出错。原因是在给变量组合赋值时，赋值组合数组的小标是递增顺序的，而在递归调用求值函数时用到的变量组合值数组的下标却是与变量的ACS编码有关的，两者对不上。解决方法：在生成变量组合数时，将zuhei=（n>>i）%2改为 zuhealzp-65=（n>>i）%2;七、测试用例、结果及其算法性能分析（一）、初始界面页脚内容17（二）、测试用例及结果（1） （A卜A）&（BkB）（重言式）M1018-王芳VDebugt重言式的判羯.ezc你好！欢迎使用重言式判别软件!会请输入逻辑表达式的表达式墨例如“：珊C*心b 州$?请选择你要的操作& OO

29、 OO <X>OOOO计襄机熨举造户自定义!合变量赋值0退出新开始情选择你要的操作二1辑表达式:“ ：Mfi）8c<B：B> OO OO 名 OO OOrue forevep否继续？代继续,它退出）（A&A）&C （矛盾式）贰F:11404011018-王芳VDebugt重言式的判羯."C你好！欢迎使用重言式判别软件!请输入逻楫表达式的表达式，例如f SBftO 8?请选择你要的操作8 OO OO <x>00001计襄祖史举浩2甚户自定义与变量赋值3重新井始0退出晴选择你要的操作二1:辑表达式XH&F'&C。

30、OOOOOOalee f ope uer否继续？日继续,in它退出）A|B|C|D|E卜A （重言式）d F:1140401101”王芳UEbugt更言式的判利."广|你好！欢迎使用重言式判别软件!展仝请输入逻辑表达式的表达中例如+wc） MIBICISIEI请选择你要的操作 淡.<>OOOOOO 1计算机穷举昔<X> 2用芦自定义给变量赋值新开始OO 0退出请选择你要的操作二1 道辑表这式二。C；D；E；ITfur foreverOO OO令OOOO（4） A&B&C&B （矛盾式）M "F:1104011 (HH-王芳VD

31、ebugt重言式的武制."e你好！欢迎使用重言式判别软件!请输入逻辑表达式的表达式:例如<“IBM> OO OO 0 <X> O<> OOOO00计算机穷举法 国户自定义给变量赋值 重新笄始退出请选择你要的操作二1逻辑表达式：A &B&C8rBFalse fopevep是否继续？代继续，其它退出）.00（5） (A|B)&(A卜B)(可满足式)-01x1yrir请输入逻辑表达式的表达式;例如F ；B»C） <A !"B>O请选择你要的操作OB逻辑表达式的值1是否继续？日继续,:它退出）atis

32、f-acx iblc1001(6) A&B|A&B;O ,0;0,1;1,0;1,1。(可满足式)莉*F： 140401 1（118-王芳。仲昭工重言式的判别.czg你好！欢迎使用重言式判别软件!k>2H1甘基亚变举造- <>2 2总芦自定义塔变量赋值 3重前开始，.，0 F 逋选择你要的操作一 逻辑表达式二E ；B&* ；R逻辑表达式的真值表重视服务群众的最后一公里"(声音)页脚内容19c' "F： 140401 1(118-王芳。仲昭工重言式的判别.czg-01x1你好！欢迎使用重言式判别软件!出If请输入逻辑表达式的表

33、达式;例如F ；B»C) aerBE 故eR>OOOO 请选择你要的操作OKX>1计算机夯举造:二!用户自定义电变量赋值K>O 2 3重新开始OO 0退出通选择你要的操作一 道辑表达式"WB E&B逻辑表达式的真值表B逻辑表达式的值1是否继续？日继续,:它退出)atisf-acx iblc1001通过测试验证结果都正确，实现了题目的要求。(三)、算法性能分析1、算法的时间性能分析用穷举法列真值表有2An (n为变量个数)种情况，为每一种情况的所有变 量赋值的次数为 n,则为所有情况的变量赋值次数为n*2An次，即在函数voidcreatzuhe(i

34、nt n,int m,char a)中的语句需执行n*2An次,是整个算法当中频度最 大的语句，由于算法的时间复杂度考虑的只是对于问题规模n的增长率，所以该算法的时间复杂度为T(n)=O(n*2An)。2、算法的空间性能分析本算法的空间复杂度较低，需要一个zuhe30的数组来存放变量的取值， 个大小为M的数组存放逻辑表达式，一个 M的二叉树链接存放逻辑表达式构成重视服务群众的最后一公里"（声音）的树结点。两个堆栈长度不超过 M,所以空间复杂度为O （M）。（四）、经验和体会初拿到本问题，就觉得与学过的带括号的算术表达式计算问题相似。其最关 键的是算符优先级的判断，可以将它类比算术表达

35、式列出同数据结构与算法课本 上表4-1类似的算符的优先关系表表1。通过查表来判断算符的优先级就变得简 易了。观察逻辑表达式可以发现，对逻辑表达式的计算类似于对二叉树的中序遍 历，可以将逻辑表达式通过优先级将其构造成一棵二叉树。当然最终实现过程中有很多细节问题需要注意，通过一步步测试、调试程序找到问题，并改善，知道 最终解决问题。八、用户使用说明1、运行程序进入显示文本方式的用户界面；2、根据提示输入要判别的逻辑表达式（表达式中可以有空格）3、输入表达式后出现菜单选项，用户可以选择程序自动穷举赋值法和用户 赋值法进行判别；4、在显示相应结果后，根据提示信息在进行下一步。九、参考文献1王昆仑，李红

36、.数据结构与算法.北京：中国铁道出版社，2006年5月。2严蔚敏，吴伟明.数据结构.北京：清华大学出版社，2007年5月。3李春葆.数据结构教程.北京：清华大学出版社，2003年5月。4蹇强，罗宇.数据结构.北京：邮电大学出版社，2004年5月。5金远平.数据结构（C+苗述.北京：清华大学出版社 2005年5月。十、附录（完整代码）#include "stdlib.h" / 调用 stdlib.h 里面的函数 '#include "stdio.h"#include "iostream.h"#include "stri

37、ng.h"/包含字符串处理函数的头文件#include "math.h"/调用数学函数库#include "iomanip.h"/ 是 I/O 流控制头文件/变量的取值组合数组定义/变量个数/根据表达式建立的二叉树的结点定义#define maxsize 100int zuhemaxsize;int N;typedef struct nodechar data;struct node *lchild;struct node *rchild;BiTNode,*bitree;typedef struct stack构/识别表达式使用的堆栈定义，它存

38、放的都是树的结页脚内容33bitree *base;bitree *top;int stacksize;/栈中的元素都是树的结点结构/栈底指针/栈顶指针/栈容量seqstack;void creatzuhe(int n,int m,char a口) 生成变量的组合数int lzp=m-1;for(int i=0;i<m;i+)zuhealzp-65=(n>>i)%2;lzp-;void create(bitree &f,bitree l,bitree r) /自底向上地根据运算符地优先级来建 立分子树函数(f->lchild=l;分树的链接f->rchil

39、d=r;/分树的链接if(l&&r)(if(int(l->data)>=65&&int(l->data)<=90)左子树(l->lchild=NULL;l->rchild=NULL;if(int(r->data)>=65&&int(r->data)<=90) 右子树(r->lchild=NULL;r->rchild=NULL;char youxianji(char m,char n)/逻辑运算符的优先级判别(int i,j;char bijiao77='',T

40、,&,'','(',')','#',/二维数组比较优先级先后'|','>','<','<','<','>','>','&','>','>','<','<','>','>','','>',

41、'>','>','<','>','>','(','<','<','<','<','=',' ',')','>','>','>',' ','>','>','#'<'<'&

42、lt;'< ','='for(i=0;i<7;i+)if(bijiao0i=m) break;for(j=0;j<7;j+)if(bijiao皿0=n) break;return bijiao皿i;void setstack(seqstack &st)/找到m运算符的列号/找到n运算符的行号/返回优先级的符号：,、=/初始化栈st.base=(bitree *)malloc(maxsize*sizeof(node);st.top=st.base;st.stacksize=maxsize;void push(seqstack &s

43、t,bitree e)if(st.top-st.base<st.stacksize)*st.top=e;st.top+;else cout<<"ERROR!"<<endl;/栈容量/入栈/符合条件入栈/不符合输出ERROR!/出栈void pop(seqstack &st,bitree &e)if(st.top=st.base) cout<<"ERROR!"<<endl; 不符合条件输出 ERROR!st.top-;/符合条件e=*st.top;void gettop(seqstack

44、 &st,bitree &e) / 取栈顶元素if(st.top=st.base) cout<<"ERROR!"<<endl不符合条件输出 ERROR!e=*(st.top-1);/符合取栈顶元素/变量栈/逻辑运算符栈/变量栈初始化/逻辑运算符栈初始化void creattree(char s口,bitree &tree) /根据逻辑表达式将数据存入二叉树中， 定义两个栈seqstack variable;seqstack logic;setstack(variable);logic1,variables,logics,e,a

45、,b,g,kuohao;/定义栈中的元素,g 为最后setstack(logic);bitree的二叉树的根logic1=(bitree)malloc(sizeof(node);/ 分配结构 node 的 size 大小的内存, 强制转换为bitree类型logic1->data='#'/将逻辑运算符栈的栈底元素设为#push(logic,logic1);/将逻辑运算符栈入栈.while(*s!=NULL)if(int(*s)>=65&&int(*s)<=90)/读取的是变量variables=(bitree)malloc(sizeof(nod

46、e);/分配结构node的size大小的内存，强制转换为bitree类型variables->data=*s;push(variable,variables);/入变量栈else if(int(*s)>90|int(*s)<65)/读取的逻辑运算符 gettop(logic,e)；/取运算符栈的栈顶元素进行优先级比较switch(youxianji(*s,e->data)case '<':/腰顶的运算符优先级低，逻辑运算符进栈logics=(bitree)malloc(sizeof(node);/ 强制转换为 bitree 类型logics->

47、;data=*s;push(logic,logics);break;case '=':pop(logic,kuohao);/括号并接受下一个字符break;case '>':/栈顶的运算符优先级高，变量出栈运算pop(logic,g);/弹出逻辑运算符pop(variable,a); /弹出变量b=NULL;/''只有右子树if(g->data!='')pop(variable,b);create(g,b,a);建树的函数调用push(variable,g);将临时的根作为新的变量压入变量栈中gettop(logic,

48、e);if(*s!='#'&&*s!=')'&&youxianji(*s,e->data)!='>')logics=(bitree)malloc(sizeof(node);/ 强制转换为 bitree 类型logics->data=*s;push(logic,logics)；/逻辑运算符入栈else s=s-1;break;s+;tree=g;int valuetree(bitree tree) /根据变量的取值组合并利用逻辑表达式的性质对 树进行求值if(!tree) return 0;遇到空的

49、结点else if(tree->data!=T&&tree->data!='&'&&tree->data!='')找到的是变return zuheint(tree->data)-65;/ 返回值else if(int(tree->data)<65|int(tree->data)>90)找到的是运算符switch(tree->data)case '|':return(valuetree(tree->lchild)|valuetree(tree->

50、;rchild);break;case '&':return(valuetree(tree->lchild)&&valuetree(tree->rchild); break;case ''：return(!valuetree(tree->rchild);break;default: return 0;else return 0;void user(int m,char b口)/用户输入变量的一组取值情况int i;cout<<”请依次输入你的变量取值(0或1)"<<endl;for(i=

51、0;i<m;i+)cout<<bi<<" "/转化为char类型输出cout<<endl;for(i=0;i<m;i+)cin>>zuhebi-65;)void print()(cout<<" "<<endl;cout<<""<<endl;cout<<"你好！"<<endl;cout<<"欢迎使用重言式判别软件！"<<endl; cout&l

52、t;<""<<endl;cout<<" "<<endl;)void meun()/菜单函数(system("cls");/清屏函数print();char strmaxsize,strimaxsize,*pstr,q,bl20;int j,i=0,choose=1,sum,n=0,m=0;bitree Tree;int SUM=0; /用于累加变量的每种组合的逻辑表达式的结果；cout<<" 请输入逻辑表达式的表达式：例如(A|B&C) "<<

53、;endl;scanf("%An",str);/读取包含多个空格的逻辑表达式pstr=str;for(;*pstr!=NULL;pstr+,n+)逻辑表达式的正确读取，if(strn>=97&&strn<=122) strn=strn-32;/ 将小写转换成大写if(strn!=' ') strii+=*pstr;/去除表达式中的空格)int nu=strlen(stri);for(int k=0;k<nu;k+)if(strik>=65&&strik<=90)int mark=0;/标记变量fo

54、r(int j=0;j<m;j+)if(blj=strik)mark=1;break;)if(mark=0)blm=strk;m+;/m是变量个数)sum=int(pow(2,m);strii='#' 最后一字符后加入#',与运算符栈的栈底元素#'对应strii+1='0'/结束标志'0'cout<<" 请选择你要的操作"<<endl;cout<<" "<<endl;cout<<" "<<end

55、l;cout<<" "<<endl;cout<<" "<<endl;cout<<" OO 1计算机穷举法"<<endl;cout<<" OO 2用户自定义给变量赋值"<<endl;cout<<" 3重新开始"<<endl;cout<<" 0 退出"<<endl;cout<<"请选择你要的操作："/提示信

56、息cin>>choose;while(choose!=1&&choose!=2&&choose!=3&&choose!=0)(cout<<"您输入的有误，请您重新输入:"/提示信息cin>>choose;switch(choose)(case 1:/判别重言式的类别creattree(stri,Tree); /建立重言式的二叉树for(j=0;j<sum;j+)(creatzuhe(j,m,bl);/产生变量取值组合SUM+=valuetree(Tree); /SUM 累力口)strii='0'/加入结