《數據結構c語言》重言式判定參考了別人的代碼

重言式判定-參考了別人的代碼。 2011-05-11 17:19 122人閱讀 評論(0) 收藏 舉報 【重言式判別】 問題描述 一個邏輯表達式如果對于其變元的任一種取值均為真，則成為重言式；反之，如果對于其變元的任一種取值都為假，則稱為矛盾式，然而，更多的情況下，既非重言式，也非矛盾式。試寫一個程序，通過真值表判別一個邏輯表達式屬于上述哪一類。，   基本要求 （1 ） 邏輯表達式從終端輸入，長度不超過一行。邏輯運算符包括 “ ” 、 “ ” 和 “ ” ，分別表示或、與和非，運算優(yōu)先程度遞增，但可有括號改變，即括號內的運算優(yōu)先。邏輯變元為大寫字母。表達式中任何地方都可以含有多個空格符。 （2 ）若是重言式或矛盾式，可以只顯示 “ True  Forever ” 或 “ False Forever ” ，否則顯示 “ Satisfactible ” 以及變量名序列，與用戶交互。若用戶對表達式變元取定一組值，程序就求出并顯示邏輯表達式的值。 測試數據 （1 ）（A A ）（B|B ） （2 ）（A& A ）C （3 ）A|B|C|D|E A 實現提示 (1) 識別邏輯表達式的符號形式并建立二叉樹可以有兩種策略：自底向上的算符優(yōu)先法和自頂向下分割，先序遍歷建立二叉樹的方法。 (2) 可設表達式中邏輯變量數不超過20 。真值的產生可以通過在一維數組上維護一個 “ 軟計數器 ” 實現，用遞歸算法實現更簡單。 cpp view plaincopyprint?1. #include<iostream>   2. using namespace std;  3. struct Arr  4.   5.        char letter;  6.        int weight;  7.          8. class Cys  9.   10.       public:  11.              Cys();  12.              void GetTautology();/輸入表達式    13.              int _CreateT(int ,int );/虛擬創(chuàng)建二叉樹    14.              int FindMin(int ,int );/找到weight最小的    15.              int count();  /計算可滿足式的值    16.              void _recursion(Arr *_arr,int i );/遞歸，窮舉    17.              void recursion();/使用接口函數    18.              void Print();/輸出結果    19.              Cys();/析構釋放空間    20.       private:  21.               int num;  22.               Arr *array;  23.               Arr _arr20; /存放字母    24.               int _arrNum;   25.               int trueforever;  26.               int falseforever;  27.         28.         29.     Cys:Cys()  30.         31.           trueforever=0;  32.           falseforever=0;  33.           array=new Arr20;  34.           for(int i=0;i<20;i+)  35.                 arrayi.weight-1;  36.                 arrayi.letter='0'  37.                   38.                _arrNum=0;  39.                num=0;  40.                   41.  void Cys:GetTautology()  42.    43.       int has27=0;  44.       int weight=0;  45.       char ch;  46.     cout<<"請輸入一個邏輯表達式,以#結束"<<endl;  47.     while(cin>>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.                                    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+.letter=arraynum.letter;  78.                                                hasarraynum.letter-'A'=1;  79.                                                 80.                                          arraynum+.weight=0;  81.                                          break;   82.                                       83.                            84.                      85.         86.   int Cys: FindMin(int low,int high)  87.      88.        int min=low;  89.        while(!arraymin.weight)  90.                     min+;          91.    92.      if(min<high)  93.           for(int i=min;i<high+1;i+)  94.           if(arrayi.weight && arrayi.weight<arraymin.weight)  95.               min=i;  96.           return min;       97.             98.      else     99.           return 0;  100.     101.              102.          103.  int Cys:_CreateT(int low,int high)  104.     105.      int Min=0;  106.     / cout<<"create"<<endl;   107.      if(low>high)   108.           return 1;     109.      else if(low=high)  110.            111.         / cout<<"letter"<<arraylow.letter<<endl;   112.           int i;  113.           for(i=0;_arri.letter!=arraylow.letter;i+);/從array中尋找與_arr中相同的字母    114.           return _arri.weight;/返回它的weight（1或0）    115.              116.       else   117.             Min=FindMin(low,high);  118.             /cout<<"arrayMin.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(Min+1,high);   125.                            break;  126.                                                   127.                         128.        129.    int Cys: count() /計算可滿足式的值    130.      131.        int i=0;  132.        cout<<"請給字母賦值"<<endl;  133.     while(_arrNum-)  134.                      cout<<_arri.letter;  135.                      cin>>_arri+.weight;  136.                        137.       if(_CreateT(0,num-1)  138.            trueforever+;  139.         else  140.            falseforever+;  141.        142.          143.          144.    void Cys:_recursion(Arr _arr,int i)/遞歸調用    145.      146.         if(i<_arrNum)  147.                       _arri.weight=0;  148.                      / cout<<"0"<<endl;   149.                       _recursion(_arr,i+1);  150.                       _arri.weight=1;  151.                      / cout<<"1"<<endl;   152.                       _recursion(_arr,i+1);  153.                         154.        else  155.         if(!trueforever|!falseforever)       156.           157.             switch(_CreateT(0,num-1)  158.               159.             case 1:  160.                 / cout<<"trueforever+;"<<endl;   161.                  trueforever+;  162.                  break;  163.             case 0:  164.                 / cout<<"falseforever+;"<<endl;   165.                  falseforever+;  166.                  break;  167.             default :  168.                  break;  169.               170.           171.        172.           173.    void Cys:Print()  174.        if(trueforever && falseforever)/如果真假同時存在就判斷它為 satisfactible.   175.              cout<<"satisfactible."<<endl;   176.            else if(!trueforever)  177.              cout<<"falseforever."<<endl;  178.              else  179.              cout<<"trueforever. "<<endl;  180.              181.             182.  void Cys:recursion()  183.    184.       _recursion(_arr,0);  185.         186.         187.  Cys:Cys()  188.       189.            delete array;  190.              191.    192.   int main()  193.     194.         cout<<"-重言式判別-"<<endl;     195.         Cys cys;  196.         char c;  197.         cys.GetTautology();  198.         cout<<"計算機窮舉請按't' or 用戶賦值請按'n'"<<endl;  199.         cin>>c;  200.         if(c='t')  201.             cys.recursion();/窮舉   202.            else  203.             cys.count();/賦值    204.         cys.Print();  205.          system("pause");  206.          return 0;  207.