本文共 5144 字，大约阅读时间需要 17 分钟。
Tautology
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 14374 | Accepted: 5553 |
Description
WFF 'N PROOF is a logic game played with dice. Each die has six faces representing some subset of the possible symbols K, A, N, C, E, p, q, r, s, t. A Well-formed formula (WFF) is any string of these symbols obeying the following rules:
- p, q, r, s, and t are WFFs
- if w is a WFF, Nw is a WFF
- if w and x are WFFs, Kwx, Awx, Cwx, and Ewx are WFFs.
The meaning of a WFF is defined as follows:
- p, q, r, s, and t are logical variables that may take on the value 0 (false) or 1 (true).
- K, A, N, C, E mean and, or, not, implies, and equals as defined in the truth table below.
| Definitions of K, A, N, C, and E |
| w x | Kwx | Awx | Nw | Cwx | Ewx |
| 1 1 | 1 | 1 | 0 | 1 | 1 |
| 1 0 | 0 | 1 | 0 | 0 | 0 |
| 0 1 | 0 | 1 | 1 | 1 | 0 |
| 0 0 | 0 | 0 | 1 | 1 | 1 |
A tautology is a WFF that has value 1 (true) regardless of the values of its variables. For example, ApNp is a tautology because it is true regardless of the value of p. On the other hand, ApNq is not, because it has the value 0 for p=0, q=1.
You must determine whether or not a WFF is a tautology.
Input
Input consists of several test cases. Each test case is a single line containing a WFF with no more than 100 symbols. A line containing 0 follows the last case.
Output
For each test case, output a line containing tautology or not as appropriate.
Sample Input
ApNpApNq0
Sample Output
tautologynot
Source
, 2006.9.30
大致题意：
输入由p、q、r、s、t、K、A、N、C、E共10个字母组成的逻辑表达式WFF 其中 p、q、r、s、t的值为1（true）或0（false），即逻辑变量. K、A、N、C、E为逻辑运算符，含义如下： K --> and: w && x A --> or: w || x N --> not : !w C --> implies : (!w) || x E --> equals : w == x 问WFF是否为【永真式】 (大前提：【输入格式保证是合法的】)
解题思路：
从右边开始读入，如果是数就推入栈，如果是运算符就根据运算符取数出来运算
代码：
#include#include #include #include using namespace std;int P[]={0,1};int Q[]={0,1};int R[]={0,1};int S[]={0,1};int T[]={0,1};int main(){ char Z[110]; while(cin>>Z&&Z[0]!='0') { int len=strlen(Z); bool flag=true; for(int i1=0;i1<=1;i1++) { for(int i2=0;i2<=1;i2++) { for(int i3=0;i3<=1;i3++) { for(int i4=0;i4<=1;i4++) { for(int i5=0;i5<=1;i5++) { stack q; int m,n; for(int i=len-1;i>=0;i--) { if(Z[i]>='Z') { if(Z[i]=='p') { q.push(P[i1]+'0'); } if(Z[i]=='q') { q.push(Q[i2]+'0'); } if(Z[i]=='r') { q.push(R[i3]+'0'); } if(Z[i]=='s') { q.push(S[i4]+'0'); } if(Z[i]=='t') { q.push(T[i5]+'0'); } } if(Z[i]=='K') { m=q.top()-'0'; q.pop(); n=q.top()-'0'; q.pop(); q.push((m&&n)+'0'); } if(Z[i]=='A') { m=q.top()-'0'; q.pop(); n=q.top()-'0'; q.pop(); q.push((m||n)+'0'); } if(Z[i]=='N') { m=q.top()-'0'; q.pop(); q.push((!m)+'0'); } if(Z[i]=='C') { m=q.top()-'0'; q.pop(); n=q.top()-'0'; q.pop(); q.push(((!m)||n)+'0'); } if(Z[i]=='E') { m=q.top()-'0'; q.pop(); n=q.top()-'0'; q.pop(); q.push(m==n?'1':'0'); } } if(!(q.top()-'0')) { flag=false; goto L; } } } } } } L: if(flag) { cout<<"tautology"<
另一种方法：
#include#include #include #include #include using namespace std;const int MAXX=110;//string str;int p,q,r,s,t;int stra[MAXX];//用来表示堆栈char str[MAXX];void First(){ int cns=0; int len = strlen(str); int t1=0,t2=0; for(int i=len-1;i>=0;i--) { if(str[i]=='p') stra[cns++]=p; else if(str[i]=='q') stra[cns++]=q; else if(str[i]=='r') stra[cns++]=r; else if(str[i]=='s') stra[cns++]=s; else if(str[i]=='t') stra[cns++]=t; else if(str[i]=='K') { t1=stra[--cns]; t2=stra[--cns]; stra[cns++]=(t1&&t2); } else if(str[i]=='A') { t1=stra[--cns]; t2=stra[--cns]; stra[cns++]=(t1||t2); } else if(str[i]=='N') { t1=stra[--cns]; stra[cns++]=(!t1); } else if(str[i]=='C') { t1=stra[--cns]; t2=stra[--cns]; stra[cns++]=((!t1)||t2); } else if(str[i]=='E') { t1=stra[--cns]; t2=stra[--cns]; stra[cns++]=(t1==t2); } }}bool salve(){ 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++) { First(); if(stra[0]==0) return false; } return true;}int main(){ while(scanf("%s",&str)) { if(strcmp(str,"0")==0) break; if(salve()) cout<<"tautology"<
转载地址：https://joycez.blog.csdn.net/article/details/82779633 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
