3295 Tautology

問題概要

p,q,r,s,tは変数で1(true)または0(false)の値を取る。
K,A,N,C,Eは、それぞれand,or,not,imply,equalを表わす。

与えられた式が変数の値によらずtrueの値を取る時、tautologyを、そうでないときはnotを出力せよ。

解法

p,q,r,s,tにそれぞれ0,1の値をあてはめて式の値を見る。
長さ100以下の式に、変数のあてはめ方を32通り試すだけなので間に合う。

構文解析は今までに見た文字をグローバルで持っておくとどこまでが項かを判別する必要がないので楽に書けるかもしれない。

ソースコード

char str[101],in[101];
int n,p;

int eval(){
	if(isdigit(in[p]))return in[p++]-'0';
	char c=in[p++];
	if(c=='N')return !eval();
	
	int w=eval(),x=eval();
	if(c=='K')return w&x;
	if(c=='A')return w|x;
	if(c=='C')return !w|x;
	return w==x;
}
int main(){
	while(scanf("%s",str),str[0]!='0'){
		n=strlen(str);
		rep(i,1<<5){
			strcpy(in,str);
			rep(j,n)if('p'<=in[j]&&in[j]<='t')in[j]=i&1<<in[j]-'p'?'1':'0';
			
			p=0;
			if(!eval()){
				puts("not"); goto END;
			}
		}
		puts("tautology"); END:;
	}
	return 0;
}