1091 資料結構

題目說明

製作特定格式的 Json 資料搜尋器。
JSON（JavaScript Object Notation)，是一種輕量級的資料交換語言資料交換，該語言以易於讓人閱讀的文字為基礎，用來傳輸由屬性值或者序列性的值組成的資料物件。

JSON 的基本資料類型：

  1. 數值：十進位數，不能有前導 0，可以為負數，可以有小數部分。還可以用 e 表示指數部分。
  2. 字串：以雙引號 “” 括起來的零個或多個 Unicode 碼位。
  3. 布林值：表示為 true 或者 false。
  4. 值的有序列表（array）：有序的零個或者多個值。每個值可以為任意類型。序列表使用方括號 [] 括起來。元素之間用逗號,分割。形如：[value, value]
  5. 物件（object）：一個無序的「鍵(key)-值(value)對」(pair)，其中鍵是字串。物件以左花括號 { 開始，並以右花括號 } 結束。鍵(key)-值(value)對之間使用逗號分隔。鍵與值之間用冒號 : 分隔。
  6. null 類型：值寫為 null。

此作業需實作出可以使用特殊的搜尋表示式，並且搜尋到任何符合條件的資
料(value)。

Input

輸入資料為兩個檔案名稱。
ex: ./hw2.exe ex1_json.json ex1_search.txt
ex1_json.json 內包含一個 JSON document 和多行雜訊。雜訊行數為 1 行以上。順序必定為 JSON document 在上，雜訊在下。

範例輸入:

ex1_json.json

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
{
 "name": "Jackson",
 "age": 18,
 "boyfriends": [
 {
 "name": "Scott",
 "age": 19
 },
 {
 "name": "Joe",
 "age": 20
 }
 ],
 "numbers": [
 1,2,3,4
 ]
}
asdfjoiasj--- 包含此行以下皆是雜訊---oruhgwergnv{
dahffsdlfhaljshf()jdoasjd%@^*jhflsdfhhljrh}
_01-1249=asdfjapsdjfpsidjfjpaijfspdfjapsidjfsdf
---雜訊格式行數為一行以上---

ex1_search.txt

1
2
3
4
name
boyfriends>name
a>b>c
numbers

ex1_search.txt 內包含多行測資，每一行文字都是一筆獨立的搜尋表示式。格式
是由一個至多個 key string 組成，key strings 之間由 > 隔開。 > 符號表示下一層。
每一筆搜尋表示式皆會指向一個或多個 leaf 節點，其形態為數值、字串、布林直或 null，並不會指向 object。

Output

輸出詳細說明：

  1. 每一筆搜尋表示式之間的輸出須由換行隔開。
  2. 依照每一筆搜尋表示式輸出任何在 json 檔案中符合的資料。
  3. 當輸出有多項 value 時，需換行輸出。
  4. 下方的 Jackson, Scott, Joe 都可以藉由搜尋表示式「name」，搜尋到，所以分行輸出相對應的 value。
  5. boyfriends 下一層的 name 只有兩個名字，所以輸出只會有 Scott,Joe 兩行。
  6. 範例中 key 為 numbers 時，因對應到 array 資料型態，所以輸出時需要分行輸出 array 中的值。
  7. value 為 null, true, false, 數字型態, 字串型態時，直接輸出。
  8. 若無法依照搜尋表示式查詢到任何 value，輸出空白行。

ex1 answer console

1
2
3
4
5
6
7
8
9
10
11
12
13
Jackson
Scott
Joe

Scott
Joe



1
2
3
4

解題思路

利用json檔的特性來判斷，將json檔一層一層剝開。

參考解法

以下解法還有些許的bug，請警慎參考!

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <sstream>
#include <iomanip>

using namespace std;

void noise(string& file)
{
	int ignore1 = 0;
	bool ignore = false;
	int count = 0;
	int i = 0;
	for (; i < file.size(); i++)
	{
		if (file[i] == '"')
		{
			ignore1++;
			if (ignore1 % 2 != 0)
			{
				ignore = true;
			}
			else
			{
				ignore = false;
			}
		}
		if (ignore)
		{
			continue;
		}
		else if (file[i] == '{')
		{
			count++;
		}
		else if (file[i] == '}')
		{
			count--;
			if (count == 0)
			{
				file = file.substr(0, i + 1);
				break;
			}
		}
	}
}

void notjson(string& file)
{
	int ignore = 0;
	for (int i = 0; i < file.size(); i++)
	{
		if (file[i] == '"' && file[i - 1] != '\\')
		{
			ignore++;
		}
		else if (file[i] == '\n' || file[i] == '\r' || file[i] == ' ' && ignore % 2 == 0)
		{
			file.erase(i, 1);
			i--;
		}
	}
}

int findend(int i, string& file)
{
	for (; i < file.size(); i++)
	{
		if (file[i] == ',' || file[i] == '}' || file[i] == '"' || file[i] == ']')
		{
			return i - 1;
		}/*
		else if (file[i] == '\n')
		{
			if (file[i + 1] == ',' || file[i + 1] == '}')
			{
				return i - 1;
			}
		}*/
	}
}

int main(int argc, char* argv[])
{
	ifstream fin1;
	ifstream fin2;
	  fin1.open("case2.json");
	fin2.open("search2.txt");
	//fin1.open(argv[1]);
	//fin2.open(argv[2]);

	stringstream strStream;
	strStream << fin1.rdbuf();
	string file = strStream.str();
	noise(file);
	notjson(file);
	string line;
	vector <string> search;
	vector <string> json;
	vector <vector <string>> ans;

	while (getline(fin2, line))
	{
		search.push_back(line);
	}

	int layer = 0;
	for (int i = 0; i < file.size(); i++)
	{
		if (file[i] == '{')
		{
			layer++;
		}
		else if (file[i] == '}')
		{
			layer--;
		}
		else if (file[i] == '"')
		{
			if (json.size() >= layer)
			{
				ans.push_back(json);

				while (json.size() >= layer && json.size() != 0)
				{
					json.pop_back();
				}
			}

			string key;
			int end = file.find('"', i + 1);
			while (file[end - 1] == '\\')
			{
				end = file.find('"', end + 1);
			}
			key = file.substr(i + 1, end - i - 1);
			json.push_back(key);

			if (file[end + 2] == '"')
			{
				int head = end + 3;
				int tail = file.find('"', head + 1);
				while (file[tail - 1] == '\\')
				{
					tail = file.find('"', tail + 1);
				}
				json.push_back(file.substr(head, tail - head));
				i = tail;
			}
			else if (file[end + 2] == '{')
			{
				layer++;
				i = end + 2;
			}
			else if (file[end + 2] == '[')
			{
				if (file[end + 3] == '{')
				{
					layer++;
					i = end + 3;
				}
				else
				{
					int tail = file.find(']', end + 3);	

					if (tail == end + 3)
					{
						json.pop_back();
					}
					else
					{
						int head = end + 3;
						for (int k = 0; head + k < file.size(); k++)
						{
							if (file[k + head] == ',')
							{
								string str = file.substr(head, k);
								if (str[0] == '"')
								{
									str = str.substr(1, str.length() - 2);
								}
								json.push_back(str);
								ans.push_back(json);
								json.pop_back();
								head = head + k + 1;
								k = 0;

							}
							else if (file[k + head] == ']')
							{
								string str = file.substr(head, k);
								if (str[0] == '"')
								{
									str = str.substr(1, str.length() - 2);
								}
								json.push_back(str);
								break;
							}
						}
					}

					i = tail;
				}
			}
			else
			{
				int head = end + 2;
				int tail = findend(head, file);
				key = file.substr(head, tail - head + 1);
				json.push_back(key);
				key.clear();
				i = tail;
			}
		}
	}
	ans.push_back(json);

	vector<vector <string>> jsonsearch;

	for (int i = 0; i < ans.size(); i++)
	{
		vector <string> temp;
		if (ans[i].size() == 0)
		{
			continue;
		}
		string data = {};
		for (int j = 0; j < ans[i].size() - 1; j++)
		{
			if (j == 0)
			{
				data = ans[i][j];
			}
			else
			{
				data += '>';
				data += ans[i][j];
			}
		}
		temp.push_back(data);
		temp.push_back(ans[i][ans[i].size() - 1]);
		jsonsearch.push_back(temp);
	}

	/*for (int i = 0; i < jsonsearch.size(); i++)
	{
		for (int j = 0; j < jsonsearch[i].size(); j++)
		{
			cout << jsonsearch[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;*/

	for (int i = 0; i < search.size(); i++)
	{
		bool find = false;
		for (int j = 0; j < jsonsearch.size(); j++)
		{
			if (jsonsearch[j][0].find(search[i], 0) != -1)
			{
				find = true;
				cout << jsonsearch[j][1] << endl;
			}
		}
		if (!find)
		{
			cout << endl;
		}
		if (i == search.size() - 1)
		{
			break;
		}
		cout << endl;
	}
}