ccf 201709-3 JSON查询

ccf 201709-3 JSON查询

解题思路：

　　首先，先逐行读入n行数据，因为数据中会经常出现空格或者是换行，所以，我们遇到空格和换行就忽略，同时将转义字符进行处理，将n行数据存入一个一维数组中。由于“n ≤ 100，每行不超过 80 个字符。m ≤ 100，每个查询的长度不超过 80 个字符”，所以我们可以将一位数组的大小设置为100*80，我偷了个懒直接设置了一维数组 in[maxn * maxn]。

　　接着需要构造一个映射，即做一个 string->string 或者是 string->object 的映射。

　　首先考虑string->string的映射，可以使用map<string,string>。

　　string->object的映射也可以转换为string->string的映射，例如输入样例：

　　　　10 5
　　　　{
　　　　"firstName": "John",
　　　　"lastName": "Smith",
　　　　"address": {
　　　　"streetAddress": "2ndStreet",
　　　　"city": "NewYork",
　　　　"state": "NY"
　　　　},
　　　　"esc\aped": ""hello""
　　　　}

　　其中的address即为嵌套，我们可以将address键值对应的object中的string->string映射如下存储：

　　　　address.streetAddress -> 2ndStreet
　　　　address.city -> NewYork
　　　　address.state -> NY

　　这样直接查找address.city就可以找到NewYork。需要注意，遇到address之后的第一个左括号' { '应该先存入：

　　　　address -> OBJECT

　　多层嵌套怎么处理呢，我们可以将一个object看成一个递归结构，每次遇到左花括号"{"就调用处理object的函数，进行处理。

　　开始的时候，在main函数中调用

　　solve("",in+1);//处理第一层嵌套

　　含义是：当前key为空，去掉左边第一个花括号，进入第一层嵌套。solve的功能就是进行string->string的映射，在记录完key值之后，遇到左括号' { '，就继续调用solve进行处理。

　　详细如何进行string->string的映射就...看代码吧

 1 #include<iostream>
 2 #include<cstring>
 3 #include<map>
 4 using namespace std;
 5 const int maxn = 100+5;
 6 map<string,string> dic; 
 7 char in[maxn*maxn];
 8 
 9 int solve(char *key,char *a)
10 {//处理的字符串的长度 
11     for(int i=0;i<strlen(a);i++)
12     {
13         char nowKey[maxn],value[maxn]; 
14         int lenKey = strlen(key);
15         int k=0;
16         for(k=0;k<lenKey;k++)
17             nowKey[k] = key[k];
18         nowKey[k] = '';
19         if(lenKey > 0)
20         {
21             nowKey[lenKey++] = '.';
22             nowKey[lenKey] = '';
23         }
24         if(a[i] == '"')//key的第一个引号
25         {
26             i++;
27             while(a[i] != ':')
28             {
29                 nowKey[lenKey++] = a[i++]; 
30             }
31             nowKey[lenKey-1] = '';
32          } 
33          //i++;//：
34          i++;//"或是｛
35          if(a[i] == '"'){
36              ///得到value的值，建立map 
37              int j=7;
38              i++;
39              strcpy(value,"STRING ");
40              while(a[i] != ',' && a[i] != '}'){
41                  value[j++] = a[i++];
42              }
43              value[j-1] = '';
44              dic[nowKey] = value;
45          }else if(a[i] == '{')
46          {
47               ///首先存储nowKey到map中
48              dic[nowKey] = "OBJECT";
49              i += solve(nowKey,a+i+1)+1;
50           } 
51           //i++;//，或是}
52           if(a[i] == '}')
53               return i+1;
54            //如果是，则继续处理 
55     }
56 }
57 
58 int main()
59 {
60     string str;
61     int n,m;
62     cin>>n>>m;
63     n = n+1;
64     int i=0;
65     while(n--)
66     {///除了字符串内部的位置，其他位置都可以插入一个或多个空格使得 JSON 的呈现更加美观，
67     ///也可以在一些地方换行，不会影响所表示的数据内容。
68     ///为了处理掉多余的空格和换行，我将输入数据存储到一个一维的char数组中 
69         getline(cin,str);
70         ///将读入的字符串先进行处理，存储到字符数组中
71         for(int k=0;k<str.length();k++)
72         {
73             if(str[k]=='\')
74                 in[i++] = str[++k];
75             else if(str[k] == ' ' || str[k] == '
')
76                 continue;
77             else{
78                 in[i++] = str[k];
79             }
80          } 
81     }
82     in[i] = '';
83     solve("",in+1);//处理第一层嵌套 
84     
85     for(int j=0;j<m;j++)
86     {
87         string str2;
88         getline(cin,str2);
89         map<string,string>::iterator iter = dic.find(str2);
90         if(iter != dic.end())
91         {//找到了 
92             cout<<dic[str2]<<endl;
93         }else{
94             cout<<"NOTEXIST"<<endl;
95         }
96     }
97     //printf("%s
",in);
98     return 0;
99 }