ACM学习历程——POJ3295 Tautology（搜索，二叉树）-白红宇

ACM学习历程——POJ3295 Tautology（搜索，二叉树）

阅读量：4317 次

发布时间：2019-06-06

本文共 3240 字，大约阅读时间需要 10 分钟。

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 考虑到运算符最多是二元的，将运算符和变量存进二叉树中，结构体中用一个val值来记录是否是变量，为了提高效率，用一个visit数组来记录用到了哪几个变量。此外在最后进行运算的时候，需要二叉树进行后序遍历。此外输入采用先序遍历。 代码：

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #include 
                
                 #include 
                 
                  #define inf 0x3fffffff#define eps 1e-10using namespace std;struct node{ char op; int val; node *left; node *right;};bool a[5];bool visit[5];int Do(char op, int x, int y){ switch (op) { case 'K': return x&&y; case 'A': return x||y; case 'N': return !x; case 'C': return !x || y; case 'E': return x == y; }}bool Input(node *p){ char ch; ch = getchar(); if (ch == '0') return 0; p->op = ch; p->val = -1; switch (ch) { case 'p': p->val = 0; visit[0] = 1; return 1; case 'q': p->val = 1; visit[1] = 1; return 1; case 'r': p->val = 2; visit[2] = 1; return 1; case 's': p->val = 3; visit[3] = 1; return 1; case 't': p->val = 4; visit[4] = 1; return 1; case 'N': p->left = (node *)malloc(sizeof(node)); return Input(p->left); default: p->left = (node *)malloc(sizeof(node)); p->right = (node *)malloc(sizeof(node)); Input(p->left); return Input(p->right); }}bool caculate(node *p){ if (p->val != -1) return a[p->val]; if (p->op == 'N') return Do(p->op, caculate(p->left), 1); else return Do(p->op, caculate(p->left), caculate(p->right));}bool dfs(int now, node *head){ if (now == 5) return caculate(head); if (visit[now] == 0) return dfs(now+1, head); int ii, jj; a[now] = 0; ii = dfs(now+1, head); a[now] = 1; jj = dfs(now+1, head); return ii && jj;}bool qt(node *head){ if (dfs(0, head)) printf("tautology\n"); else printf("not\n");}int main(){ //freopen("test.txt", "r", stdin); node *head; for (;;) { memset(visit, 0, sizeof(visit)); head = (node *)malloc(sizeof(node)); if(!Input(head)) break; getchar(); qt(head); } return 0;}

转载于:https://www.cnblogs.com/andyqsmart/p/4111419.html

你可能感兴趣的文章