ETautology(永真式)

题目描述

WFF &＃39;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&＃61;0, q&＃61;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

题解:逻辑判断表达式&＃xff0c;判断这个表达式是否为永真式。有5个数&＃xff0c;所以共有32中情况&＃xff0c;枚举&＃43;递归搞定。
代码如下&＃xff1a;

#include
#include
#include
#include
#include
#define maxn 10000
#define INF 0x3f3f3f3f
using namespace std;
int q,p,r,s,t,pos;
char a[105];
bool cal()
{pos&＃43;&＃43;;switch(a[pos]){ //switch真的是好用啊&＃xff0c;分情况递归即可case &＃39;p&＃39;: return p;case &＃39;q&＃39;: return q;case &＃39;r&＃39;: return r;case &＃39;s&＃39;: return s;case &＃39;t&＃39;: return t;case &＃39;K&＃39;: return cal()&cal();case &＃39;A&＃39;: return cal()|cal();case &＃39;N&＃39;: return !cal();case &＃39;C&＃39;: return (!cal())|cal();case &＃39;E&＃39;: return cal()&＃61;&＃61;cal();}
}
int main()
{while(scanf("%s",a)!&＃61;EOF && a[0] !&＃61; &＃39;0&＃39;){bool flag &＃61; true;for(p &＃61; 0; p < 2 && flag; p&＃43;&＃43;) //这里的flag表示&＃xff0c;只要有一种情况不成立&＃xff0c;则推出循环for(q &＃61; 0; q < 2 && flag; q&＃43;&＃43;)for(r &＃61; 0; r < 2 && flag; r&＃43;&＃43;)for(s &＃61; 0; s < 2 && flag; s&＃43;&＃43;)for(t &＃61; 0; t < 2 && flag; t&＃43;&＃43;){pos &＃61; -1;flag &＃61; cal();}if(flag)printf("tautology\n");else printf("not\n");}return 0;
}