3295:Tautology

keyword

構文解析　論理式　BruteForce　C++

概要

真偽値をもつ元が5つと、それぞれの組み合わせからなる論理式がある。論理式の値が真偽値の任意の組み合わせに対して1となるかどうかを判定する問題。
まずは式を構文解析する。あとは真偽の組み合わせ2^5全通り試すだけ。

char str[110];
int n;
int tf[5];
int p;


int eval(){
    if(p==n) return -1;
    int a = str[p++];
    switch(a){
        case 'p': return tf[0];
        case 'q': return tf[1];
        case 'r': return tf[2];
        case 's': return tf[3];
        case 't': return tf[4];
        case 'K': return K();
        case 'A': return A();
        case 'N': return N();
        case 'C': return C();
        case 'E': return E();
    }
    return -1;
}

int K(){
    int w = eval(), x = eval();
    if(w==-1 || x==-1) return -1;
    return w*x;
}

int A(){
    int w = eval(), x = eval();
    if(w==-1 || x==-1) return -1;
    return (w+x)?1:0;
}

int N(){
    int w = eval();
    if(w==-1) return -1;
    return 1-w;
}

int C(){
    int w = eval(), x = eval();
    if(w==-1 || x==-1) return -1;
    return ((1-w)+x)?1:0;
}

int E(){
    int w = eval(), x = eval();
    if(w==-1 || x==-1) return -1;
    return (w==x)?1:0;
}

int main(){
    int mask, i;
    while(scanf("%s\n",str)){
        if(!strcmp(str,"0")) break;
        n = strlen(str);
        REP(mask,1<<5){
            REP(i,5)tf[i] = (mask>>i)&1;
            p=0;
            if(!eval()) break;
        }
        puts((mask==1<<5)?"tautology":"not");
    }
}