重言式判别课程设计报告

《重言式判别课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.-XX学院计算机科学与技术系课程设计报告2021～2021学年第1学期课程数据构造与算法课程设计题目名称重言式的判别学生XX王芳学号1404011018专业班级计算机科学与技术14级1班指导教师李红何立新-.word.zl.-2021年9月一、题目【问题描述】一个逻辑表达式如果对于其变元的任一种取值都为真，那么称为重言式；反之，如果对于其变元的任一种取值都为假，那么称为矛盾式；然而，更多的情况下，既非重言式，也非矛盾式。试写一个程序，通过真值表判别一个逻辑表达式属于上述哪一类。【根本要求】(1)逻辑表达式从终端输入，长度

2、不超过一行。逻辑运算符包括""，"&"和"~"，分别表示或、与和非，运算优先程度递增，但可由括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。(2)假设是重言式或矛盾式，可以只显示"Trueforever"，或"Falseforever"，否那么显示"Satisfactible"以及变量名序列，与用户交互。假设用户对表达式中变元取定一组值，程序就求出并显示逻辑表达式的值。【测试数据】(1)(A~A)&(B~B)(2)(A&~A)&C(3)ABCDE~A-.word.zl.-(4)A&B

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

4、。表达式中任何地方都可以含有多个空格符。2)假设是重言式或矛盾式，可以只显示“TrueForever〞或“FalseForever〞，否那么显示运算中每种赋值和与其相对应的表达式的值。2、通过真值表判别逻辑表达式是否为重言式，需解决以下问题：1)对逻辑表达式中空格符的处理。为了方便对逻辑表达式进展扫描判断，应先去掉表达式中的空格符。2)算符的优先级问题在带括号的表达式中，界限符包括左右括号以及表达式起始、完毕符“-.word.zl.-#〞。对于一个简单的表达式求值运算规那么如下：〔1〕从左至右依次计算。〔2〕先取反，然后相

5、与，后相或。〔3〕先括号内，后括号外。为统一算法的描述，将运算符和界限符统称为算符。这样，算符集为{~，&，，〔，〕，#}。根据上述3条规那么，两个前后相继出现的算符a1，a2间的优先关系可以归纳如下：（1）假设a1,a2同为“&〞或同为“〞，那么算符a1的优先级大于a2。（2）“~〞、“&〞、“〞的优先级依次减小。（3）由于先括号内，后括号外，假设a1为“〞、“&〞、“~〞，a2为“〔〞；或者，a1为“〔〞，而a2为“〞、“&〞、“~〞，那么a1的优先级小于a2。（4）同理，假设a1为“〞、“&〞、“~〞，a2为“〕〞；

6、或者，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间的优先关系-.word.zl.-a1a2&~()#><<<>>&>><<>>~>>><>>(

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

8、e类型，并与运算符栈logic的栈顶算符进展优先级比较，并作如下处理：①-.word.zl.-假设栈顶算符a1的优先级低于刚读入的算符a2，那么将a2压入运算符栈logic。①假设栈顶算符a1的优先级高于刚读入的算符a2，那么将a1出栈，同时将变量栈variable出栈一次，得到变量A，再判断栈顶算符a