《《数据结构c语言》重言式判定参考了别人的代码.doc》由会员分享，可在线阅读，更多相关《《数据结构c语言》重言式判定参考了别人的代码.doc（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、重言式判定-参考了别人的代码。 2011-05-11 17:19 122人阅读 评论(0) 收藏 举报 【重言式判别】 问题描述 一个逻辑表达式如果对于其变元的任一种取值均为真，则成为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式，然而，更多的情况下，既非重言式，也非矛盾式。试写一个程序，通过真值表判别一个逻辑表达式属于上述哪一类。， 基本要求 （1 ） 逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括 “ ” 、 “ ” 和 “ ” ，分别表示或、与和非，运算优先程度递增，但可有括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。 （2
2、）若是重言式或矛盾式，可以只显示 “ True Forever ” 或 “ False Forever ” ，否则显示 “ Satisfactible ” 以及变量名序列，与用户交互。若用户对表达式变元取定一组值，程序就求出并显示逻辑表达式的值。 测试数据 （1 ）（A A ）（B|B ） （2 ）（A& A ）C （3 ）A|B|C|D|E A 实现提示 (1) 识别逻辑表达式的符号形式并建立二叉树可以有两种策略：自底向上的算符优先法和自顶向下分割，先序遍历建立二叉树的方法。 (2) 可设表达式中逻辑变量数不超过20 。真值的产生可以通过在一维数组上维护一个 “ 软计数器 ” 实现，用递归算
3、法实现更简单。 cpp view plaincopyprint?1. #include 2. usingnamespacestd;3. structArr4. 5. charletter;6. intweight;7. ;8. classCys9. 10. public:11. Cys();12. voidGetTautology();/输入表达式 13. int_CreateT(int,int);/虚拟创建二叉树 14. intFindMin(int,int);/找到weight最小的 15. intcount();/计算可满足式的值 16. void_recursion(Arr*_arr,
4、inti);/递归，穷举 17. voidrecursion();/使用接口函数 18. voidPrint();/输出结果 19. Cys();/析构释放空间 20. private:21. intnum;22. Arr*array;23. Arr_arr20;/存放字母 24. int_arrNum;25. inttrueforever;26. intfalseforever;27. ;28. 29. Cys:Cys()30. 31. trueforever=0;32. falseforever=0;33. array=newArr20;34. for(inti=0;i20;i+)35.
5、arrayi.weight-1;36. arrayi.letter=0;37. 38. _arrNum=0;39. num=0;40. 41. voidCys:GetTautology()42. 43. inthas27=0;44. intweight=0;45. charch;46. cout请输入一个逻辑表达式,以#结束ch&ch!=#)48. 49. 50. 51. if(ch=)52. continue;53. 54. switch(ch)55. 56. case(:57. weight+=4;58. break;59. case):60. weight-=4;61. break;62
6、. case&:63. arraynum.letter=ch;64. arraynum+.weight=weight+2;65. break;66. case|:67. arraynum.letter=ch;68. arraynum+.weight=weight+1;69. break;70. case:71. arraynum.letter=ch;72. arraynum+.weight=weight+3;73. break;74. default:75. arraynum.letter=ch;76. if(!hasarraynum.letter-A)77. _arr_arrNum+.let
7、ter=arraynum.letter;78. hasarraynum.letter-A=1;79. 80. arraynum+.weight=0;81. break;82. 83. 84. 85. 86. intCys:FindMin(intlow,inthigh)87. 88. intmin=low;89. while(!arraymin.weight)90. min+;91. 92. if(minhigh)93. for(inti=min;ihigh+1;i+)94. if(arrayi.weight&arrayi.weightarraymin.weight)95. min=i;96.
8、returnmin;97. 98. else99. return0;100. 101. 102. 103. intCys:_CreateT(intlow,inthigh)104. 105. intMin=0;106. /coutcreatehigh)108. return1;109. elseif(low=high)110. 111. /coutletterarraylow.letterendl; 112. inti;113. for(i=0;_arri.letter!=arraylow.letter;i+);/从array中寻找与_arr中相同的字母 114. return_arri.wei
9、ght;/返回它的weight（1或0） 115. 116. else117. Min=FindMin(low,high);118. /coutarrayMin.letter:arrayMin.letter; 119. switch(arrayMin.letter)120. case&:return(_CreateT(low,Min-1)&_CreateT(Min+1,high);121. break;122. case|:return(_CreateT(low,Min-1)|_CreateT(Min+1,high);123. break;124. case:return(!_CreateT(
10、Min+1,high);125. break;126. 127. 128. 129. intCys:count()/计算可满足式的值 130. 131. inti=0;132. cout请给字母赋值endl;133. while(_arrNum-)134. cout_arri+.weight;136. 137. if(_CreateT(0,num-1)138. trueforever+;139. else140. falseforever+;141. 142. 143. 144. voidCys:_recursion(Arr_arr,inti)/递归调用 145. 146. if(i_arrN
11、um)147. _arri.weight=0;148. /cout0endl; 149. _recursion(_arr,i+1);150. _arri.weight=1;151. /cout1endl; 152. _recursion(_arr,i+1);153. 154. else155. if(!trueforever|!falseforever)156. 157. switch(_CreateT(0,num-1)158. 159. case1:160. /couttrueforever+;endl; 161. trueforever+;162. break;163. case0:164
12、. /coutfalseforever+;endl; 165. falseforever+;166. break;167. default:168. break;169. 170. 171. 172. 173. voidCys:Print()174. if(trueforever&falseforever)/如果真假同时存在就判断它为satisfactible. 175. coutsatisfactible.endl;176. elseif(!trueforever)177. coutfalseforever.endl;178. else179. couttrueforever.endl;18
13、0. 181. 182. voidCys:recursion()183. 184. _recursion(_arr,0);185. 186. 187. Cys:Cys()188. 189. deletearray;190. 191. 192. intmain()193. 194. cout-重言式判别-endl;195. Cyscys;196. charc;197. cys.GetTautology();198. cout计算机穷举请按tor用户赋值请按nc;200. if(c=t)201. cys.recursion();/穷举 202. else203. cys.count();/赋值 204. cys.Print();205. system(pause);206. return0;207.