【题解】P1575 正误问题

_Yoimiya_ · 2021-07-19 15:22:02 · 题解

题目传送门。

题意：输入一个字符串形式的逻辑表达式，求值。

解题思路：

• 先将读入的一个个字符串转成数字，方便后面计算。
• 先考虑 error 的情况。
• 共 3 种情况使得表达式不合法，包括：连续的布尔值，连续的与、或运算符，非运算后不是布尔值或非运算符。特判后输出即可。
• 特判 error 同时处理逻辑表达式里的非运算符（非运算符拥有最高的优先级），将其对应的逻辑值转换一下。
• 处理完非运算符后，分批处理“与”和“或”两种运算符。
• 处理完后，输出答案即可。

AC 代码（含有注释）：

 #include<bits/stdc++.h>
using namespace std;
const int M(1e3+5);
int handle[M],flag[M],ans,tot;
string s;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    while(cin>>s){
        if(s=="false")handle[++tot]=0;
        if(s=="true") handle[++tot]=1;
        if(s=="and")  handle[++tot]=3;
        if(s=="not")  handle[++tot]=4;
        if(s=="or")   handle[++tot]=2;
    }
    for(register int i(1),last(0);i<=tot;++i){
        if(!handle[i]||handle[i]==1){//当前位置是布尔值 
            if(last==1) {cout<<"error";return 0;}//是否为连续布尔值 
            last=1;
        }
        else{
            if(handle[i]==4){//当前位置是非 
                if(handle[i+1]==2||handle[i+1]==3){
                    cout<<"error";return 0;//非后跟其他逻辑运算符
                }
                else{
                    bool ts(1);while(handle[i+1]==4)++i,ts^=1;//处理连续的非
                    handle[i+1]=ts^handle[i+1];
                }
            }
            else{
                if(!last) {cout<<"error";return 0;}//前面是不是布尔值 
                last=0;
            }
        }
    }
    register int top(0); 
    for(register int i(1);i<=tot;++i){
        if(!handle[i]||handle[i]==1) ++top,flag[top]=handle[i];
        if(handle[i]==3) flag[top]&=handle[++i];//处理与运算 
    }
    for(register int i(1);i<=top;++i) ans|=flag[i];
    if(!ans)cout<<"false";else cout<<"true";
    return 0;
}