CCF201709-3-JSON查询

（一）题目描述：

（二）解题思路：

1.先简单说一下当时我在考场上的做法吧：首先开许多个的map，每一个map保存每一层对象的键-值对，再开一个单独的map保存每一个对象对应的编号，以便查询。查询的时候顺着‘.’将待查询的字符串依次分解，然后分别查询map中的值。做着做着发现这样很容易导致同一层不同对象之间存在冲突，但是当时时间不够了，就硬着头皮写了下去，最后比预期结果要好点：80分。

现在回想起来当时的思路是真的乱，代码也写得乱。当时的做法有这么几个缺陷，首先在保存的时候要在不同层次的对象之间跳转有点麻烦，然后是在查询的时候假如层次有许多层的话，要分解起来也比较麻烦，每次还要做一系列的判断。

2.今天闲着无聊又去做了一下这个题目，想到了一种新的做法：上次我是将每个对象的键值对保存，然后沿着路径查询。而这次想到可以直接在分析原来的字符串的时候直接将所有的路径保存，这些路径用一个map<string,string>ans储存，具体来说样例的过程是这样：

ans[.firstname]=John                                             //第一个点是为了保持操作统一

ans[.lastname]=Smith

ans[.address]=OBJECT

ans[.address.streetAddress]=2ndStreet

ans[.address.city]=NewYork

ans[.address.state]=NY;

ans[.esc\aped]="hello"

这样的话就是把所有的可能查询全部保存下来，查询的时候便可以根据输入直接判断出结果，这样听操作起来似乎十分简单，但是实际上...也并不复杂。我们主要需要解决的是怎么在路径之间跳转，比如这里由"."变为".address"，再由".address"变为"."，我这里用一个map<string,string>stf(emmm，意思是son to father)解决，就是保存了当期路径的上一个路径，当碰到‘{’时，生成一个新的路径，当碰到‘}’时,回到前一个路径，具体细节参见代码。

（三）具体代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
using namespace std;
map<string,string>ans,stf;
string getstring(int &i,string str){
    i++;string ss="";
    while(1){
        if(str[i]=='"')break;
        if(str[i]=='\\')ss+=str[i+1],i++;
        else ss+=str[i];
        i++;
    }
    return ss;
}
int main(){
    int n,m;
    string s,str="",key="",val="",name="";
    cin>>n>>m;getchar();
    for(int i=0;i<n;i++)getline(cin,s),str+=s;
    int len=str.length();
    for(int i=1;i<len-1;i++)
    if(str[i]==' '||str[i]==',')continue;
    else if(str[i]=='}')name=stf[name];
    else if(str[i]=='"')key=getstring(i,str);
    else if(str[i]==':'){
        i++;while(str[i]==' ')i++;
        if(str[i]=='"'){
            val=getstring(i,str);
            ans[name+'.'+key]=val;
        }
        else if(str[i]=='{'){
            ans[name+'.'+key]="OBJECT";
            stf[name+'.'+key]=name;
            name=name+'.'+key;
        }
    }
    for(int i=0;i<m;i++){
        cin>>s;s='.'+s;
        if(ans[s]=="")cout<<"NOTEXIST"<<endl;
        else if(ans[s]=="OBJECT")cout<<"OBJECT"<<endl;
        else cout<<"STRING "<<ans[s]<<endl;
    }
    return 0;
}

结果写完后1A，当时真的是蠢了，还浪费了大量的时间...果然第三题这样的模拟还是得要有一个合适的思路才行QWQ。