POJ3295Tautology

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<stack>
  4 #include<cstring>
  5 using namespace std ;
  6 stack<int >Q;
  7 int p,q,r,s,t ,i,j;
  8 int a,b,flag;
  9 int judge(char ch,int p,int q, int r,int s,int t)
 10 {
 11     switch(ch)
 12     {
 13         case 'p':Q.push(p);return 1;
 14         case 'q':Q.push(q);return 1;
 15         case 'r':Q.push(r);return 1;
 16         case 's':Q.push(s);return 1;
 17         case 't':Q.push(t);return 1;
 18     }
 19     return 0 ;
 20 }
 21 void judge2(char sh)
 22 {
 23     switch(sh)
 24     {
 25         case 'K':
 26         {
 27             a = Q.top() ;
 28             Q.pop();
 29             b = Q.top();
 30             Q.pop() ;
 31             Q.push(a&&b);
 32             break ;
 33         }
 34         case 'A':
 35         {
 36             a = Q.top();
 37             Q.pop();
 38             b = Q.top();
 39             Q.pop();
 40             Q.push(a||b);
 41             break;
 42         }
 43         case 'N':
 44         {
 45             a = Q.top();
 46             Q.pop();
 47             Q.push(!a);
 48             break ;
 49         }
 50         case 'C':
 51         {
 52             a = Q.top();
 53             Q.pop();
 54             b = Q.top();
 55             Q.pop();
 56             Q.push((!a)||b);
 57             break;
 58         }
 59         case 'E':
 60         {
 61             a = Q.top();
 62             Q.pop();
 63             b = Q.top();
 64             Q.pop();
 65             Q.push(a == b);
 66             break;
 67         }
 68     }
 69     return;
 70 }
 71 int main()
 72 {
 73     char ah[101];
 74     while(cin>>ah)
 75     {
 76         if(strcmp(ah,"0") == 0)
 77         break;
 78         flag = 1;
 79         int len = strlen(ah)-1;
 80         for(p = 0 ; p <= 1 ; p++)
 81         {
 82             for(q = 0 ; q <= 1 ; q++)
 83             {
 84                 for(r = 0 ; r <= 1 ; r++)
 85                 {
 86                     for(s = 0 ; s <= 1 ; s++)
 87                     {
 88                         for(t = 0 ; t <= 1 ; t++)
 89                         {
 90                             for(i = len ; i >= 0 ; i--)
 91                             {
 92                                 if(!judge(ah[i],p,q,r,s,t))
 93                                 {
 94                                     judge2(ah[i]);
 95                                 }
 96                             }
 97                             j = Q.top();
 98                             Q.pop();
 99                             if(!j)
100                             {
101                                 //cout<<"not"<<endl;
102                                 flag = 0;
103                                 break;
104                             }
105                         }
106                         if(!flag) break;
107                     }
108                     if(!flag) break;
109                 }
110                 if(!flag) break;
111             }
112             if(!flag) break ;
113         }
114         if(flag)
115         cout<<"tautology"<<endl ;
116         else cout<<"not"<<endl;
117     }
118     return 0 ;
119 }
View Code
大神的博客，两种方法实现的
http://blog.csdn.net/lyy289065406/article/details/6642766