POJ 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
问这个逻辑表达式是否为永真式。
PS:输入格式保证是合法的

代码如下

//3295
//Tautology

#include<iostream>
#include<stack>
#include<bitset>


using namespace std;

const string Variables = "pqrst";
const string Operators = "KANCE";


//掩码
const short Mask_p = 1;
const short Mask_q = 2;
const short Mask_r = 4;
const short Mask_s = 8;
const short Mask_t = 16;

bool calculate( stack<bool> &operands, char operation )
{
    bool ans, op1, op2;

    op1 = operands.top();
    operands.pop();

    //单目运算
    if( operation == 'N' ){
        ans = !op1;
        //cout << op1 << operation << endl; //test
    }
    else{   //双目运算
        op2 = operands.top();
        operands.pop();

        switch( operation ) {
            case 'K':
                ans = op1 && op2;
                break;
            case 'A':
                ans = op1 || op2;
                break;
            case 'C':
                ans = (!op2) || op1;
                break;
            case 'E':
                ans = op1 == op2;
                break;
        }

        //cout << op1 << operation << op2 << endl;  //test
    }

    operands.push(ans);

    return ans;
}


bool changeToBool( short vars, char var )
{
    bool ans;

    switch( var ){
        case 'p':
            ans = vars & Mask_p;
            break;
        case 'q':
            ans = vars & Mask_q;
            break;
        case 'r':
            ans = vars & Mask_r;
            break;
        case 's':
            ans = vars & Mask_s;
            break;
        case 't':
            ans = vars & Mask_t;
            break;
    }

    return ans;
}


int main()
{
    const short range = 0x1f;
    short vars = 0;
    stack<bool> operands;

    string formula;


    while( cin >> formula, formula != "0" ){

        for( vars = 0;  vars <= range;  vars++ ){
            //cout<< vars << " = " << bitset<sizeof(short)*8>(vars)  << endl;   //test
            for( string::reverse_iterator c = formula.rbegin();  c != formula.rend();  c++ ){   //注意c的类型
                if( Variables.find(*c) != string::npos ){
                    operands.push( changeToBool(vars, *c) );
                }else{
                    calculate( operands, *c );  
                }
            }

            if( operands.top() == false ){
                cout << "not" << endl;
                break;
            }

        }

        if( operands.top() == true )
            cout << "tautology" << endl;

        while( !operands.empty() )  //清空栈
            operands.pop();
    
    }

    return 0;
}

注意

• 使用了string::reverse_iterator
• 首先审题，注意题目是只输入单个数据就结束还是循环输入
• 分别处理好程序正确与错误的结束方式
• 不好搞混变量，分析最有可能出错的地方

这题的考点我觉得主要是位操作和前缀表达式的运行。而对于前缀表达式运算，上面的方法是自底而上的思想，还可以用递归的方式进行自顶向下的运算。

//3295
//Tautology
//递归求解

#include<iostream>
#include<stack>
#include<bitset>


using namespace std;

const string Variables = "pqrst";
const string Operators = "KANCE";


//掩码
const short Mask_p = 1;
const short Mask_q = 2;
const short Mask_r = 4;
const short Mask_s = 8;
const short Mask_t = 16;


int cnt = -1;   
bool step( string formula, short vars )
{
    bool ans;
    cnt++;  //必须放在前面

    switch( formula[cnt] ){
        case 'p':
            ans = vars & Mask_p;
            break;
        case 'q':
            ans = vars & Mask_q;
            break;
        case 'r':
            ans = vars & Mask_r;
            break;
        case 's':
            ans = vars & Mask_s;
            break;
        case 't':
            ans = vars & Mask_t;
            break;
        case 'N':
            ans = !step(formula, vars);
            break;
        case 'K':
            //只能是&而不能是&&，因为&&有短路特性，可能会跳过第二个step
            ans = step(formula, vars) & step(formula, vars);
            break;
        case 'A':
            ans = step(formula, vars) | step(formula, vars);
            break;
        case 'C':
            ans = ( !step(formula, vars) )  |  step(formula, vars);
            break;
        case 'E':
            ans = step(formula, vars) == step(formula, vars);
            break;
            
    }

    return ans;
}

int main()
{
    const short range = 0x1f;
    short vars = 0;
    bool ans;

    string formula;


    while( cin >> formula, formula != "0" ){

        //cout << formula << endl;  //test
        for( vars = 0;  vars <= range;  vars++ ){

            cnt = -1;
            ans = step( formula, vars );

            if( ans == false ){
                cout << "not" << endl;
                break;
            }
        }

        if( ans == true )
            cout << "tautology" << endl;

    }


    return 0;
}

POJ 3295

原文：https://www.cnblogs.com/friedCoder/p/12263370.html