题解：CF7E Defining Macros

· · 题解

思路

众所周知，乘除法的运算优先级大于加减法的运算优先级，有括号先算括号里面的。

输入

首先输入，注意这句话：

The input lines may contain any number of spaces anywhere, providing these spaces do not break the word "define" or the names of constructions and variables. In particular, there can be any number of spaces before and after the "#" symbol.

意思就是：

在 # 前后可能出现任意多个空格。

我们先输入名字和内容，内容要去空格处理后才可用。

判断

我们发现有四种可能：

我们从后往前判断（从前往后会在第六个 WA），将整个式子分成两部分。

如果两部分都是 d，那么整个式子也是 d；

如果分隔符是 +，那么整个式子是 b；

如果分隔符是 -，并且后面的式子为 b，那么整个式子为 d，否则为 b。

如果分隔符是 *，如果前后两个式子有一个是 b，那么整个式子为 d。否则为 c。

如果分隔符是 /，如果前后两个式子有一个是 b或者后面的式子为 c，那么整个式子为 d，否则是 c。

如果这个式子第一个字符为 (，或第四个字符为 )，我们只需要判断括号里面的是不是对的。

如果以上都不是，那么这个式子只能是一串字母。我们用 map 存一下我们输入的宏定义的状态 (a,b,c,d)，判断这串字母是不是宏定义，如果是宏定义 那么判断这个宏定义是不是对的；如果不是宏定义，就直接正确。

整体

我们只需要把最后输入的字符串判断一下是不是对的即可。

代码

#include<iostream>
#include<map>
#include<string>
using namespace std;
map<string,int> mp;
/*
 level:
 1: 左右全是括号，完全正确
 2: x+y x-y
 3: x*y,x/y
 4: !@#$%^ 完全错误
 */
int check(string s,int l,int r){//递归进行，s是字符串,l和r是左右下标
    int f=0;
    int kuohao=0;
    int l1,l2;
    for(int i=r;i>=l;i--){
        if(s[i]=='(') kuohao++;
        else if(s[i]==')') kuohao--;
        else if((kuohao==0&&f==0)&&(s[i]=='*'||s[i]=='/')){
            f=i;
        }
        else if((kuohao==0&&(s[i]=='+'||s[i]=='-'))){
            l1=check(s,l,i-1);
            l2=check(s,i+1,r);
            //cout<<l1<<" "<<l2<<endl;
            if(l1==4||l2==4) return 4;
            if(s[i]=='+'){
                return 2;
            }
            if(s[i]=='-'){
                if(l2==2) return 4;
                else return 2;
            }
        }

    }
    if(f!=0){
        l1=check(s,l,f-1);
        l2=check(s,f+1,r);
        if(l1==4||l2==4) return 4;
        if(s[f]=='*'){
            if(l1==2||l2==2) return 4;
            else return 3;
        }
        if(s[f]=='/'){
            if(l2==2||l1==2||l2==3) return 4;
            else return 3;
        }
    }
    else if(s[l]=='('&&s[r]==')'){
        if(check(s,l+1,r-1)==4){
            return 4;
        }
        return 1;
    }
    else{
        string ss;
        ss="";
        for(int j=l;j<=r;j++){
            ss+=s[j];
        }
        if(mp[ss]!=0){
            return mp[ss];
        }
        return 1;
    }
    return 1;
}
signed main(){
    int T;
    cin>>T;
    for(int i=1;i<=T;i++){
        string t;
        cin>>t;
        if(t[t.size()-1]=='#') cin>>t;
        string na;
        cin>>na;
        string s3;//去空格后的字符串
        string s2;//去空格前的字符串
        getline(cin,s2);
        s3="";
        for(int j=0;j<s2.size();j++){
            if(s2[j]!=' '){
                s3+=s2[j];
            }
        }
        //cout<<s3<<endl;
        mp[na]=check(s3,0,s3.size()-1);
        //cout<<mp[s[i].na]<<endl;

    }
    string s2;
    getline(cin,s2);
    string code;
    for(int j=0;j<s2.size();j++){
        if(s2[j]!=' '){
            code+=s2[j];
        }
    }
    //cout<<code<<endl;
    if(check(code,0,code.size()-1)!=4){
        cout<<"OK";
    }
    else{
        cout<<"Suspicious";
    }
    return 0;
}