poj3295：Tautology

传送门

题目大意

给定一个由10种字符(p,q,r,s,t,N,K,A,C,E)组成的逻辑表达式，其中pqrst为逻辑变量，NKACE为逻辑运算符，他们的含义分别是

• K==and：x && y
• N==not：!x
• A==or：x || y
• C==implies：(!x)||y
• E==equals：x==y

要求判断这个逻辑表达式是否为重言式，如果是就输出tautology，否则输出not

思路

根据题设，我们不难判断，单目运算符一定在整个字符串的后半部分，双目运算符一定在整个字符串的前半部分。例如ApNp，它应该被判为A(p,N(p))，所以上述结论的正确性是显然的。那么就可以像常规的表达式计算一样，从尾部压入栈，然后弹一个计算一个。

因为只有5个逻辑变量，所以最多只会有2^5=32种情况，依次枚举就好。

代码

我的写法

五重循环枚举每一位，最内层去枚举长度。

#include <stack>
#include <vector>
#include <cstdio>
#include <iostream>

using namespace std;

string str;

bool input(stack<int>& sta, char ss, int p, int q, int r, int s, int t) {
	switch(ss) {
		case 'p' : sta.push(p); return true;
		case 'q' : sta.push(q); return true;
		case 'r' : sta.push(r); return true;
		case 's' : sta.push(s); return true;
		case 't' : sta.push(t); return true;
	}

	return false;
}

void operated(stack<int>& sta, char ss) {
	int a, b;
	switch(ss) {
		case 'K' : {
			a = sta.top();sta.pop();
			b = sta.top();sta.pop();
			sta.push(a && b);
			break;
		}
		case 'N' : {
			a = sta.top();sta.pop();
			sta.push(!a);
			break;
		}
		case 'A' : {
			a = sta.top();sta.pop();
			b = sta.top();sta.pop();
			sta.push(a || b);
			break;
		}
		case 'E' : {
			a = sta.top();sta.pop();
			b = sta.top();sta.pop();
			sta.push(a == b);
			break;
		}
		case 'C' : {
			a = sta.top();sta.pop();
			b = sta.top();sta.pop();
			sta.push(!a || b);
			break;
		}
	}
}

int main() {
	while(cin >> str) {
		if(str[0] == '0') break;
		int len = str.length();
		stack<int> sta;

		bool flag = 1;
		for(int p = 0; p <= 1; p++) {
			for(int q = 0; q <= 1; q++) {
				for(int r = 0; r <= 1; r++) {
					for(int s = 0; s <= 1; s++) {
						for(int t = 0; t <= 1; t++) {
							for(int l = len; l >= 0; l--) {//倒叙读入 
								if(!input(sta, str[l], p, q, r, s, t)) {
									//如果当前字符不是变量，就根据运算符计算 
									operated(sta, str[l]);
								}
							}
							//只要出现真值为0的项就可以退出了 
							if(!sta.top()) {flag = 0; break;}
						}
						if(!flag) break;
					}
					if(!flag) break;
				}
				if(!flag) break;
			}
			if(!flag) break;
		}

		flag ? cout << "tautology\n" : cout << "not\n";
	}

	return 0;
}

另外一种写法

在网上冲浪的时候看到了另一种用位运算来枚举的写法，属实高级且优雅，但碍于本人稀烂的位运算水平，只能在此贴出代码，日后水平渐长才能尝试读懂。

//来源：https://www.cnblogs.com/shenben/p/5646335.html
#include<iostream>
using namespace std;
int cnt;
char str[101];
bool step(char str[101],int tk){
    cnt++;
    switch(str[cnt]){
        case 'p':return tk&1;
        case 'q':return(tk>>1)&1;
        case 'r':return(tk>>2)&1;
        case 's':return(tk>>3)&1;
        case 't':return(tk>>4)&1;
        case 'N':return !step(str,tk);
        case 'K':return step(str,tk)&step(str,tk);
        case 'A':return step(str,tk)|step(str,tk);
        case 'C':return !step(str,tk)|step(str,tk);
        case 'E':return step(str,tk)==step(str,tk);
    }
}
bool judge(char str[101]){
    for(int i=0;i<32;i++){
        cnt=-1;
        if(!step(str,i)) return 0;    
    }
    return 1;
}
int main(){
    while(cin>>str){   
        if(str[0]=='0') break;
        if(judge(str))
            cout<<"tautology"<<endl;
        else
            cout<<"not"<<endl;
    }
    return 0;
}