【题解】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;
  }