poj 3295 Tautology [ 栈 ]

Tautology

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 10107		Accepted: 3850

Description

WFF 'N PROOF is a logic game played with dice. Each die has six faces representing some subset of the possible symbols K, A, N, C, E, p, q, r, s, t. A Well-formed formula (WFF) is any string of these symbols obeying the following rules:

p, q, r, s, and t are WFFs
if w is a WFF, Nw is a WFF
if w and x are WFFs, Kwx, Awx, Cwx, and Ewx are WFFs.

The meaning of a WFF is defined as follows:

p, q, r, s, and t are logical variables that may take on the value 0 (false) or 1 (true).
K, A, N, C, E mean and, or, not, implies, and equals as defined in the truth table below.

Definitions of K, A, N, C, and E

w x	Kwx	Awx	Nw	Cwx	Ewx
1 1	1	1	0	1	1
1 0	0	1	0	0	0
0 1	0	1	1	1	0
0 0	0	0	1	1	1

A tautology is a WFF that has value 1 (true) regardless of the values of its variables. For example, ApNp is a tautology because it is true regardless of the value of p. On the other hand, ApNq is not, because it has the value 0 for p=0, q=1.

You must determine whether or not a WFF is a tautology.

Input

Input consists of several test cases. Each test case is a single line containing a WFF with no more than 100 symbols. A line containing 0 follows the last case.

Output

For each test case, output a line containing tautology or not as appropriate.

Sample Input

ApNp
ApNq
0

Sample Output

tautology
not

Source

Waterloo Local Contest, 2006.9.30

用栈处理计算过程，每种情况暴力跑一次

13990104

njczy2010

3295

Accepted

552K

47MS

G++

2592B

2015-03-21 17:29:21

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <stack>
  4 #include <vector>
  5 #include <algorithm>
  6 #include <map>
  7 
  8 #define ll long long
  9 int const N = 105;
 10 int const M = 205;
 11 int const inf = 1000000000;
 12 ll const mod = 1000000007;
 13 
 14 using namespace std;
 15 
 16 int l;
 17 char ssss[N];
 18 int flag;
 19 int ss[N];
 20 
 21 void ini()
 22 {
 23     flag=1;
 24     l=strlen(ssss);
 25     //printf(" l=%d
",l);
 26 }
 27 
 28 int fun(int x,int a,int b)
 29 {
 30     if(x==2){
 31         return a & b;
 32     }
 33     else if(x==3){
 34         return a | b;
 35     }
 36     else if(x==4){
 37         if(a==1 && b==0){
 38             return 0;
 39         }
 40         else return 1;
 41     }
 42     else if(x==5){
 43         return a==b ? 1 : 0;
 44     }
 45     return 0;
 46 }
 47 
 48 void cal(int p,int q,int r,int s,int t)
 49 {
 50    // printf(" p=%d q=%d flag=%d
",p,q,flag);
 51     int top;
 52     map<char,int>mp;
 53     mp['p']=p;
 54     mp['q']=q;
 55     mp['r']=r;
 56     mp['s']=s;
 57     mp['t']=t;
 58     mp['K']=2;
 59     mp['A']=3;
 60     mp['N']=6;
 61     mp['C']=4;
 62     mp['E']=5;
 63     top=0;
 64     int te;
 65     int a,b,x;
 66     for(int i=0;i<l;i++){
 67         te=mp[ ssss[i] ];
 68         top++;
 69         ss[top]=te;
 70         if(te>=2){
 71             continue;
 72         }
 73         else{
 74             while(1)
 75             {
 76                 if(top>=2 && ss[top-1]==6){
 77                     te=ss[top];
 78                     top--;
 79                     ss[top]=1-te;
 80                 }
 81                 else if(top>=3 && ss[top]<=1 && ss[top-1]<=1 && ss[top-2]>=2 && ss[top-2]<=5){
 82                     b=ss[top];
 83                     top--;
 84                     a=ss[top];
 85                     top--;
 86                     x=ss[top];
 87                     //top++;
 88                     ss[top]=fun(x,a,b);
 89                    // printf(" top=%")
 90                 }
 91                 else break;
 92             }
 93 
 94         }
 95     }
 96     if(ss[1]==0){
 97         flag=0;
 98     }
 99     //printf(" p=%d q=%d ss=%d flag=%d
",p,q,ss[1],flag);
100 }
101 
102 void solve()
103 {
104     //printf("  sol
");
105     int p,q,r,s,t;
106     for(p=0;p<=1;p++)
107         for(q=0;q<=1;q++)
108             for(r=0;r<=1;r++)
109                 for(s=0;s<=1;s++)
110                     for(t=0;t<=1;t++)
111                         cal(p,q,r,s,t);
112 }
113 
114 void out()
115 {
116     if(flag==1){
117         printf("tautology
");
118     }
119     else{
120         printf("not
");
121     }
122 }
123 
124 int main()
125 {
126     //freopen("data.in","r",stdin);
127     //scanf("%d",&T);
128    // for(cnt=1;cnt<=T;cnt++)
129     //while(T--)
130     while(scanf("%s",ssss)!=EOF)
131     {
132         if(strcmp(ssss,"0")==0) break;
133         ini();
134         solve();
135         out();
136     }
137 }