1091 資料結構
題目說明 製作特定格式的 Json 資料搜尋器。 JSON(JavaScript Object Notation),是一種輕量級的資料交換語言資料交換,該語言以易於讓人閱讀的文字為基礎,用來傳輸由屬性值或者序列性的值組成的資料物件。
JSON 的基本資料類型:
數值:十進位數,不能有前導 0,可以為負數,可以有小數部分。還可以用 e 表示指數部分。
字串:以雙引號 “” 括起來的零個或多個 Unicode 碼位。
布林值:表示為 true 或者 false。
值的有序列表(array):有序的零個或者多個值。每個值可以為任意類型。序列表使用方括號 [] 括起來。元素之間用逗號,分割。形如:[value, value]
物件(object):一個無序的「鍵(key)-值(value)對」(pair),其中鍵是字串。物件以左花括號 { 開始,並以右花括號 } 結束。鍵(key)-值(value)對之間使用逗號分隔。鍵與值之間用冒號 : 分隔。
null 類型:值寫為 null。
此作業需實作出可以使用特殊的搜尋表示式,並且搜尋到任何符合條件的資 料(value)。
輸入資料為兩個檔案名稱。 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 輸出詳細說明:
每一筆搜尋表示式之間的輸出須由換行隔開。
依照每一筆搜尋表示式輸出任何在 json 檔案中符合的資料。
當輸出有多項 value 時,需換行輸出。
下方的 Jackson, Scott, Joe 都可以藉由搜尋表示式「name」,搜尋到,所以分行輸出相對應的 value。
boyfriends 下一層的 name 只有兩個名字,所以輸出只會有 Scott,Joe 兩行。
範例中 key 為 numbers 時,因對應到 array 資料型態,所以輸出時需要分行輸出 array 中的值。
value 為 null, true, false, 數字型態, 字串型態時,直接輸出。
若無法依照搜尋表示式查詢到任何 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 ; } } } int main (int argc, char * argv[]) { ifstream fin1; ifstream fin2; fin1.open ("case2.json" ); fin2.open ("search2.txt" ); 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 < 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; } }