POJ 3295 Tautology (构造题)

时间:2022-03-31 00:14:22

字母:K, A, N, C, E 表示逻辑运算

字母:p, q, r, s, t 表示逻辑变量 0 或 1

给一个字符串代表逻辑表达式,如果是永真式输出tautology 否则输出not

枚举每个逻辑变量的值,5个变量,共2^5种情况,对于每种情况都为真则为永真式。

代码:

/***************************************
Problem: 3295 User:
Memory: 688K Time: 0MS
Language: G++ Result: Accepted
***************************************/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack> using namespace std; int p, q, r, s, t; // variables 0 or 1 int st[32][5] = {0,0,0,0,0, 0,0,0,0,1, 0,0,0,1,0, 0,0,0,1,1, 0,0,1,0,0, 0,0,1,0,1, 0,0,1,1,0,
0,0,1,1,1, 0,1,0,0,0, 0,1,0,0,1, 0,1,0,1,0, 0,1,0,1,1, 0,1,1,0,0, 0,1,1,0,1,
0,1,1,1,0, 0,1,1,1,1, 1,0,0,0,0, 1,0,0,0,1, 1,0,0,1,0, 1,0,0,1,1, 1,0,1,0,0,
1,0,1,0,1, 1,0,1,1,0, 1,0,1,1,1, 1,1,0,0,0, 1,1,0,0,1, 1,1,0,1,0, 1,1,0,1,1,
1,1,1,0,0, 1,1,1,0,1, 1,1,1,1,0, 1,1,1,1,1};
char exp[105]; int get_value(char ch)
{
switch(ch) {
case 'p': return p;
case 'q': return q;
case 'r': return r;
case 's': return s;
case 't': return t;
case 'N': return -1;
default: return -2;
}
} int WFF(char ch, int a, int b)
{
if (ch == 'K') return a && b;
if (ch == 'A') return a || b;
if (ch == 'C') return (!b) || a;
if (ch == 'E') return a == b;
} bool solve()
{
int i, a, b;
int len = strlen(exp);
stack<int> mystack;
for (i = len - 1; i >= 0; --i) {
if (get_value(exp[i]) >= 0) {
a = get_value(exp[i]);
mystack.push(a);
} else if (get_value(exp[i]) == -1) {
a = mystack.top(); mystack.pop();
a = !a;
mystack.push(a);
} else {
a = mystack.top(); mystack.pop();
b = mystack.top(); mystack.pop();
a = WFF(exp[i], b, a);
mystack.push(a);
}
}
return mystack.top();
} int main()
{
int i;
while (scanf("%s", exp) != EOF) {
if (exp[0] == '0') break;
for (i = 0; i < 32; ++i) {
p = st[i][0]; q = st[i][1]; r = st[i][2];
s = st[i][3]; t = st[i][4];
if (!solve()) break;
}
if (i == 32) puts("tautology");
else puts("not");
}
return 0;
}