| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 10897 | Accepted: 4136 |
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.
| 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 |
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
|
1 2 3 |
ApNp ApNq 0 |
Sample Output
|
1 2 |
tautology not |
Source
这道题目我一开始读了半天还没读懂，后来请教了一位英文好的同学才弄懂了（还是学文的。。。），其实这道题就是离散数学里面的前缀表达式，输入由p、q、r、s、t、K、A、N、C、E共十个字母组成的逻辑表达式，其中p、q、r、s、t的值为1或者0，即逻辑变量； K、A、N、C、E为逻辑运算符， K-> and: x&&y A-> or: x||y N-> not: !x C-> implies： （!x)||y E-> equals: x==y 然后求在输入格式保证合法的前提下问逻辑表达式是否为永真式。
我的解法是直接暴力p,q,r,s,t不同的取值总共32种情况，然后用数组模拟堆栈。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
/************************************************************************* > File Name: 3295.cpp > Author: razrLeLe > Personal homepage: https://razrLeLe.com > Created Time: Mon 21 Jul 2014 06:01:44 PM CST ************************************************************************/ #include<iostream> using namespace std; #include <string.h> int a[100]; char o[100]; int main() { int p, q, r, s, t; int x, y, k, l; while(cin >> o) { bool mark = true; l = strlen(o); if(o[0] == '0') return 0; 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++) { k = 0; for(int i = l-1; i >= 0; i--) { if(o[i] == 'p') a[k++] = p; else if(o[i] == 'q') a[k++] = q; else if(o[i] == 'r') a[k++] = r; else if(o[i] == 's') a[k++] = s; else if(o[i] == 't') a[k++] = t; else if(o[i] == 'N') { x = a[--k]; x = (!x); a[k++] = x; } else{ x = a[--k]; y = a[--k]; } if(o[i] == 'K') a[k++] = (x&&y); else if(o[i] == 'A') a[k++] = (x||y); else if(o[i] == 'C') a[k++] = ((!x)||y); else if(o[i] == 'E') a[k++] = (x==y?1:0); } if(a[0] == 0) mark = false; } if(mark) cout << "tautology" << endl; else cout << "not" << endl; } return 0; } |
其实就是从右往左如果逻辑变量就压栈，如果是逻辑运算符就出栈两个逻辑变量然后把运算结果压栈。
但是这个题其实应该用递归做的，我在网上找了一段代码，简直不能更赞。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <csdtio> char str[105]; int current; int judge(int i) { char ch = str[current++]; if(ch=='p' || ch=='q'|| ch=='r' || ch=='s' || ch=='t') return (i>>(ch-'p'))&1; else if(ch=='K') return judge(i) & judge(i); else if(ch=='A') return judge(i) | judge(i); else if(ch=='N') return !judge(i); else if(ch=='C') return (!judge(i)) | judge(i); else if(ch=='E') return judge(i) == judge(i); else return 0; } int main() { int flag; while(scanf("%s",str)==1 && str[0]!='0') { flag = 1; for(int i=0; i<32; i++) { current = 0; if(!judge(i)) { flag = 0; break; } } if(flag) printf("tautologyn"); else printf("notn"); } return 0; } |
这里把五个逻辑变量看成五个二进制数，五个二进制数总共32种情况，然后再用位运算符。我的代码跑了16ms，这个在OJ上面显示的是0ms，思路清晰，要好好学习。