POJ 3295 Tautology （结构法 栈）

POJ 3295 Tautology （构造法 栈）

题目链接：http://poj.org/problem?id=3295

一整天也就出一个题都习惯了。自代码出来刷了一天的WA。 TAT

这个题就是给你一串逻辑关系表达式，让你判断是不是重言式，这个题有两个难度点：

1.怎么判断这是不是一个重言式

2.逻辑语句是题目定义的语法，怎么知道这个逻辑语句描述的是什么

 

对于第一点，因为只有五个变量p，q，r，s，t，那么会有2^5次方种情况，那就直接枚举就好啦。

第二个问题，我想起来在寒假做过的一个由前缀式转中缀式的题目，当时下了一个doc啃了半天，虽然把题出来了，但其实就是模板水过的，但那个题让我知道，栈在表达式上是可以改变顺序的，所以遇到这种题我就会像栈上靠边，这个题也一样。

 

栈是通过先记录两个操作数再判断操作符来实现表达式运算，那么想要计算表达式，就要先在栈中存在两个操作数，然后再根据操作符运算。

这样思路就出来了

 

先那标准测试数据来说：

表达式 ：ApNp

1.先把p的布尔值压入栈

2.因为有个NP，所以把刚才压入栈的p弹出，并对其布尔值取反后压入栈

3.再把p压入栈

4.因为有个二元操作符A，把栈中的两个元素弹出，对其操作（“||”）后，把其结果压入栈。

最后栈顶便是结果。

 

剩下的就是构建模拟一个栈模拟的问题了。

但是在对于a→b这种对先后有顺序的操作符，一定要注意计算顺序，我的这个代码实现是从后先前扫，先入栈的反而在表带式的后面，也就是说判断的时候注意操作符的逆序计算问题，这个不知道WA了多少次。

代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int p,q,r,s,t;
char str[1000];

bool z[10000];

int zh (char c)
{
    switch (c)
    {
    case 'p':
        return p;
    case 'q':
        return q;
    case 'r':
        return r;
    case 's':
        return s;
    case 't':
        return t;
    }
}

bool js (int a,int b,char c)
{
    if (c == 'K')
        return a && b;
    if (c == 'A')
        return a || b;
    if (c == 'C')
        return ((!b) || a);      //a→b 和 b→a完全不同，但因为用的栈，所以顺序为b→a
    if (c == 'E')
        return a == b;
}

bool pd (char str[])
{
    memset (z,0,sizeof (z));
    char *ps = &str[strlen(str) - 1];
    bool *sz = z;
    
    //构建栈
    while (ps >= str)
    {
        if (*ps == 'p' || *ps == 'q' || *ps == 'r' || *ps == 's' || *ps == 't')
        {
            *(sz++) = zh(*ps);
        }else if (*ps == 'K' || *ps == 'A' || *ps == 'C' || *ps == 'E')
        {
            *(sz - 2) = js (*(sz - 1),*(sz - 2),*ps);
            sz--;
        }else if (*ps == 'N')
        {
            *(sz - 1) = !*(sz - 1);
        }
        ps--;
    }
    if (sz > &z[1])  //确保栈已经空，不过这个题不用判断
        return 0;
    return z[0];
}
int main()
{
    //freopen ("1.txt","w",stdout);    //因为这个还WA了一回
    while (scanf ("%s",str),strcmp (str,"0"))
    {
        int tf = 1;
        for (p = 0;p < 2;p++)     //2^5直接枚举就好啦
        {
            for (q = 0;q < 2;q++)
            {
                for (r = 0;r < 2;r++)
                {
                    for (s = 0;s < 2;s++)
                    {
                        for (t = 0;t < 2;t++)
                        {
                            tf = pd (str);
                            if (!tf)
                                break;
                        }
                        if (!tf)
                            break;
                    }
                    if (!tf)
                        break;
                }
                if (!tf)
                    break;
            }
            if (!tf)
                break;
        }

        if (tf)
            puts ("tautology");
        else
            puts ("not");
    }
    return 0;
}

最后截张图留念一下