资源描述：
《数据结构与算法课程设计报告重言式判别本科论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、合肥学院计算机科学与技术系课程设计报告2016～2017学年第1学期课程数据结构与算法课程设计题目名称重言式的判别学生姓名学号专业班级计算机科学与技术14级1班指导教师2016年9月一、题目【问题描述】一个逻辑表达式如果对于其变元的任一种取值都为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式；然而，更多的情况下，既非重言式，也非矛盾式。试写一个程序，通过真值表判别一个逻辑表达式属于上述哪一类。【基本要求】(1)逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括"
2、"，"&"和"~"，分别表示或、与和非，运算优先程度
3、递增，但可由括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。(2)若是重言式或矛盾式，可以只显示"Trueforever"，或"Falseforever"，否则显示"Satisfactible"以及变量名序列，与用户交互。若用户对表达式中变元取定一组值，程序就求出并显示逻辑表达式的值。【测试数据】(1)(A
4、~A)&(B
5、~B)(2)(A&~A)&C(3)A
6、B
7、C
8、D
9、E
10、~A(4)A&B&C&~B(5)(A
11、B)&(A
12、~B)(6)A&~B
13、~A&B;O,0;0,1;1,0;1,1。二、问题分析1
14、、一个逻辑表达式如果对于其变元的任一种取值均为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式，若对于其变元的任一种取值既有真，又有假，则称其为可满足式。写一个程序通过真值表判别一个逻辑表达式属于上述哪一类。基本要求如下：1)逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括“
15、”、“&”、“~”，分别表示或、与、非，运算优先程度递增，但可有括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。2)若是重言式或矛盾式，可以只显示“TrueForever”或“FalseForever”
16、，否则显示运算中每种赋值和与其相对应的表达式的值。2、通过真值表判别逻辑表达式是否为重言式，需解决以下问题：1)对逻辑表达式中空格符的处理。为了方便对逻辑表达式进行扫描判断，应先去掉表达式中的空格符。2)算符的优先级问题在带括号的表达式中，界限符包括左右括号以及表达式起始、结束符“#”。对于一个简单的表达式求值运算规则如下：（1）从左至右依次计算。（2）先取反，然后相与，后相或。（3）先括号内，后括号外。为统一算法的描述，将运算符和界限符统称为算符。这样，算符集为{~，&，
17、，（，），#}。根据上述3条规则，两个前后相继出现的算符a1，a2
18、间的优先关系可以归纳如下：（1）若a1,a2同为“&”或同为“
19、”，则算符a1的优先级大于a2。（2）“~”、“&”、“
20、”的优先级依次减小。（3）由于先括号内，后括号外，若a1为“
21、”、“&”、“~”，a2为“（”；或者，a1为“（”，而a2为“
22、”、“&”、“~”，则a1的优先级小于a2。（4）同理，若a1为“
23、”、“&”、“~”，a2为“）”；或者，a1为“）”，而a2为“
24、”、“&”、“~”，则a1的优先级大于a2。（5）若a1、a2同为“（”，则a1的优先级小于a2；若a1、a2同为“）”，则a1的优先级大于a2。（6）表达式的起
25、始、结束符“#”的优先级小于其他所有合法出现的算符。（7）若a1为“（”，a2为“）”；或者，a1、a2同为“#”，则a1、a2优先级相同。综上所述，将两个相继出现的算符a1、a2的优先关系进行归纳如表1所示。表1算符a1和a2间的优先关系a1a2
26、&~()#
27、><<<>>&>><<>>~>>><>>(<<<<=___)>>>___>>#<<<<___=我们可以将逻辑表达式的计算类比算术表达式的计算，通常借助堆栈来实现按运算符的优先级完成表达式的求值计算。一个是存放运算符栈，另一个是存放变量或中间结果栈。（1）首先初始化算符栈logic和变
28、量栈，并将表达式的起始符“#”压入算符栈logic。（2）依次读入表达式中的每个字符。若是变量，则为其分配结构node的size大小的内存,强制转换为bitree类型，并将其压入变量栈variable；若是运算符，则为其分配结构node的size大小的内存,强制转换为bitree类型，并与运算符栈logic的栈顶算符进行优先级比较，并作如下处理：①若栈顶算符a1的优先级低于刚读入的算符a2，则将a2压入运算符栈logic。②若栈顶算符a1的优先级高于刚读入的算符a2，则将a1出栈，同时将变量栈variable出栈一次，得到变量A，再判断栈顶
29、算符a1是否为“~”，如果a1不是“~”，则继续出栈变量栈variable一次，得到变量B，将a1作为根结点，B作为a1的左孩子，A作为a1的右孩子，并将根结点a1压入变量栈va
