POJ3295-Tautology【常规做法】

　　转载请注明出处：優YoU http://user.qzone.qq.com/289065406/blog/1309062835　　另这是使用STL的的做法：http://user.qzone.qq.com/289065406/blog/1309064454　　 　　大致题意：　　输进由p、q、r、s、t、K、A、N、C、E共10个字母组成的逻辑表达式，　　个中p、q、r、s、t的值为1（true）或0（false），即逻辑变量；　　K、A、N、C、E为逻辑运算符，　　K --> and: x && y　　A --> or: x || y　　N --> not : !x　　C --> implies : (!x)||y　　E --> equals : x==y　　问这个逻辑表达式是不是为永真式。　　PS:输进格式保证是正当的　　解题思路：　　p, q, r, s, t不同的取值组合共32种环境，罗列不同取值组合代进逻辑表达式WFF进行计算。　　假如对于全部的取值组合，WFF值都为 true, 则效果为 tautology，否则为 not。 　　WFF的计算方法：　　从字符串WFF的末端开始依次向前读取字符。　　构造一个栈stack，当碰到逻辑变量 p, q, r, s ,t 则将其当前的值压栈；　　碰到 N 则取栈顶元素进行非运算，运算效果的值压栈；　　碰到K, A, C, E则从栈顶中弹出两个元素进行相应的运算，将效果的值压栈。 　　由于输进是正当的，当字符串WFF扫描结束时，栈stack中只剩一个值，该值就是逻辑表达式WFF的值。　　//Memory Time　　//212K 79MS 　　 　　#include　　using namespace std;　　 　　int pp,qq,rr,ss,tt; //各个逻辑变量的值　　 　　typedef class STACK　　{　　 public:　　 int value;　　 class STACK* next;　　 STACK()　　 {　　 next=0;　　 }　　}Stack;　　 　　typedef class Top　　{　　 public:　　 Stack* top;　　 Top()　　 {　　 top=0;　　 }　　}linkstack;　　 　　void Insert(linkstack* s,int e); //进栈　　int Pop(linkstack* s); //栈顶值出栈　　void Empty(linkstack* s); //清空栈　　 　　bool isvariables(linkstack* s,char ch); //判定ch是不是为变量p q r s t，假如则把其当前值进栈　　void operators(linkstack* s,char op); //根据操纵符op对栈实行操纵　　int K(int x,int y); //and: x&&y　　int A(int x,int y); //or : x||y　　int C(int x,int y); //implies: (!x)||y　　int E(int x,int y); //equals: x==y　　int N(int x); //not: !x　　 　　int main(void)　　{　　 linkstack* s=new linkstack[sizeof(linkstack)];　　 　　 char WFF[110];　　 while(cin>>WFF && WFF[0]!='0')　　 {　　 int len=strlen(WFF); //逻辑表达式的长度　　 　　 bool flag=true; //标记逻辑表达式是不是为永真式　　 for(pp=0;pp<=1;pp++) //罗列逻辑变量的值　　 {　　 for(qq=0;qq<=1;qq++)　　 {　　 for(rr=0;rr<=1;rr++)　　 {　　 for(ss=0;ss<=1;ss++)　　 {　　 for(tt=0;tt<=1;tt++)　　 {　　 for(int pw=len-1;pw>=0;pw--)　　 {　　 if(!isvariables(s,WFF[pw]))　　 operators(s,WFF[pw]);　　 }　　 　　 int ans=s->top->value; //末了栈剩一个值，即为逻辑表达式的值　　 if(!ans) //只要表达式有一个值为假，它就不是永真式　　 {　　 flag=false;　　 break;　　 }　　 Empty(s);　　 }　　 if(!flag)　　 break;　　 }　　 if(!flag)　　 break;　　 }　　 if(!flag)　　 break;　　 }　　 if(!flag)　　 break;　　 }　　 if(flag)　　 cout<<"tautology"<value=e;　　 node->next=s->top;　　 s->top=node;　　 　　 return;　　}　　 　　int Pop(linkstack* s)　　{　　 int e=s->top->value;　　 Stack* temp=s->top;　　 s->top=s->top->next;　　 delete temp;　　 　　 return e;　　}　　 　　void Empty(linkstack* s)　　{　　 while(s->top)　　 {　　 Stack* temp=s->top;　　 s->top=s->top->next;　　 delete temp;　　 }　　 return;　　}　　 　　bool isvariables(linkstack* s,char ch)　　{　　 switch(ch)　　 {　　 case 'p':Insert(s,pp);return true;　　 case 'q':Insert(s,qq);return true;　　 case 'r':Insert(s,rr);return true;　　 case 's':Insert(s,ss);return true;　　 case 't':Insert(s,tt);return true;　　 }　　 return false;　　}　　 　　void operators(linkstack* s,char op)　　{　　 switch(op)　　 {　　 case 'K':　　 {　　 int x=Pop(s);　　 int y=Pop(s);　　 Insert(s,K(x,y));　　 break;　　 }　　 case 'A':　　 {　　 int x=Pop(s);　　 int y=Pop(s);　　 Insert(s,A(x,y));　　 break;　　 }　　 case 'C':　　 {　　 int x=Pop(s);　　 int y=Pop(s);　　 Insert(s,C(x,y));　　 break;　　 }　　 case 'E':　　 {　　 int x=Pop(s);　　 int y=Pop(s);　　 Insert(s,E(x,y));　　 break;　　 }　　 case 'N':　　 {　　 int x=Pop(s);　　 Insert(s,N(x));　　 break;　　 }　　 }　　 return;　　}　　 　　int K(int x,int y)　　{　　 return x&&y;　　}　　 　　int A(int x,int y)　　{　　 return x||y;　　}　　 　　int C(int x,int y)　　{　　 return (!x)||y;　　}　　 　　int E(int x,int y)　　{　　 return x==y;　　}　　 　　int N(int x)　　{　　 return !x;　　}

伤害

四级

感谢朋友,情人,家人