CCF CSP 201709-3.JSON查询

发表于 | 更新于 | 分类于 | 浏览 次
字数统计: 2k

问题描述

　　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 格式描述的数据，以及若干查询，编程返回这些查询的结果。

输入格式

　　第一行是两个正整数 n 和 m，分别表示 JSON 数据的行数和查询的个数。
　　接下来 n 行，描述一个 JSON 数据，保证输入是一个合法的 JSON 对象。
　　接下来 m 行，每行描述一个查询。给出要查询的属性名，要求返回对应属性的内容。需要支持多层查询，各层的属性名之间用小数点 . 连接。保证查询的格式都是合法的。

输出格式

　　对于输入的每一个查询，按顺序输出查询结果，每个结果占一行。
　　如果查询结果是一个字符串，则输出 STRING <string>，其中 <string> 是字符串的值，中间用一个空格分隔。
　　如果查询结果是一个对象，则输出 OBJECT，不需要输出对象的内容。
　　如果查询结果不存在，则输出 NOTEXIST。

样例输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
10 5
{
"firstName": "John",
"lastName": "Smith",
"address": {
"streetAddress": "2ndStreet",
"city": "NewYork",
"state": "NY"
},
"esc\\aped": "\"hello\""
}
firstName
address
address.city
address.postal
esc\aped

样例输出

1
2
3
4
5
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”}} 是二层结构的对象，以此类推。

分析：

使用map<string,string>存储解析后的JSON字符串。

遇到对象，键值用{}表示。对象parent中的子对象或者字符串的属性名key，使用parent + '.' + key 作键名。

解析字符串的过程如下：

遇到右花括号}，则表示当前需要处理的json串已经结束；

遇到空格或者逗号,，则直接跳过；

遇到引号"，则获取键名；

遇到冒号:，则先去掉可能存在的空格，然后判断值是字符串，还是对象。

若为字符串，则获取键值；若为对象，则去掉左花括号{后面可能存在的空格，继续解析JSON子串。

注意：

1.键的大小写敏感。

2.键名和键值中可能存在转义字符，需要将\"转换为"，将\\转换为\。

  • C++版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <cstdio>
#include <iostream>
#include <map>
#include <string>
using namespace std;

map<string, string> json;

// 从下标i开始，寻找键名或者键值，并去掉首尾的引号、中间的转义符号'\'
string get(int &i, string str) {
	string key;
	i++;
	while (i < str.size() && str[i] != '"') {
		// 若遇到转义符号，则跳过一位
		if (str[i] == '\\') {
			key += str[++i];
		} else {
			key += str[i];
		}
		i++;
	}
	return key;
}

// 解析json字符串，parent表示当前处理的json串是哪个键的值，
// str为尚未解析的字符串，返回值为本次解析的json串的长度
int parseJSON(string parent, string str) {

	string key;
	for (int i = 0; i < str.size(); i++) {

		// 遇到右花括号}，表示当前需要处理的json串已经结束
		if (str[i] == '}') {
			return i;
		}

		if (str[i] == ' ' || str[i] == ',') {
			continue;
		}
		// 获取键名
		if (str[i] == '"') {
			key = get(i, str);
			continue;
		}
		// 获取键值
		if (str[i] == ':') {
			// 去掉可能存在的空格
			while (str[++i] == ' ') {}
			// 若值为字符串
			if (str[i] == '"') {
				string value = get(i, str);
				if (!parent.empty()) {
					json[parent + '.' + key] = value;
				} else {
					json[key] = value;
				}
				continue;
			}
			// 若值为对象
			// 去掉左花括号{后面可能存在的空格
			while (str[++i] == ' ') {}
			string newParent;
			if (!parent.empty()) {
				newParent = parent + '.' + key;
			} else {
				newParent = key;
			}
			// 用{}标记newParent的值为对象
			json[newParent] = "{}";
			// 解析子串
			i += parseJSON(newParent, str.substr(i));
		}
	}
	return str.size();
}

int main() {
	int n, m;
	cin >> n >> m;
	getchar();

	string str = "";
	string line;
	while (n--) {
		getline(cin, line);
		str += line;
	}

	parseJSON("", str);

	while (m--) {
		cin >> line;
		if (!json.count(line)) {
			cout << "NOTEXIST" << endl;
		} else if (json[line] == "{}") {
			cout << "OBJECT" << endl;
		} else {
			cout << "STRING " << json[line] << endl;
		}
	}

	return 0;
}
  • Java版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

	public static Map<String, String> json = new HashMap<>();

	// 返回键名或键值最后一个字符的索引号
	public static int offset(int i, String str) {
		i++;
		while (i < str.length() && str.charAt(i) != '"') {
			if (str.charAt(i) == '\\') {
				i++;
			}
			i++;
		}
		return i;
	}

	// 解析json字符串，parent表示当前处理的json串是哪个键的值，
	// str为尚未解析的字符串，返回值为本次解析的json串的长度
	public static int parseJSON(String parent, String str) {

		String key = null;
		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == '}') {
				return i;
			}
			if (str.charAt(i) == ' ' || str.charAt(i) == ',') {
				continue;
			}
			// 获取键名
			if (str.charAt(i) == '"') {
				int index = offset(i, str);
				// 将键名中的\\替换为\，\"替换为"
				key = str.substring(i + 1, index).replace("\\\\", "\\").replace("\\\"", "\"");
				i = index;
				continue;
			}

			// 获取键值
			if (str.charAt(i) == ':') {
				// 去掉可能存在的空格
				while (str.charAt(++i) == ' ') {}
				// 若值为字符串
				if (str.charAt(i) == '"') {
					int index = offset(i, str);
					String value = str.substring(i + 1, index).replace("\\\\", "\\").replace("\\\"", "\"");
					i = index;
					if (parent.isEmpty()) {
						json.put(key, value);
					} else {
						json.put(parent + '.' + key, value);
					}
					continue;
				}
				// 若值为对象
				// 去掉左花括号{后面可能存在的空格
				while (str.charAt(++i) == ' ') {}
				String newParent;
				if (parent.isEmpty()) {
					newParent = key;
				} else {
					newParent = parent + '.' + key;
				}
				// 用{}标记newParent的值为对象
				json.put(newParent, "{}");
				// 解析子串
				i += parseJSON(newParent, str.substring(i));
			}

		}
		return str.length();
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();
		scan.nextLine();

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			sb.append(scan.nextLine().trim());
		}

		parseJSON("", sb.toString());

		StringBuilder out = new StringBuilder();
		for (int i = 0; i < m; i++) {
			String key = scan.nextLine().trim();
			if (!json.containsKey(key)) {
				out.append("NOTEXIST\n");
			} else if (json.get(key) == "{}") {
				out.append("OBJECT\n");
			} else {
				out.append("STRING ").append(json.get(key)).append('\n');
			}
		}
		scan.close();

		System.out.println(out.toString());
	}
}

----------本文结束感谢您的阅读----------
坚持原创技术分享，您的支持将鼓励我继续创作！