【poj】3295 Tautology 栈 KANCE pqrst 恒真式

题意为K、A、N、C、E（分别表示与、或、非、包含于、相等5种运算）来运算p、q、r、s、t（分别为5个变量，但只能为0或者1），判断在各种取值情况下，表达式是否为恒真式。从串尾往串首运算，一个栈就OK了。遇到KANCE就运算，结果马上入栈，最后结果正确。

void Push(Stack*p,boolnum)
{
     p->n[++p->top]=num;
}
bool Pop(Stack*p)
{
     return p->n[p->top--];
}
void InitStack(Stack*p)
{
     p->top=-1;
     memset(p->n,0,sizeof(p->n));
}
int IsStackEmpty(Stack*p)
{
     return-1== p->top;
}
bool Cal(char symbol,bool w,bool x)
{
     switch(symbol)
     {
         case'K' :
         {
             returnw&x;
         }
         case'A' :
         {
             returnw | x;
         }
         case'C' :
         {
             returnw<=x;
         }
         case'E' :
         {
             returnw==x;
         }
     }
}
int main()
{
     Stackst;
     int i,j,len;
     bool w,x,succ;
     charstr[MAX],symbol,tc;

     while(scanf("%s",str) &&str[0]!='0')
     {
         succ=1;
         if (1== (len=strlen(str))) //仅有一个变量，不恒为0
         {
             printf("notn");
             continue;
         }
         for (j=0; succ&&j<32; j++) //枚举32种情况
         {
             InitStack(&st);
             for (i=len-1; i>=0; i--)
             {
                 //为表达式运算标志
                 if (str[i]=='K' || str[i]=='A' || str[i]=='N'
                                     || str[i]=='C' || str[i]=='E')
                 {
                     w=Pop(&st);
                     if ('N'==str[i])
                     {
                         Push(&st,!w);
                     }
                     else
                     {
                         x=Pop(&st);
                         Push(&st,Cal(str[i],w,x));
                     }
                 }
                 //为参与运算的变量
                 else
                 {
                     Push(&st,pqrst[j][str[i]-'p']);
                 }
             }
             //栈中最后剩下运算结果
             if (!Pop(&st))
             {
                 //结果为false则表达式不恒真，退出循环
                 succ=0;
                 break;
             }
         }
         if (succ)
         {
             printf("tautologyn");
         }
         else
         {
             printf("notn");
         }
     }
     return 0;
}

2011-03-30 22:59 发表于百度空间，今搬至CU。