《《數(shù)據(jù)結(jié)構(gòu)c語言》重言式判定參考了別人的代碼》由會員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)c語言》重言式判定參考了別人的代碼（6頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、重言式判定------參考了別人的代碼。。 2011-05-11 17:19 122人閱讀 評論(0) 收藏 舉報 【重言式判別】 [ 問題描述] 一個邏輯表達(dá)式如果對于其變元的任一種取值均為真，則成為重言式；反之，如果對于其變元的任一種取值都為假，則稱為矛盾式，然而，更多的情況下，既非重言式，也非矛盾式。試寫一個程序，通過真值表判別一個邏輯表達(dá)式屬于上述哪一類。， ? [ 基本要求] （1 ） 邏輯表達(dá)式從終端輸入，長度不超過一行。邏輯運算符包括 “ ｜ ” 、 “ ＆ ” 和 “ ～ ” ，分別表示或、與和非，運算優(yōu)先程度遞增，但可有括號改變，即括號內(nèi)的運算優(yōu)先。邏

2、輯變元為大寫字母。表達(dá)式中任何地方都可以含有多個空格符。 （2 ）若是重言式或矛盾式，可以只顯示 “ True? Forever ” 或 “ False Forever ” ，否則顯示 “ Satisfactible ” 以及變量名序列，與用戶交互。若用戶對表達(dá)式變元取定一組值，程序就求出并顯示邏輯表達(dá)式的值。 [ 測試數(shù)據(jù)] （1 ）（A ｜～A ）＆（B|~B ） （2 ）（A& ～A ）＆C （3 ）A|B|C|D|E ｜～A [ 實現(xiàn)提示] (1) 識別邏輯表達(dá)式的符號形式并建立二叉樹可以有兩種策略：自底向上的算符優(yōu)先法和自頂向下分割，先序遍歷建立二叉樹的方

3、法。 (2) 可設(shè)表達(dá)式中邏輯變量數(shù)不超過20 。真值的產(chǎn)生可以通過在一維數(shù)組上維護一個 “ 軟計數(shù)器 ” 實現(xiàn)，用遞歸算法實現(xiàn)更簡單。 [cpp] view plaincopyprint? 1. #include ?? 2. using?namespace?std;?? 3. struct?Arr?? 4. {?? 5. ???????char?letter;?? 6. ???????int?weight;?? 7. ???????};?? 8. class?Cys?? 9. {?? 10. ??????public:?? 11. ?????

4、????????Cys();?? 12. ?????????????void?GetTautology();//輸入表達(dá)式? ?? 13. ?????????????int?_CreateT(int?,int?);//虛擬創(chuàng)建二叉樹? ?? 14. ?????????????int?FindMin(int?,int?);//找到weight最小的? ?? 15. ?????????????int?count();??//計算可滿足式的值? ?? 16. ?????????????void?_recursion(Arr?*_arr,int?i?);//遞歸，窮舉? ?? 17. ??

5、???????????void?recursion();//使用接口函數(shù)? ?? 18. ?????????????void?Print();//輸出結(jié)果? ?? 19. ?????????????~Cys();//析構(gòu)釋放空間? ?? 20. ??????private:?? 21. ??????????????int?num;?? 22. ??????????????Arr?*array;?? 23. ??????????????Arr?_arr[20];?//存放字母? ?? 24. ??????????????int?_arrNum;??? 25. ??????????

6、????int?trueforever;?? 26. ??????????????int?falseforever;?? 27. ??????};?? 28. ???????? 29. ????Cys::Cys()?? 30. ??????{?? 31. ??????????trueforever=0;?? 32. ??????????falseforever=0;?? 33. ??????????array=new?Arr[20];?? 34. ??????????for(int?i=0;i<20;i++){?? 35. ????????????????array[i].

7、weight-1;?? 36. ????????????????array[i].letter='0';?? 37. ????????????????}?? 38. ???????????????_arrNum=0;?? 39. ???????????????num=0;?? 40. ????????????????}?? 41. ?void?Cys::GetTautology()?? 42. ?{?? 43. ??????int?has[27]={0};?? 44. ??????int?weight=0;?? 45. ??????char?ch;?? 46. ????c

8、out<<"請輸入一個邏輯表達(dá)式,以#結(jié)束"<>ch??&&?ch!='#')??? 48. ????{?? 49. ????????????????????? 50. ?????????????????? 51. ??????????????????if(ch=='?')?? 52. ??????????????????????continue;?? 53. ???????????????????????? 54. ????????????????????????switch(ch)?? 55. ????????????

9、????????????{???????? 56. ???????????????????????????????????case?'(':?? 57. ??????????????????????????????????????????weight+=4;?? 58. ??????????????????????????????????????????break;?? 59. ???????????????????????????????????case?')':?? 60. ??????????????????????????????????????????weight-=4;?

10、? 61. ??????????????????????????????????????????break;?? 62. ???????????????????????????????????case?'&':?? 63. ??????????????????????????????????????????array[num].letter=ch;?? 64. ??????????????????????????????????????????array[num++].weight=weight+2;?? 65. ???????????????????????????????????

11、???????break;??? 66. ???????????????????????????????????case?'|':?? 67. ??????????????????????????????????????????array[num].letter=ch;?? 68. ??????????????????????????????????????????array[num++].weight=weight+1;?? 69. ??????????????????????????????????????????break;?? 70. ????????????????????

12、???????????????case?'~':?? 71. ??????????????????????????????????????????array[num].letter=ch;?? 72. ??????????????????????????????????????????array[num++].weight=weight+3;?? 73. ??????????????????????????????????????????break;?? 74. ?????????????????????????????????default:?? 75. ?????????????

13、????????????????????????????array[num].letter=ch;?? 76. ??????????????????????????????????????????if(!has[array[num].letter-'A']){?? 77. ??????????????????????????????????????????_arr[_arrNum++].letter=array[num].letter;?? 78. ???????????????????????????????????????????????has[array[num].letter-'

14、A']=1;?? 79. ??????????????????????????????????????????????}?? 80. ?????????????????????????????????????????array[num++].weight=0;?? 81. ?????????????????????????????????????????break;??? 82. ????????????????????????}?????????????? 83. ??????????????????????????? 84. ???????????????????}?? 85

15、. ??????}?? 86. ??int?Cys::?FindMin(int?low,int?high)?? 87. ???{?? 88. ???????int?min=low;?? 89. ???????while(!array[min].weight)?? 90. ????????????????????min++;?????????? 91. ??? 92. ?????if(min

16、[i].weight

17、/?cout<<"create"<high)??? 108. ??????????return?1;????? 109. ?????else?if(low==high)?? 110. ?????{?????? 111. ????????//?cout<<"letter"<

18、arr[]中相同的字母? ?? 114. ??????????return?_arr[i].weight;//返回它的weight（1或0）? ?? 115. ???????????}?? 116. ??????else{??? 117. ????????????Min=FindMin(low,high);?? 118. ????????????//cout<<"array[Min].letter:?"<

19、??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(Min+1,high)

20、);??? 125. ???????????????????????????break;?? 126. ????????????????????????????}?????????????????????? 127. ????????????}???????????? 128. ?????}?? 129. ???int?Cys::?count()?//計算可滿足式的值? ?? 130. ???{?? 131. ???????int?i=0;?? 132. ???????cout<<"請給字母賦值"<

21、134. ?????????????????????cout<<_arr[i].letter;?? 135. ?????????????????????cin>>_arr[i++].weight;?? 136. ?????????????????????}?? 137. ??????if(_CreateT(0,num-1))?? 138. ???????????trueforever++;?? 139. ????????else?? 140. ???????????falseforever++;?? 141. ??????? 142. ???????}?? 143. ????

22、????? 144. ???void?Cys::_recursion(Arr?_arr[],int?i)//遞歸調(diào)用? ?? 145. ???{?? 146. ????????if(i<_arrNum){?? 147. ??????????????????????_arr[i].weight=0;?? 148. ?????????????????????//?cout<<"0"<

23、=1;?? 151. ?????????????????????//?cout<<"1"<

24、159. ????????????case?1:?? 160. ????????????????//?cout<<"trueforever++;"<

25、????????break;?? 167. ????????????default?:?? 168. ?????????????????break;?? 169. ????????????}?? 170. ????????}?? 171. ?????}?? 172. ?????????? 173. ???void?Cys::Print()?? 174. ?????{??if(trueforever?&&?falseforever)//如果真假同時存在就判斷它為?satisfactible. ?? 175. ?????????????cout<<"satisfactible."

26、<

27、??????}?? 186. ???????? 187. ?Cys::~Cys()?? 188. ????{?? 189. ???????????delete[]?array;?? 190. ???????????}?? 191. ??? 192. ??int?main()?? 193. ??{?? 194. ????????cout<<"-------------------重言式判別--------------------"<

28、?cys.GetTautology();?? 198. ????????cout<<"計算機窮舉請按't'?or?用戶賦值請按'n'"<>c;?? 200. ????????if(c=='t')?? 201. ????????????cys.recursion();//窮舉 ?? 202. ???????????else?? 203. ????????????cys.count();//賦值? ?? 204. ????????cys.Print();?? 205. ?????????system("pause");?? 206. ?????????return?0;?? 207. ?????????}???