大致题意: 输入由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 --> : x && y A --> : 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的值。 #include<stdio.h> #include<stack> #include<iostream> #include<cstring> #define N 1000 using namespace std; stack<int>s; int pp,qq,rr,tt,ss; int kmp(char c) { switch(c) { case 'p':s.push(pp);return 1; case 'q':s.push(qq);return 1; case 'r':s.push(rr);return 1; case 's':s.push(ss);return 1; case 't':s.push(tt);return 1; default: return 0; } } void ope(char c) { switch(c) { case 'K': { int x=s.top(); s.pop(); int y=s.top(); s.pop(); s.push(x&&y); break; } case 'A': { int x=s.top(); s.pop(); int y=s.top(); s.pop(); s.push(x||y); break; } case 'C': { int x=s.top(); s.pop(); int y=s.top(); s.pop(); s.push((!x)||y); break; } case 'E': { int x=s.top(); s.pop(); int y=s.top(); s.pop(); s.push(x==y); break; } case 'N': { int x=s.top(); s.pop(); s.push(!x); break; } } } int main() { char WFF[N]; int i; while(cin>>WFF&&WFF[0]!='0') { int len=strlen(WFF); int flag=1; 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(i=len-1;i>=0;i--)//从尾往前入站 { if(!kmp(WFF[i])) { ope(WFF[i]); } } int ans=s.top(); s.pop(); if(!ans){flag=0;break;} } if(!flag)break; } if(!flag)break; } if(!flag)break; } if(!flag)break; } if(!flag)printf("not\n"); else printf("tautology\n"); } }