题意简述

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

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;
}