progress

~/problems / Iterators & parsers / Parsers and interpreters

JSON parser and schema validator

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

hard assessment 3 levels ~75 min PinterestConfluent

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 more key: value pairs 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 either 0 alone or a digit from 1 to 9 followed by more digits. So +5, 007, -, 1.5 and 1e3 are all malformed.
  • true, false and null are 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.

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Topic: Parsers and interpreters. Tokenize, recursive descent, S-expressions, evaluation and type inference.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc