《数据结构c语言》重言式判定参考了别人的代码.doc

重言式判定-参考了别人的代码。 2011-05-11 17:19 122人阅读 评论(0) 收藏 举报 【重言式判别】 问题描述 一个逻辑表达式如果对于其变元的任一种取值均为真，则成为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式，然而，更多的情况下，既非重言式，也非矛盾式。试写一个程序，通过真值表判别一个逻辑表达式属于上述哪一类。，   基本要求 （1 ） 逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括 “ ” 、 “ ” 和 “ ” ，分别表示或、与和非，运算优先程度递增，但可有括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。 （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 。真值的产生可以通过在一维数组上维护一个 “ 软计数器 ” 实现，用递归算法实现更简单。 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 );/虚拟创建二叉树    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.