本文主要是介绍POJ 3295 Tautology（构造法 stack），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://poj.org/problem?id=3295
题意：给你一个逻辑表达式，让你判断是否是重言式
思路，对串进行解析，借助栈转求出所有情况的结果，一共是32种，枚举一遍！
代码：
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <stack>
using namespace std;
#define maxn 500
char str[maxn];
stack<char> sta;
map<char,bool> m;
int main(){int i,j,k,len;char p,q,r,s,t;char now,then;while(scanf("%s",str)!=EOF){if(str[0]=='0') break;len=strlen(str);m['0']=false;m['1']=true;for(k=0;k<32;k++){while(!sta.empty()) sta.pop();m['p']=m['q']=m['s']=m['r']=m['t']=false;if(k&1) m['p']=true;if(k&2) m['q']=true;if(k&4) m['r']=true;if(k&8) m['s']=true;if(k&16) m['t']=true;i=len-1;while(i>=0){while(str[i]>='a' && i>=0){sta.push(str[i]);i--;}if(i<0) break;if(str[i]=='K'){now=sta.top();sta.pop();then=sta.top();sta.pop();if(m[now] && m[then]) sta.push('1');else sta.push('0');}else if(str[i]=='A') {now=sta.top();sta.pop();then=sta.top();sta.pop();if(m[now] || m[then]) sta.push('1');else sta.push('0');}else if(str[i]=='N') {now=sta.top();sta.pop();if(m[now]) sta.push('0');else sta.push('1');}else if(str[i]=='E') {now=sta.top();sta.pop();then=sta.top();sta.pop();if(m[now] == m[then]) sta.push('1');else sta.push('0');}else if(str[i]=='C'){now=sta.top();sta.pop();then=sta.top();sta.pop();if(m[now]==false && m[then]==true) sta.push('0');else sta.push('1');}i--;}if(m[sta.top()]==false) break;}if(m[sta.top()]) printf("tautology\n");else printf("not\n");}return 0;
}
这篇关于POJ 3295 Tautology（构造法 stack）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
