首页 > 代码库 > poj3295解题报告（构造、算术表达式运算）

poj3295解题报告（构造、算术表达式运算）

2024-07-06 20:22:30   227人阅读

 

POJ 3952，题目链接http://poj.org/problem?id=3295

题意：

输入由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 --> and:  x && y

A --> or:  x || y

N --> not :  !x

C --> implies :  (!x)||y

E --> equals :  x==y

输入格式保证是合法的，问这个逻辑表达式是否为永真式。

思路：

1. 从输入字符串末尾向前读取字符，构造一个栈，遇到pqrst则入栈，遇到N则取出栈顶一个值计算后入栈，遇到KACE则取栈顶两个值计算后入栈。最后栈内将只剩一个值，即该表达式的值。（与用栈计算算术表达式的方式一样）

2. 一个5个逻辑变量，每种情况都要考虑，那么一共2^5（0x1f）种情况。

代码：

?
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
//560K  0MS
 
#include <cstdio>
#include <cstring>
#include <stack>
using std::stack;
 
//K, A, N, C, E //逻辑符号
//p, q, r, s, t //bool值
char buf[101];
stack<bool> s_stack;
bool data[5]={false};
bool WFF(char* str, int val)
{
    //init p q r s t
    for (int i=0; i<5; ++i){
        data[i] = (1<<i) & val;
    }
 
    while (! s_stack.empty()) s_stack.pop();
    int strLen = strlen(str);
    bool a,b;
    while (--strLen >= 0)
    {
        switch (buf[strLen])
        {
        case ‘p‘:
            s_stack.push(data[0]);
            break;
        case ‘q‘:
            s_stack.push(data[1]);
            break;
        case ‘r‘:
            s_stack.push(data[2]);
            break;
        case ‘s‘:
            s_stack.push(data[3]);
            break;
        case ‘t‘:
            s_stack.push(data[4]);
            break;
        case ‘K‘:
            a=s_stack.top(); s_stack.pop();
            b=s_stack.top(); s_stack.pop();
            s_stack.push(a && b);
            break;
        case ‘A‘:
            a=s_stack.top(); s_stack.pop();
            b=s_stack.top(); s_stack.pop();
            s_stack.push(a || b);
            break;
        case ‘N‘:
            a=s_stack.top(); s_stack.pop();
            s_stack.push(!a);
            break;
        case ‘C‘:
            a=s_stack.top(); s_stack.pop();
            b=s_stack.top(); s_stack.pop();
            s_stack.push(!a || b);
            break;
        case ‘E‘:
            a=s_stack.top(); s_stack.pop();
            b=s_stack.top(); s_stack.pop();
            s_stack.push(a == b);
            break;
        default:
            break;
        }
    }
    return s_stack.top();
}
 
int main()
{
    while (true)
    {
        memset(buf, 0, sizeof(char)*101);
        scanf("%s", buf);
        if (strcmp(buf, "0") == 0) break;
 
        bool tautology = true;
        for (int val=0; val<=0x1f; ++val)
        {
            if (! WFF(buf, val)){
                tautology = false;
                break;
            }
        }
 
        if (tautology){
            printf("tautology\n");
        }else {
            printf("not\n");
        }
    }
 
    return 0;
}

 


联系
我们