POJ 3295 Tautology(枚举 + 构造)

红太狼 2021-10-01 01:08 221阅读 0赞

Tautology

<table> 
 <tbody> 
 <tr> 
 <td>Time Limit:&nbsp;1000MS</td> 
 <td>&nbsp;</td> 
 <td>Memory Limit:&nbsp;65536K</td> 
 </tr> 
 <tr> 
 <td>Total Submissions:&nbsp;5306</td> 
 <td>&nbsp;</td> 
 <td>Accepted:&nbsp;1997</td> 
 </tr> 
 </tbody> 
</table>

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:

*  p, q, r, s, and t are WFFs
 *  if *w* is a WFF, N*w* is a WFF
 *  if *w* and *x* are WFFs, K*wx*, A*wx*, C*wx*, and E*wx* 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.

<table> 
 <tbody> 
 <tr> 
 <td> Definitions of K, A, N, C, and E </td> 
 </tr> 
 </tbody> 
</table>

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

Source

[Waterloo Local Contest][], 2006.9.30

解题报告：就是判断所给的式子是否为永真式；其中K表示&&（并）A表示||（或），N表示！（非），C表示a->b(!a||b)，E表示等值(a == b);他们的值有两种1或0，所以用枚举的方法，枚举一遍即可；

代码如下：

#include <iostream>
 #include <cstdio>
 #include <cstring>
 using namespace std;
 const int N = 105;
 char str[N];
 int flag[6], st;
 int Judge()
 {
 
 int p, q;
 switch(str[++st])
 {
 
 case 'K': p = Judge(); q = Judge(); return p && q;
 case 'A': p = Judge(); q = Judge(); return p || q;
 case 'N': return !Judge();
 case 'C': p = Judge(); q = Judge(); return !p || q;
 case 'E': return Judge() == Judge();
 default: return flag[str[st] - 'p' ];
 }
 }
 int main()
 {
 
 int i, j, k, l, m, ans;
 while(scanf("%s", str) != EOF && str[0] != '0')
 {
 
 ans = 1;
 for (i = 0; i <= 1; ++i)//相当于枚举
 {
 
 flag[0] = i;
 for (j = 0; j <= 1; ++j)
 {
 
 flag[1] = j;
 for (k = 0; k <= 1; ++k)
 {
 
 flag[2] = k;
 for (l = 0; l <= 1; ++l)
 {
 
 flag[3] = l;
 for (m = 0; m <= 1; ++m)
 {
 
 flag[4] = m;
 st = -1;
 ans = ans && Judge();
 if (!ans)
 {
 
 break;
 }
 }
 }
 }
 }
 }
 if (ans)
 {
 
 printf("tautology\n");
 }
 else
 {
 
 printf("not\n");
 }
 }
 return 0;
 }

转载于:https://www.cnblogs.com/lidaojian/archive/2012/02/25/2367889.html

[Waterloo Local Contest]: http://poj.org/searchproblem?field=source&key=Waterloo+Local+Contest