资源描述:
《重言式判别-课程设计报告》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、..学院计算机科学与技术系课程设计报告2021~2021学年第1学期课程数据构造与算法课程设计题目名称重言式的判别学生王芳学号1404011018专业班级计算机科学与技术14级1班指导教师红何立新..word.zl...2021年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..word.zl...(4)A&B&C&~B(5)(A
11、B)&(A
12、~B)(6)A&~B
13、~A&B;O
14、,0;0,1;1,0;1,1。二、问题分析1、一个逻辑表达式如果对于其变元的任一种取值均为真,那么称为重言式;反之,如果对于其变元的任一种取值都为假,那么称为矛盾式,假设对于其变元的任一种取值既有真,又有假,那么称其为可满足式。写一个程序通过真值表判别一个逻辑表达式属于上述哪一类。根本要求如下:1)逻辑表达式从终端输入,长度不超过一行。逻辑运算符包括“
15、〞、“&〞、“~〞,分别表示或、与、非,运算优先程度递增,但可有括号改变,即括号的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。2)假设是重言式或矛盾式,可以只显示“TrueForever
16、〞或“FalseForever〞,否那么显示运算中每种赋值和与其相对应的表达式的值。2、通过真值表判别逻辑表达式是否为重言式,需解决以下问题:1)对逻辑表达式中空格符的处理。为了方便对逻辑表达式进展扫描判断,应先去掉表达式中的空格符。2)算符的优先级问题在带括号的表达式中,界限符包括左右括号以及表达式起始、完毕符“#〞。对于一个简单的表达式求值运算规那么如下:〔1〕从左至右依次计算。〔2〕..word.zl...先取反,然后相与,后相或。〔3〕先括号,后括号外。为统一算法的描述,将运算符和界限符统称为算符。这样,算符集为{~,&,
17、,〔,〕,#}。根据上述3条
18、规那么,两个前后相继出现的算符a1,a2间的优先关系可以归纳如下:(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同为“〕〞,那么
25、a1的优先级大于a2。(6)表达式的起始、完毕符“#〞的优先级小于其他所有合法出现的算符。(7)假设a1为“〔〞,a2为“〕〞;或者,a1、a2同为“#〞,那么a1、a2优先级一样。综上所述,将两个相继出现的算符a1、a2的优先关系进展归纳如表1所示。表1算符a1和a2间的优先关系..word.zl...a1a2
26、&~()#
27、><<<>>&>><<>>~>>><>>(<<<<=___)>>>___>>#<<<<___=我们可以将逻辑表达式的计算类比算术表达式的计算,通常借助堆栈来实现按运算符的优先级完成表达式的求值计算。一个是存放运算符栈,另一个是存放变量或中
28、间结果栈。(1)首先初始化算符栈logic和变量栈,并将表达式的起始符“#〞压入算符栈logic。(2)依次读入表达式中的每个字符。假设是变量,那么为其分配构造node的size大小的存,强制转换为bitree类型,并将其压入变量栈variable;假设是运算符,那么为其分配构造node的size大小的存,强制转换为bitree类型,并与运算符栈logic的栈顶算符进展优先级比拟,并作如下处理:①..word.zl...假设栈顶算符a1的优先级低于刚读入的算符a2,那么将a2压入运算符栈logic。①假设栈顶算符a1的优先级高于刚读入的算符a2,那么将a1出栈
29、,同时将变量栈variable出栈一次