题解 P1575 正误问题

· · 题解

解题思路：

考虑模拟，先将字符串式的读入转换成数组方便处理，同时处理逻辑 not，然后就像普通的多项式求值一样处理 and 和 or。

具体的，用一个栈维护当前剩下的布尔值，对于 or 直接丢进去，最后统一处理，对于 and 将栈顶与序列中的下一个值进行 and 运算。

这里会发现一个问题，就是查找下一个值得时候可能会有 not，导致写起来比较困难，可以先将所有的 not 处理掉，然后在下一次循环中直接往后取值。

对于表达式错误的判断有且仅有以下几条：

  1. not 后跟运算符；
  2. 连续的运算符或布尔值；
  3. 最后一个是 not 或运算符，即没有布尔值对应。

实现上：特判第三点；处理 not 时同时判断第一点；对于第二点，使用一个值对应上一个非 not 符号是运算符还是布尔值，然后处理时直接判断。这些操作都可以再依次循环中解决。

注意可能出现连续的 not，这样是正确的。

代码：

#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
string a;
int s[1005],len,last,st[1005],top,ans;
int main(){
    while(cin>>a){
        len++;
        if(a=="true")s[len]=1;
        if(a=="false")s[len]=0;
        if(a=="or")s[len]=2;
        if(a=="and")s[len]=3;
        if(a=="not")s[len]=4;
    }
    s[len+1]=2;
    for(int i=1;i<=len;i++){
        if(s[i]==1||s[i]==0){
            if(last==1)return printf("error\n")&0;
            last=1;
        }
        else
        if(s[i]==4){
            if(s[i+1]==2||s[i+1]==3)return printf("error\n")&0;
            else{
                bool b=1;
                while(s[i+1]==4)i++,b^=1;
                s[i+1]=b^s[i+1];
            }
        }
        else{
            if(last==0)return printf("error\n")&0;
            last=0;
        }
    }
    for(int i=1;i<=len;i++){
        if(s[i]==0||s[i]==1)top++,st[top]=s[i];
        if(s[i]==3)st[top]&=s[i+1],i++;
    }
    for(int i=1;i<=top;i++){
        ans|=st[i];
    }
    if(ans)
    printf("true\n");
    else
    printf("false\n");
    return 0;
}