题解 P1575 【正误问题】

ykkz000 · 2018-12-18 15:32:00 · 题解

这道题的与、或都是二元运算符，只有not是一元运算符，故特判not，其余的可以同普通表达式一样地运算

#include<bits/stdc++.h>
using namespace std;
//手写模板栈
template<typename _Type>
class q_stack{
    #define MAX_SIZE 1024
    private:
        _Type m_stack[MAX_SIZE];
        int m_top;
    public:
        q_stack(){
            m_top=0;
        }
        //入栈
        bool push(_Type element){
            if(m_top==MAX_SIZE) return true;
            m_stack[m_top++]=element;
            return false;
        }
        //出栈(返回值为是否下溢)
        bool pop(){
            if(m_top==0) return true;
            --m_top;
            return false;
        }
        //取栈顶
        bool top(_Type &element){
            if(m_top==0) return true;
            element=m_stack[m_top-1];
            return false;
        }
        //判断是否为空
        bool empty(){
            return m_top==0;
        }
};
int main(){
    //优先级表not>and>or，同时也是id表
    map<string,int> perious;
    perious["or"]=1;
    perious["and"]=2;
    perious["not"]=3;
    q_stack<bool> value; //操作数栈
    q_stack<int> operate; //操作符栈
    operate.push(0); //压入虚拟操作符，优先级最低
    string tmp;
    int pre=1; //上一个读入类型，1：操作符，2：操作数
    bool error=false; //是否有误
    bool no=false;  //当前是否还有not
    while(cin>>tmp){
        if(error) continue; //出错就不再运算
        else if(tmp=="true"){
            if(pre==0) error=true;
            else{
                if(!no) value.push(true);
                else value.push(false);
                no=false;
                pre=0;
            }
        }
        else if(tmp=="false"){
            if(pre==0) error=true;
            else{
                if(!no) value.push(false);
                else value.push(true);
                no=false;
                pre=0;
            }
        }
        else{  //若读入运算符
            int op=perious[tmp];
            //特判not
            if(pre==1&&op!=3) error=true;
            if(pre==0&&op==3) error=true;
            if(op==3) no=true;
            int f; //上一个操作符id
            operate.top(f);
            while(op<f){
                operate.pop();
                bool op1,op2;
                switch(f){
                    case 1:{ //或
                        value.top(op1);
                        value.pop();
                        value.top(op2);
                        value.pop();
                        value.push(op1||op2); //答案入栈
                        break;
                    }
                    case 2:{ //与
                        value.top(op1);
                        value.pop();
                        value.top(op2);
                        value.pop();
                        value.push(op1&&op2);
                        break;
                    }
                }
                operate.top(f);
            }
            if(op!=3) operate.push(op); //若读入的是不是not，压栈
            pre=1;
        }
    }
    if(no) error=true; //not后无操作数，即表达式不正确
    int f;
    //下面循环弹出操作符和操作数，并将当前结果压入操作数栈
    operate.top(f);
    while(f>0&&(!error)){
        operate.pop();
        bool op1,op2;
        switch(f){
            case 1:{
                value.top(op1);
                value.pop();
                value.top(op2);
                value.pop();
                value.push(op1||op2);
                break;
            }
            case 2:{
                value.top(op1);
                value.pop();
                value.top(op2);
                value.pop();
                value.push(op1&&op2);
                break;
            }
        }
        operate.top(f);
    }
    bool ans;
    //操作数栈中最后剩的便是答案
    value.top(ans);
    //...
    if(error) cout<<"error";
    else if(ans) cout<<"true";
    else cout<<"false";
    return 0;
}