题意简述
输入长度≤100的由K,A,N,C,E,p,q,r,s,t组成的逻辑表达式,其中K,A,N,C,E分别代表与,或,非,条件,等价,小写字母为命题变量。
若该式为永真式,则输出tautology,否则输出not
输入数据有多组,遇0停止输入。
算法分析
考虑表达式最多只有5个变量,真值表最多只有2^5=32种排列,所以选择枚举所有排列判断表达式是否恒真。
使用一个int型变量,从0枚举至31,则其二进制拆分成位后刚好匹配了32种01全排列。在使用时,假设想取出第4位,只需将它&(1000)2,不等0则为1,否则为0。其余位置可类推。
判断一个确定赋值的表达式是否为真,可以参照栈的多项式处理应用。由于不牵扯括号运算所以较为简单。从右向左扫描表达式,遇变量则将其赋值压入栈中。遇单目运算符(not)则对栈顶元素进行操作。遇双目运算符则弹出栈顶两个元素,运算后将结果压回栈中。
最后判断栈顶剩余元素(其实栈中只剩下一个元素)是否为1即可。
Problem Status: AC。时间0ms,内存360k
程序样例
#include<stdio.h> #include<string.h> int judge(char c[], int f1, int l) { int s[100] = {0}, h, p, f[5] = {1}, i; for (i = 1; i < 5; i++) f[i] = f[i - 1] * 2; for (i = 0; i < 5; i++) { f[i] = f[i] & f1; if (f[i] > 0) f[i] = 1; } p = l - 1; h = 0; while (p >= 0) { switch (c[p]) { case 'p': s[h] = f[0]; h++; break; case 'q': s[h] = f[1]; h++; break; case 'r': s[h] = f[2]; h++; break; case 's': s[h] = f[3]; h++; break; case 't': s[h] = f[4]; h++; break; case 'K': h = h - 2; if (s[h] == 1 && s[h + 1] == 1) h++; else { s[h] = 0; h++; } break; case 'A': h = h - 2; if (s[h] == 0 && s[h + 1] == 0) h++; else { s[h] = 1; h++; } break; case 'N': h = h - 1; if (s[h] == 0) s[h] = 1; else s[h] = 0; h++; break; case 'C': h = h - 2; if (s[h] == 0 && s[h + 1] == 1) h++; else { s[h] = 1; h++; } break; case 'E': h = h - 2; if (s[h] == s[h + 1]) s[h] = 1; else s[h] = 0; h++; break; } p--; } return s[0]; } int main() { char c[100]; int i, l; scanf("%s", c); while (strcmp(c, "0") != 0) { l = strlen(c); for (i = 0; i < 32; i++) if (!judge(c, i, l)) { printf("not\n"); break; } if (i == 32) printf("tautology\n"); scanf("%s", c); } return 0; }