POJ 3295 Tautology(구조)

Tautology
Time Limit: 1000MS
 
Memory Limit: 65536K
Total Submissions: 6088
 
Accepted: 2315
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, Nwis 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
 
 
 
 
간단한 문제.코드를 보면 알 수 있을 거예요.

/*

POJ 3295

 

p,q,r,s,t 

 



AC  G++  684K  0MS

*/



#include<stdio.h>

#include<iostream>

#include<string.h>

using namespace std;

const int MAXN=120;

int sta[MAXN];// 

char str[MAXN];

int p,q,r,s,t;

void  DoIt()

{

    int top=0;

    int len=strlen(str);

    for(int i=len-1;i>=0;i--)

    {

        if(str[i]=='p') sta[top++]=p;

        else if(str[i]=='q') sta[top++]=q;

        else if(str[i]=='r') sta[top++]=r;

        else if(str[i]=='s') sta[top++]=s;

        else if(str[i]=='t') sta[top++]=t;

        else if(str[i]=='K')

        {

            int t1=sta[--top];

            int t2=sta[--top];

            sta[top++]=(t1&&t2);

        }

        else if(str[i]=='A')

        {

            int t1=sta[--top];

            int t2=sta[--top];

            sta[top++]=(t1||t2);

        }

        else if(str[i]=='N')

        {

            int t1=sta[--top];

            sta[top++]=(!t1);

        }

        else if(str[i]=='C')

        {

            int t1=sta[--top];

            int t2=sta[--top];

            if(t1==1&&t2==0)sta[top++]=0;

            else sta[top++]=1;

        }

        else if(str[i]=='E')

        {

            int t1=sta[--top];

            int t2=sta[--top];

            if((t1==1&&t2==1)||(t1==0&&t2==0)) sta[top++]=1;

            else sta[top++]=0;

        }

    }

}

bool solve()

{

    for(p=0;p<2;p++)

      for(q=0;q<2;q++)

        for(r=0;r<2;r++)

           for(s=0;s<2;s++)

              for(t=0;t<2;t++)

              {

                  DoIt();

                  if(sta[0]==0)return false;

              }

    return true;

}



int main()

{

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    while(scanf("%s",&str))

    {

        if(strcmp(str,"0")==0)break;

        if(solve())printf("tautology
");

        else printf("not
");

    }

    return 0;

}