POJ-3295 解题报告

题意简述

输入长度≤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

程序样例

[c]#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("notn");
break;
}
if(i==32) printf("tautologyn");
scanf("%s",c);
}
return 0;
}
[/c]

Leave a Reply

Your email address will not be published. Required fields are marked *