学步园

只需要枚举p，q，r，s，t的所有组合即可，总共32中情况，然后用栈来实现。

//11332729	c00h00g	3295	Accepted	600K	0MS	G++	2067B	2013-03-10 10:57:10
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<string.h>
using namespace std;

char input[105];
stack<int> st;

int main(){
    while(scanf("%s",input)&&strcmp(input,"0")!=0){
        //枚举pqrst
        int p,q,r,s,t;
        int tmp[5];
        bool flag=true;
        for(int i=0;i<32;i++){
            memset(tmp,0,sizeof(tmp));
            int cnt=4,num=i;
            while(num){
                tmp[cnt--]=num%2;
                num=num/2;
            }
            p=tmp[0],q=tmp[1],r=tmp[2],s=tmp[3],t=tmp[4];
            int len=strlen(input);
            for(int j=len-1;j>=0;j--){
                if(input[j]=='p') st.push(p);
                if(input[j]=='q') st.push(q);
                if(input[j]=='r') st.push(r);
                if(input[j]=='s') st.push(s);
                if(input[j]=='t') st.push(t);
                //and
                if(input[j]=='K'){
                    int a=st.top();st.pop();
                    int b=st.top();st.pop();
                    st.push(a&b);
                }
                if(input[j]=='A'){
                    int a=st.top();st.pop();
                    int b=st.top();st.pop();
                    st.push(a|b);
                }
                if(input[j]=='N'){
                    int a=st.top();st.pop();
                    st.push(1-a);
                }
                if(input[j]=='C'){
                    int a=st.top();st.pop();
                    int b=st.top();st.pop();
                    st.push(b>=a?1:0);
                }
                if(input[j]=='E'){
                    int a=st.top();st.pop();
                    int b=st.top();st.pop();
                    st.push(a==b?1:0);
                }
            }//end for j
            if(st.top()==0){
                flag=false;
                break;
            } 
        }//end for i
        if(flag==true)
            printf("tautology\n");
        else
            printf("not\n");
    } 
    //system("pause");   
    return 0;
}