CCF-CSP 201709-3 JSON查询 题解

试题编号: 201709-3
试题名称: JSON查询
时间限制: 1.0s
内存限制: 256.0MB
问题描述:
问题描述
  JSON (JavaScript Object Notation) 是一种轻量级的数据交换格式,可以用来描述半结构化的数据。JSON 格式中的基本单元是值 (value),出于简化的目的本题只涉及 2 种类型的值:
  * 字符串 (string):字符串是由双引号 " 括起来的一组字符(可以为空)。如果字符串的内容中出现双引号 ",在双引号前面加反斜杠,也就是用 " 表示;如果出现反斜杠 ,则用两个反斜杠 \ 表示。反斜杠后面不能出现 " 和 以外的字符。例如:""、"hello"、""\"。
  * 对象 (object):对象是一组键值对的无序集合(可以为空)。键值对表示对象的属性,键是属性名,值是属性的内容。对象以左花括号 { 开始,右花括号 } 结束,键值对之间以逗号 , 分隔。一个键值对的键和值之间以冒号 : 分隔。键必须是字符串,同一个对象所有键值对的键必须两两都不相同;值可以是字符串,也可以是另一个对象。例如:{}、{"foo": "bar"}、{"Mon": "weekday", "Tue": "weekday", "Sun": "weekend"}。
  除了字符串内部的位置,其他位置都可以插入一个或多个空格使得 JSON 的呈现更加美观,也可以在一些地方换行,不会影响所表示的数据内容。例如,上面举例的最后一个 JSON 数据也可以写成如下形式。
  {
  "Mon": "weekday",
  "Tue": "weekday",
  "Sun": "weekend"
  }
  给出一个 JSON 格式描述的数据,以及若干查询,编程返回这些查询的结果。
输入格式
  第一行是两个正整数 nm,分别表示 JSON 数据的行数和查询的个数。
  接下来 n 行,描述一个 JSON 数据,保证输入是一个合法的 JSON 对象。
  接下来 m 行,每行描述一个查询。给出要查询的属性名,要求返回对应属性的内容。需要支持多层查询,各层的属性名之间用小数点 . 连接。保证查询的格式都是合法的。
输出格式
  对于输入的每一个查询,按顺序输出查询结果,每个结果占一行。
  如果查询结果是一个字符串,则输出 STRING <string>,其中 <string> 是字符串的值,中间用一个空格分隔。
  如果查询结果是一个对象,则输出 OBJECT,不需要输出对象的内容。
  如果查询结果不存在,则输出 NOTEXIST。
样例输入
10 5
{
"firstName": "John",
"lastName": "Smith",
"address": {
"streetAddress": "2ndStreet",
"city": "NewYork",
"state": "NY"
},
"esc\aped": ""hello""
}
firstName
address
address.city
address.postal
escaped
样例输出
STRING John
OBJECT
STRING NewYork
NOTEXIST
STRING "hello"
评测用例规模与约定
  n ≤ 100,每行不超过 80 个字符。
  m ≤ 100,每个查询的长度不超过 80 个字符。
  字符串中的字符均为 ASCII 码 33-126 的可打印字符,不会出现空格。所有字符串都不是空串。
  所有作为键的字符串不会包含小数点 .。查询时键的大小写敏感。
  50%的评测用例输入的对象只有 1 层结构,80%的评测用例输入的对象结构层数不超过 2 层。举例来说,{"a": "b"} 是一层结构的对象,{"a": {"b": "c"}} 是二层结构的对象,以此类推。

首先这道题目并没有像传统的CCF-CSP的题目那么长

可能是因为前几年的题目的缘故

由于这是一道模拟题

所以博主就直接上代码

配合详细的注释应该非常好理解


  1 //Author:LanceYu
  2 #include<iostream>
  3 #include<string>
  4 #include<cstring>
  5 #include<cstdio>
  6 #include<fstream>
  7 #include<iosfwd>
  8 #include<vector>
  9 #include<cstdlib>
 10 #include<queue>
 11 #include<set>
 12 #include<ctime>
 13 #include<algorithm>
 14 #include<complex>
 15 #include<cmath>
 16 #include<array>
 17 #include<valarray>
 18 #include<bitset>
 19 #define ll long long
 20 using namespace std;
 21 const double clf=1e-8;
 22 //const double e=2.718281828;
 23 const double PI=3.141592653589793;
 24 const int MMAX=2147483647;
 25 const int mod=1e9+7;
 26 //priority_queue<int>p;
 27 //priority_queue<int,vector<int>,greater<int> >pq;
 28 char a[10001],b[10001];//创建两个字符数组用于保存字符串 
 29 int main()
 30 {
 31     //freopen("C:\Users\LENOVO\Desktop\in.txt","r",stdin);
 32     //freopen("C:\Users\LENOVO\Desktop\out.txt","r",stdin);
 33     int n,k;
 34     scanf("%d%d",&n,&k);
 35     getchar();
 36     int i=0,j=0,flag=0,t,len,head=0,count,sum=0;
 37     char c;
 38     while(1)
 39     {
 40         c=getchar();
 41         if(c==' ')
 42             continue;
 43         else if(c=='
')
 44             flag++;
 45         else a[i++]=c;
 46         if(flag==n)
 47             break;
 48     }//读入时自动过滤空格和换行 
 49     len=strlen(a);
 50     j=0;
 51     for(i=0;i<len;i++)
 52     {
 53         if(a[i]=='\'&&(a[i+1]=='\'||a[i+1]=='"'))
 54             b[j++]=a[++i];
 55         else if(a[i]!='"')
 56             b[j++]=a[i];
 57     }//变化\ 和 "同时消除多余的引号,方便下面处理 
 58     len=strlen(b);
 59     //puts(b);
 60     string s,str[81];//s保存分割前的,str保存分割后的 
 61     while(k--)
 62     {
 63         cin>>s;
 64         int q=0;//q用于保存是否满足Object和String两种状态 
 65         int len2=s.length();
 66         int w=0;//分有点和没有点讨论,本来是像靠没有点捞点分的 
 67         for(i=0;i<len2;i++)
 68         { 
 69             if(s[i]=='.')
 70             { 
 71                 w++;
 72                 break;
 73             }
 74         }
 75         if(!w)//没有点的情况
 76         {
 77             for(i=0;i<len-len2;i++)
 78             {
 79                 flag=0;
 80                 for(j=0;j<len2;j++)
 81                 {
 82                     if(b[i+j]==s[j])
 83                         flag++;
 84                 }//出现字串进行以下处理 
 85                 if(flag==len2)
 86                 {
 87                     sum=0;
 88                     for(j=1;j<i+len2;j++)
 89                     {
 90                         if(b[j]=='{')
 91                             sum++;
 92                         else if(b[j]=='}')
 93                             sum--;
 94                     }
 95                     if(sum)//计算这个之前的{和}的数量(除第一个以外),如果两两配对证明是第一层的元素 
 96                         continue;
 97                     int bz=0;//bz作为标记判定是否是OBJECT和STRING 
 98                     if(b[i+len2]==':'&&b[i+len2+1]=='{')
 99                         bz=2;//有:{组合,一定是OBJECT 
100                     else if(b[i+len2]==':')
101                     {
102                         bz=1;//除上面的情况,还出现了:一定是STRING 
103                         head=i+len2+1;//head表示STRING起始的位置 
104                     }
105                     if(j==len)
106                         t=j;
107                     if(bz==2)
108                     {
109                         q=1;
110                         printf("OBJECT
");
111                     }
112                     else if(bz==1)
113                     {
114                         q=1;
115                         printf("STRING ");
116                         for(j=head;b[j]!=','&&b[j]!='}';j++)
117                             putchar(b[j]);
118                         putchar('
');
119                     }
120                 }
121             }
122             if(!q)//如果不满足OBJECT和STRING的情况就不存在 
123                 printf("NOTEXIST
"); 
124         }
125         else
126         {
127             count=1;
128             for(i=0;i<len2;i++)
129             {
130                 if(s[i]=='.')
131                 {
132                     s[i]=' ';//有点的地方打上空格方便用字符串流处理 
133                     count++;
134                 }
135             }
136             istringstream ss(s);
137             for(i=0;i<count;i++)
138                 ss>>str[i];//分割字符串 
139             t=0;
140             for(int l=0;l<count;l++)//l用于保存当前处理的字符串是第几个 
141             {
142                 len2=str[l].length();
143                 for(i=t;i<len-len2;i++)//i一定要从当前的位置之后遍历获取下一个的位置 
144                 {
145                     flag=0;
146                     for(j=0;j<len2;j++)
147                     {
148                         if(b[i+j]==str[l][j])
149                             flag++;
150                     }//和上面没有点的情况同理 
151                     if(flag==len2&&b[i+len2]==':'&&b[i+len2+1]=='{'&&l!=count-1)
152                     {
153                         if(l==0)
154                             head=i+len2;//head表示刚开始的位置 
155                         t=i+len2+2;//t表示结束的位置 
156                         break;
157                     }
158                     else if(flag==len2&&b[i+len2]==':'&&l==count-1&&b[i+len2+1]!='{')
159                     {
160                         sum=0;
161                         for(j=head-1;j<i+len2;j++)
162                         {
163                             if(b[j]=='{')
164                                 sum++;
165                             else if(b[j]=='}')
166                                 sum--;
167                         }
168                         if(sum!=count-1)//和上面相同,不一样的地方在于这里只能有count-1个,且这里放在了是string的里面,当然放在外面也是可以的,读者自行考虑 
169                             continue; 
170                         printf("STRING ");
171                         q=1;
172                         for(j=i+len2+1;b[j]!=','&&b[j]!='}';j++)
173                             putchar(b[j]);
174                         putchar('
');
175                         break;
176                     }
177                     else if(flag==len2&&b[i+len2]==':'&&l==count-1&&b[i+len2+1]=='{')//当里面还有:{组合的时候就是OBJECT 
178                     {
179                         printf("OBJECT
");
180                         q=1;
181                         break;
182                     }
183                 }
184             }
185             if(!q)
186                 printf("NOTEXIST
");
187         }
188     }
189     return 0;
190 }

这个代码虽然可以AC,但是仍然存在很大的bug

例如:{组合判断本身就不够严谨,因为双引号里面完全可能出现:{组合,这个是非常正常的现象

同时}判断也是同理

所以在字符串分解的时候应该保留双引号

具体操作就不再赘述了

2019-02-19 06:36:50  Author:LanceYu

原文地址:https://www.cnblogs.com/lanceyu/p/10398977.html