poj 3295 tautology

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

模拟了一下：

#include<iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include<stdlib.h>
#include <string.h>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<time.h>
using namespace std;
#define MAX_N 105
#define inf 0x7fffffff
#define LL long long
#define ull unsigned long long
const LL INF = 9e18;
const int mod = 100000000;
typedef pair<double, double>P;

char S[MAX_N];
stack<char>ope, c;
map<char, int>mp;
int p, q, r, s, t;
int len;
void init()
{
    mp['p'] = p;
    mp['q'] = q;
    mp['r'] = r;
    mp['s'] = s;
    mp['t'] = t;
}
int find(int left, int right)
{
    if(S[left]>='a' && S[left]<='z')
        return left;
    int sum;
    if(S[left] == 'N')
        sum = 1;
    else
        sum = 2;
    for(int i=left+1;i<=right;i++) {
        if(S[i]>='a' && S[i]<='z')
            sum--;
        else if(S[i]!='N')
            sum++;
        if(!sum)
            return i;
    }
    return right;
}
bool dfs(int left, int right)
{
    if(right == left) {
        return mp[S[left]];
    }
    if(S[left] == 'N') {
        return !dfs(left+1, right);
    }
    else {
        if(S[left] <= 'z' && S[left] >= 'a') {
            return mp[S[left]];
        }
        else if(S[left] == 'K') {
            int mid = find(left+1, right);
            return dfs(left+1, mid) & dfs(mid+1, right);
        }
        else if(S[left] == 'A') {
            int mid = find(left+1, right);
            return dfs(left+1, mid) | dfs(mid+1, right);
        }
        else if(S[left] == 'C') {
            int mid = find(left+1, right);
            return (!dfs(left+1, mid)) | dfs(mid+1, right);
        }
        else if(S[left] == 'E') {
            int mid = find(left+1, right);
            return dfs(left+1, mid) == dfs(mid+1, right);
        }
    }
}
bool check()
{
    for(p=0;p<2;p++) {
        for(q=0;q<2;q++) {
            for(r=0;r<2;r++) {
                for(s=0;s<2;s++) {
                    for(t=0;t<2;t++) {
                        init();
                        if(!dfs(0, len-1)) {
                            return false;
                        }
                    }
                }
            }
        }
    }
    return true;
}
int main()
{
    while(scanf("%s",S)) {
        if(S[0] == '0')
            break;
        len = strlen(S);
        if(check())
            printf("tautologyn");
        else
            printf("notn");
    }
}

评论区里看到的一个简洁递归：

#include<iostream>
#include<cstring>
#include<cassert>

using namespace std;

string s;int cur;char a[5];

void Change(char i)//穷举时改变数组用的函数
{
    for(int j=0;j!=5;j++)
        a[j]=((i>>j)&00000001);
}
bool Cal()//递归
{
    char c=s[cur];bool w,x;
    cur++;
    switch(c){
    case 'p':return a[0];
    case 'q':return a[1];
    case 'r':return a[2];
    case 's':return a[3];
    case 't':return a[4];
    case 'N':return !Cal();
    case 'K':w=Cal();x=Cal();return (w&&x);
    case 'A':w=Cal();x=Cal();return (w||x);
    case 'C':w=Cal();x=Cal();return (w<=x);
    case 'E':w=Cal();x=Cal();return (w==x);
    default :return 0;
    }
}
int main()
{
    int f;
    while(1)
    {
        cin>>s;
        if(s=="0")  break;
        f=1;
        for(char i=0;i!=32;i++)
        {
            cur=0;Change(i);
            if(!Cal()) {f=0;break;}
        }
        if(f==1) cout<<"tautology"<<endl;
        else cout<<"not"<<endl;

    }
    return 0;
}