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 WFFsif w is a WFF, Nw is a WFFif 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
ApNp ApNq 0Sample Output
tautology not 1 //类似于后缀式求值； 2 3 #include<stdio.h> 4 #include<string.h> 5 #include<stack> 6 using namespace std; 7 8 char ss[101]; 9 stack <int> st; 10 int flag; 11 12 void check(int p, int q, int r, int s,int t) 13 { 14 while(!st.empty()) 15 st.pop(); 16 int a,b; 17 int len = strlen(ss); 18 for(int i = len-1; i >= 0; i--) 19 { 20 if(ss[i] == 'p') 21 st.push(p); 22 else if(ss[i] == 'q') 23 st.push(q); 24 else if(ss[i] == 'r') 25 st.push(r); 26 else if(ss[i] == 's') 27 st.push(s); 28 else if(ss[i] == 't') 29 st.push(t); 30 else if(ss[i] == 'K') 31 { 32 a = st.top(); 33 st.pop(); 34 b = st.top(); 35 st.pop(); 36 if(a == 1 && b == 1) 37 st.push(1); 38 else st.push(0); 39 } 40 else if(ss[i] == 'A') 41 { 42 a = st.top(); 43 st.pop(); 44 b = st.top(); 45 st.pop(); 46 if(a == 0 && b == 0) 47 st.push(0); 48 else st.push(1); 49 } 50 else if(ss[i] == 'N') 51 { 52 a = st.top(); 53 st.pop(); 54 if(a == 1) 55 st.push(0); 56 else st.push(1); 57 } 58 else if(ss[i] == 'C') 59 { 60 a = st.top(); 61 st.pop(); 62 b = st.top(); 63 st.pop(); 64 if(a == 0 && b == 1) 65 st.push(0); 66 else st.push(1); 67 } 68 else if(ss[i] == 'E') 69 { 70 a = st.top(); 71 st.pop(); 72 b = st.top(); 73 st.pop(); 74 st.push((a && b) || (!a && !b)); 75 } 76 } 77 if(st.top() != 1) 78 flag = 0; 79 } 80 int main() 81 { 82 while(~scanf("%s",ss)) 83 { 84 flag = 1; 85 if(strcmp("0",ss) == 0) 86 break; 87 for(int p = 0; p < 2; p++) 88 for(int q = 0; q < 2; q++) 89 for(int r = 0; r < 2; r++) 90 for(int s = 0; s < 2; s++) 91 for(int t = 0; t < 2; t++) 92 check(p, q, r, s, t); 93 if(flag == 1) 94 printf("tautology\n"); 95 else printf("not\n"); 96 } 97 return 0; 98 } View Code
转载于:https://www.cnblogs.com/LK1994/p/3240539.html
相关资源：JAVA上百实例源码以及开源项目