Level 1 Parse JSON by hand
A service takes JSON documents from clients and checks them against a schema before storing them. Over three levels you'll build both halves yourself, starting with the parser.
Implement parse_json(text: str). It reads a restricted form of JSON and returns the matching Python value:
| JSON | Example | Python |
|---|---|---|
| object | {"a": 1, "b": [true]} |
dict |
| array | [1, "x", null] |
list |
| string | "hi\n" |
str |
| integer | -12 |
int |
true, false |
True, False |
|
null |
None |
The rules. Anything that breaks one of them is malformed: raise ValueError.
- Whitespace (space, tab, newline, carriage return) may appear before or after any value, and around
:and,. - An object is
{, then zero or morekey: valuepairs separated by commas, then}. Every key is a string. The same key may not appear twice in one object. - An array is
[, then zero or more values separated by commas, then]. A comma must sit between two values:[1,]and[,1]are malformed. - A string is text between double quotes. Inside it, any character is allowed except
",\and control characters (codes below 32, such as a raw newline or tab). A backslash starts an escape, and only these eight exist:\"\\\/\b\f\n\r\t. There is no\u. - An integer is an optional
-, then either0alone or a digit from 1 to 9 followed by more digits. So+5,007,-,1.5and1e3are all malformed. true,falseandnullare written exactly so, in lower case.- The text holds exactly one value. Only whitespace may follow it, and an empty text is malformed.
Don't use the json module, eval or any other ready-made parser. A test checks your imports.
parse_json('{"name": "Ana", "tags": ["a", "b"], "age": 31, "admin": false, "boss": null}')
# {"name": "Ana", "tags": ["a", "b"], "age": 31, "admin": False, "boss": None}
parse_json(' [ 1 , -20 , [ ] , { } ] ') # [1, -20, [], {}]
parse_json('"tab\\there"') # "tab\there" (the escape \t becomes a real tab)
parse_json('0') # 0
parse_json('[1, 2,]') # ValueError: no value after the comma
parse_json('{"a": 1, "a": 2}') # ValueError: duplicate key
parse_json('012') # ValueError: leading zero
parse_json('{"a": 1} x') # ValueError: text after the value
Texts are up to 2 × 10^5 characters long, values nest at most 100 levels deep, and every integer fits in a signed 64-bit integer. In C++ and Java the starter describes the value type to return.
⭐ Bonus: a speed test on a 200,000-character document earns a star in O(n). Cutting the text down as you go (text = text[1:]) copies it every time and is O(n²).
Show hint
write one function per kind of value. Each takes the index where its value starts and returns the value together with the index right after it, so you never copy the text. Look at the first character to decide which function to call: {, [, ", a digit or -, or a letter.