首页 > 代码库 > Poj3295 tautology

Poj3295 tautology

大致题意:

输入由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

问这个逻辑表达式是否为永真式。

PS:输入格式保证是合法的

 

解题思路:

p, q, r, s, t不同的取值组合共32种情况,枚举不同取值组合代入逻辑表达式WFF进行计算。

如果对于所有的取值组合,WFF值都为 true, 则结果为 tautology,否则为 not。 
  

WFF的计算方法:

从字符串WFF的末尾开始依次向前读取字符。

构造一个栈stack,当遇到逻辑变量 p, q, r, s ,t 则将其当前的值压栈;

遇到 N 则取栈顶元素进行非运算,运算结果的值压栈;

遇到K, A, C, E则从栈顶中弹出两个元素进行相应的运算,将结果的值压栈。 

由于输入是合法的,当字符串WFF扫描结束时,栈stack中只剩一个值,该值就是逻辑表达式WFF的值。

 

 

栈可以自己构造,也可以利用STL的<stack>,都一样,

#include<string>
#include<iostream>
#include<stack>

using namespace std;
int main()
{
    string s;
    int len;
    int d, i;
    bool dgt[5], op1, op2, flag;

    stack<bool>st;

    while (cin >> s&&s[0] != 0)
    {
        len = s.length();
        flag = true;
        for (d = 0; d < 32; d++)      //每个变量有0或者1两种,一共五个变量有32种可能
        {
            //对每一种可能的情况进行遍历

            for (i = 0; i < 5; i++)   //五个变量:p,q,r,s,t
            {
                if (d & 1 << i)
                {
                    dgt[i] = true;
                }
                else
                {
                    dgt[i] = false;
                }
            }
            for (i = len - 1; i >= 0;i--)   //从尾遍历string s这个字符串数组
            {
                switch (s[i])
                {
                case p:
                case q:
                case r:
                case s:
                case t:
                    st.push(dgt[s[i] - p]);//入栈。dgt[s[i] - ‘p‘]??
                    break;
                case K:
                    op1 = st.top(); st.pop();
                    op2 = st.top(); st.pop();
                    st.push(op1&&op2);
                    break;
                case A:
                    op1 = st.top(); st.pop();
                    op2 = st.top(); st.pop();
                    st.push(op1 || op2);
                    break;
                case N:
                    op1 = st.top(); st.pop();
                    st.push(!op1);
                    break;
                case C:
                    op1 = st.top(); st.pop();
                    op2 = st.top(); st.pop();
                    st.push(!op1 || op2);
                    break;
                case E:
                    op1 = st.top(); st.pop();
                    op2 = st.top(); st.pop();
                    st.push(op1 == op2);
                    break;

                }
            }
            //必须所有的op1是1才能算tautology,否则跳出循环,输出not
            op1 = st.top(); st.pop();
            if (!op1)
            {
                flag = false;
                break;
            }
        }
        if (flag)
        {
            cout << "tautology" << endl;
        }
        else
        {
            cout << "not" << endl;
        }
    }
}

 

Poj3295 tautology