1.原题
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:
1.p, q, r, s, and t are WFFs
2.if w is a WFF, Nw is a WFF
3.if w and x are WFFs, Kwx, Awx, Cwx, and Ewx are WFFs.
The meaning of a WFF is defined as follows:
1.p, q, r, s, and t are logical variables that may take on the value 0 (false) or 1 (true).
2.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
2.题意
就是说给你一个string的字符串，然后就是有一套规则，p, q, r, s, t可以任意是0或1，然后K，A，N，C，E的与前面的字符匹配的值在上面的表格中，即“K11”为“1”，“N1”为“0”等，然后在最后看结果是否为0，如果有一种情况为0，则输出not,如果没有这种情况的话，那就输出tautology。
3.思路
我的思路：就是先用map存储一个序列，比如mapList[“K11”] = ‘1’,然后（p，q，r，s，t）从（0，0，0，0，0）到（1，1，1，1，1）的所有情况全部遍历一遍，然后判断是否为零，方法的话就是在从字符串最后一位开始，一直往前，每次的话将map中的值压栈，在再出栈，知道最后出现结果为止，判断是否为0
大神思路：本来这道题在训练计划中，是属于“构造法”的，但是我感觉我的思路丝毫没有啥构造的感觉，然后网上查了一下，才发现还可以这样做，就是压栈和出栈的思路是对的，只要是表格中K可以表示成x&y，A是x||y,C是(!x)||y,E是x==y,N是!x，这样的话，就不用那么麻烦的判断了。这样才是构造啊，这是厉害！！完全没有想到
4.代码(别人的)
贴个链接 http://blog.csdn.net/lyy289065406/article/details/6642766