P1575 题解

· · 题解

注意：这是一篇 C++ 题解。

题目传送门

题意：

给定一个逻辑表达式，包含 \verb!true!、\verb!false!、\verb!not!、\verb!and!、\verb!or! 和空格。

如果该表达式错误，输出 \verb!error!，否则输出结果（\verb!true! 或 \verb!false!）。

前文：

有难度的模拟题，卡了我两天。

逻辑表达式翻译：

第一眼看到题目，觉得可以直接用字符串模拟，于是就有了下面的提交记录：交了几十次WA。

然后就是不断的 \verb!Debug!，在各位大佬的帮助下调了近两天才勉强通过，在调试过程中发现题解区缺少模拟做法的 \verb!C++! 题解，故写篇题解以补全空缺。

正文：

首先可以看到：

优先级从高到低依次为 \verb!not!，\verb!and!，\verb!or!。

所以我们可以先把所有的 \verb!not! 处理掉，然后依次处理 \verb!and! 和 \verb!or!。

可以从头遍历字符串，找到一段连续的 \verb!not!，然后将 \verb!not! 从字符串中删除。（可以把这段字符串赋值成空格，也可以使用 \operatorname{erase} 函数。）

最后判断 \verb!not! 数量的奇偶性，如果为偶数，后面的值不变，否则就变成相反的值，然后继续寻找下一处 \verb!not!。

从头遍历字符串，找到 \verb!and! 后判断前后是否合法，然后进行计算即可（前后为真返回真，否则返回假）。

和 \verb!and! 的操作方法类似，具体实现细节见代码中。

  4. 在计算过程中逻辑表达式中出现多个 \verb!true! 或 \verb!false! 且没有出现运算符（例如：\verb!true false!）。
  5. 逻辑表达式中只有运算符（例如：\verb!not not!）。

输入可能有多余空格，计算过程中也可能会产生多余空格，所以我们在一开始及每次运算结束时进行去除多余空格，细节见代码。

code：

超长代码预警！！！

#include <bits/stdc++.h>
using namespace std;
string s;
int l;
string trim(string& str){
    str.erase(0, str.find_first_not_of(" \t")); // 去掉头部空格
    str.erase(str.find_last_not_of(" \t") + 1); // 去掉尾部空格
    return str;
}
void kongge(){
    char st[305]="";
    s=trim(s);
    int len=s.length();
    bool fl=1;
    int cnt=0;
    for(int i=0;i<len;i++){
        if(s[i] == ' '){
            if(!fl){
                st[cnt++]=s[i];
                fl=1;
            }
        }
        else{
            fl=0;
            st[cnt++]=s[i];
        }
    }
    s=st;
    s+=" ";     //不加的话再循环中会越界 
    return ;
}
bool check1(int i){     //判断 and 前后是否合法 
    int t=i;
    char c[305]="";
    int cnt=0;
    i-=2;
    while(s[i] != ' ' && i > 0){c[cnt++]=s[i]; i--;}
    string str=c;
    reverse(str.begin(),str.end());
    if(str == "not" || str == "and" || str == "or") return 0;
    memset(c,'\0',sizeof(c));
    i=t;
    i+=4;
    cnt=0;
    int lene=s.length();
    while(s[i] != ' ' && i < lene){c[cnt++]=s[i], i++;}
    str=c;
    if(str == "and" || str == "or") return 0;
    return 1;
}
bool check4(int i){     //判断 or 前后是否合法 
    int t=i;
    char c[305]="";
    int cnt=0;
    i-=2;
    while(s[i] != ' ' && i > 0){c[cnt++]=s[i]; i--;}
    string str=c;
    reverse(str.begin(),str.end());
    if(str == "not" || str == "and" || str == "or") return 0;
    memset(c,'\0',sizeof(c));
    i=t;
    i+=3;
    cnt=0;
    int lene=s.length();
    while(s[i] != ' ' && i < lene){c[cnt++]=s[i], i++;}
    str=c;
    if(str == "and" || str == "or") return 0;
    return 1;
}
bool check3(int i){ //判断not前后是否合法 
    kongge();
    int cnt=0;
    char c1[10]="";
    while(s[--i] == ' ');   //-
    int lene=s.length();
    while(s[++i] != ' ' && i < lene)c1[cnt++]=s[i]; // -
    string str=c1;
    if(str == "or" || str == "and")    return 0;
    return 1;
}
bool check(int i){
    kongge();
    if(s[i+4]=='f'&&s[i+5]=='a'&&s[i-5]=='t'&&s[i-4]=='r')  return 1;
    if(s[i+4]=='t'&&s[i+5]=='r'&&s[i-6]=='f'&&s[i-5]=='a')  return 1;
    return 0;
}
bool check2(int i){
    kongge();
    if(s[i+3]=='f'&&s[i+4]=='a'&&s[i-5]=='t'&&s[i-4]=='r')  return 1;
    if(s[i+3]=='t'&&s[i+4]=='r'&&s[i-6]=='f'&&s[i-5]=='a')  return 1;
    return 0;
}
void init(){
    bool fl=1;
    l=s.length();
    for(int i=0;i<l;i++){
        if(s[i]=='t'&&s[i+1]=='r'&&s[i+2]=='u'&&s[i+3]=='e'){
            fl=0;
            i+=3;
        }
        else if(s[i]=='f'&&s[i+1]=='a'&&s[i+2]=='l'&&s[i+3]=='s'&&s[i+4]=='e'){
            fl=0;
            i+=4;
        }
    }
    if(fl){
        cout << "error";
        exit(0); 
    }
}
void solve(){
    l=s.length();
    if(l == 0){
        cout << "error";
        exit(0); 
    }
    kongge();
    if(s[0]=='a' || s[0]=='o' || s[l-1]=='d' || s[l-1]=='r' || s[l-1]=='t'){
        cout << "error";exit(0);
    }
    if(l <= 5){
        kongge();
        cout << s;
        exit(0);
    }
    for(int i=0;i<l;i++){
        if((s[i]=='a'&&s[i+1]=='n')||(s[i]=='o'&&s[i+1]=='r')){
            if(!check1(i)){
                cout << "error";
                exit(0); 
            }
        }
    }
    bool fl=0;
    for(int i=0;i<l;i++){
        if(s[i]=='n'&&s[i+1]=='o'&&s[i+2]=='t'){
            fl=1;
            i+=2;
        }
        else if(s[i]=='a'&&s[i+1]=='n'&&s[i+2]=='d'){
            fl=1;
            i+=2;
        }
        else if(s[i]=='o'&&s[i+1]=='r'){
            fl=1;
            i++;
        }
    }
    //cout << fl;
    kongge();
    l=s.length();
    if(!fl && l > 6){   //l>6原因：末尾可能会有一个多余空格 
        //cout << l << s;
        cout << "error";
        exit(0); 
    }
    init();
    return ;
}
int main(){
    getline(cin,s);
    init();
    solve();
    string stmp="not";
    while(s.find(stmp) != -1){
        kongge();
        l=s.length(); 
        for(int i=0;i<l;i++){
            if(s[i] == 'n' && s[i+1] == 'o'){
                if(!check3(i)){
                    cout << "error";
                    return 0;
                }
                //cout << i << " ";
                s[i]=s[i+1]=s[i+2]=' ';
                //cout << s << "@";
                i+=3;
                int t=1;
                while(s[i] == ' ')  i++;
                while(s[i] == 'n' && s[i+1] == 'o'){
                    s[i]=s[i+1]=s[i+2]=' ';t++;i+=3;
                    while(s[i] == ' ')  i++;
                }
                //cout<<i<<t<<endl;
                //i++;
                if(t%2 != 0){
                    //cout << s[i] << "#";
                    if(s[i] == 't' && s[i+1] == 'r'){
                        s.erase(i,4);
                        string tmp="false";
                        s.insert(i,tmp);
                        i++;
                    }   
                    else if(s[i] == 'f' && s[i+1] == 'a'){
                        s.erase(i,5);
                        string tmp="true";
                        s.insert(i,tmp);
                        i--;
                    }   
                }
               // cout << s << "@";
                break;
            }
        }
    }
    solve();
    string ssss="and";
    while(s.find(ssss) != -1){
        kongge();
        l=s.length(); 
        for(int i=0;i<l;i++){
            kongge();
            if(s[i] == 'a' && s[i+1] == 'n'){
                if(!check1(i)){ //and两边出现not或or 
                    cout << "error";
                    return 0; 
                }
                else if(s[i-4] == 'n' && s[i-3] == 'o'){
                    cout << "error";
                    return 0;
                }
                if(s[i+4]=='f'&&s[i+5]=='a'&&s[i-6]=='f'&&s[i-5]=='a'){ //双false
                    s.erase(i,9);
                }
                else if(s[i+4]=='t'&&s[i+5]=='r'&&s[i-5]=='t'&&s[i-4]=='r'){    //双true 
                    s.erase(i,8);
                }
                else if(check(i)){  //一true一false 
                    if(s[i+4]=='f') s.erase(i-5,8);
                    else    s.erase(i,8);
                } 
                break;
            }   
        }  
    }
    solve();
    string sss="or";
    while(s.find(sss)!=-1){
        kongge();
        l=s.length(); 
        for(int i=0;i<l;i++){
            kongge();
            if(s[i] == 'o' && s[i+1] == 'r'){
                if(!check4(i)){
                    //cout << s;
                    cout << "error";
                    return 0;
                }
                else if(s[i-4] == 'n' && s[i-3] == 'o'){
                    cout << "error";
                    return 0;
                }
                if(s[i+3]=='f'&&s[i+4]=='a'&&s[i-6]=='f'&&s[i-5]=='a'){ //双false
                    s.erase(i,8);
                }
                else if(s[i+3]=='t'&&s[i+4]=='r'&&s[i-5]=='t'&&s[i-4]=='r'){    //双true 
                    s.erase(i,7);
                }
                else if(check2(i)){ //一true一false 
                    if(s[i+3]=='f') s.erase(i,8);
                    else    s.erase(i-6,9);
                } 
                break;
            }
        }
    }
    solve();
    cout << s;
    return 0;
}

文章、代码若有错误欢迎大佬指出。