2759. Convert JSON String to Object
Problem Description
The given LeetCode problem asks us to write a function that takes a string str
as input and returns parsedStr
, which is the result of parsing str
as JSON. The input string is guaranteed to be a valid JSON string, meaning it will only contain values that are valid JSON types such as strings, numbers, arrays, objects, booleans, or null. It is also specified that the string lacks invisible and escape characters, and string values within the JSON contain only alphanumeric characters. An essential constraint is that we must implement this parsing functionality without using the built-in JSON.parse
function.
Intuition
To solve this problem, we need to understand the structure of a JSON string. JSON (JavaScript Object Notation) is a lightweight data interchange format that is easy for humans to read and write and easy for machines to parse and generate. A JSON object consists of key-value pairs enclosed in curly braces {}
, an array is an ordered list of values enclosed in square brackets []
, and values can be a string, number, object, array, boolean (true
/false
), or null
.
Our solution approach is, therefore, to define a parser that can recognize and handle each of these cases. We do this through recursive descent parsing, which is a common technique used to parse expressions and structured text. The parser contains functions to handle each type of value that can be encountered:
parseTrue
,parseFalse
, andparseNull
recognize and handle the respective literalstrue
,false
, andnull
.parseNumber
recognizes sequences of digits, possibly including a minus sign and decimal point, which constitute a number.parseString
handles quoted sequences of characters, which represent strings in JSON.parseArray
checks for a list of values enclosed in square brackets[]
and parses each value in the list.parseObject
looks for key-value pairs enclosed in curly brackets{}
and parses each key (which will be a string) and each value (which could be any JSON data type).parseValue
is a helper function that determines which of the above functions to call based on the current character of the input string.
We maintain an index i
which points to the current character in the string being parsed. As we parse elements of the string, we advance i
to move through the string. When a parse function is called, it processes its part of the string and returns the appropriate JavaScript value (object
, array
, string
, number
, boolean
, or null
). The main parsing function, parseValue
, delegates to the other functions based on the initial character(s) of the current element being parsed, allowing us to recursively construct the data structure that represents the JSON input.
The parser's functions collectively read through the input string, interpret the structure using the rules of JSON syntax, and construct an in-memory representation (like what JSON.parse
does). The assumption that the input string is valid JSON and does not contain invisible characters or escape characters (aside from those in strings) simplifies the parser's implementation since it does not need to handle error cases or deal with such complexities. The result is an efficient parser that uses a straightforward approach to convert a JSON string representation into the corresponding JavaScript data structure.
Solution Approach
The solution for parsing a JSON string without using the built-in JSON.parse
method involves a technique called recursive descent parsing. This technique consists of a collection of functions that "descend" through the grammar of the inputāin this case, the JSON structureāprocessing each piece as it appears. Below is the explanation of the various parts of the solution:
-
Variables: An index
i
is used to keep track of the current position within the stringstr
. The length of the input string is stored inn
. -
Parsing Boolean and Null Values: The functions
parseTrue
,parseFalse
, andparseNull
check for the literal valuestrue
,false
, andnull
, respectively, and update the indexi
to move past the parsed value. -
Parsing Numbers: The function
parseNumber
accumulates in a strings
the consecutive characters that make up a number until it encounters a delimiter (a comma,
, a closing brace}
, or a closing bracket]
). It then convertss
to a number usingNumber(s)
. -
Parsing Strings:
parseString
processes characters within double quotes"
. It handles potentially escaped characters by checking for backslashes\
and advancing the index accordingly. Once it finds the closing double quote, it returns the accumulated string and advances the index past the quote. -
Parsing Arrays: The
parseArray
function creates an array, advances past the opening bracket[
, and continues until it encounters the closing bracket]
. For every element it finds (separated by commas), it callsparseValue
to parse that element and adds the result to the array. -
Parsing Objects: Similarly,
parseObject
creates an object, advances past the opening brace{
, and loops until it reaches the closing brace}
. It looks for string keys, followed by a colon:
, and then parses the value associated with that key. Each key-value pair is added to the object. -
Making Decisions:
parseValue
is the central function that determines the type of the next value in the JSON string by looking at the current character: an object if it's{
, an array if it's[
, a string if it's"
, a boolean literaltrue
orfalse
if it starts witht
orf
,null
if it starts withn
, and a number for anything else (typically a digit or a minus). -
Recursion and Looping: Both arrays and objects may contain nested structures (arrays within arrays, objects within objects, etc.). The recursive calls to
parseValue
enable the function to handle arbitrary depths of nesting. Loops allow parsing through multiple keys in an object or multiple values in an array. -
Ending the Parsing: Each helper parsing function advances the index
i
past the parsed value to the next relevant character in the input string, or to the end of the string.parseValue
is called initially to start the parsing process. Once all the characters are processed, the top-level parsed structure is returned.
Algorithmically, the solution uses simple control structures (if-else, while loops) to navigate and recognize patterns in the input string. Recursion is a key component that simplifies the handling of nested structures. This implementation can be characterized by its linear time complexity because it processes each character in the input exactly once (or slightly more in the case of backtracking during recursive calls).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take an example of a JSON string to illustrate the solution approach. We will use the following simple JSON string for our walkthrough:
"{"name":"John","age":30,"isStudent":false}"
-
Initialize the variables: The index
i
starts at 0, and we'll store the length of the string in variablen
. -
The first character is
{
, indicating that we need to parse an object. We callparseObject
to handle this. -
In
parseObject
, we skip past the opening{
and look for the first key. The next set of characters""name":""
are processed byparseString
, which will return the key name "name". We then skip the colon and callparseValue
to determine the type of value. -
parseValue
sees the opening quote"
, indicating a string value. It then callsparseString
to process the characters"John"
. The result "John" is stored as the value for the key "name". -
We then move past the comma to the next key-value pair, with
parseString
handling the""age":""
which returns "age" as the key. -
The next character is
3
, indicating a number value.parseNumber
is called and processes30
, then returns it as the value for the key "age". -
We continue past the comma to the next key
"isStudent"
, and after the colon, we encounterfalse
.parseFalse
is called and returnsfalse
as the value for the key "isStudent". -
Finally, we find the closing
}
, so we conclude the object parsing. -
At this point,
i
has reached the end of the input string, and the entire JSON string has been successfully parsed into a JavaScript object.
The functions work together to interpret input string sections and construct a data structure that mirrors what you would get from JSON.parse
. Each component of the JSON structure is handled by a specialized function that delegates to other functions as needed, ensuring that the entire structure is parsed correctly, regardless of nesting level or complexity. The final output we obtain is the following JavaScript object:
{ "name": "John", "age": 30, "isStudent": false }
This step-by-step process showcases recursion and orderly parsing of each JSON element using the helper functions without ever needing to invoke JSON.parse
.
Solution Implementation
1def json_parse(json_str):
2 length = len(json_str)
3 index = 0
4
5 def parse_true():
6 # Parses a literal `true` value
7 nonlocal index
8 index += 4
9 return True
10
11 def parse_false():
12 # Parses a literal `false` value
13 nonlocal index
14 index += 5
15 return False
16
17 def parse_null():
18 # Parses a literal `null` value
19 nonlocal index
20 index += 4
21 return None
22
23 def parse_number():
24 # Parses a number value
25 nonlocal index
26 num_str = ''
27 while index < length:
28 char = json_str[index]
29 if char in [',', '}', ']']:
30 break
31 num_str += char
32 index += 1
33 return float(num_str)
34
35 def parse_array():
36 # Parses an array value
37 nonlocal index
38 array = []
39 index += 1 # Skip past the opening bracket '['
40
41 while index < length:
42 char = json_str[index]
43 if char == ']':
44 index += 1 # Skip past the closing bracket ']'
45 break
46 if char == ',':
47 index += 1 # Skip past the comma
48 continue
49
50 value = parse_value()
51 array.append(value)
52
53 return array
54
55 def parse_string():
56 # Parses a string value
57 nonlocal index
58 string_val = ''
59 index += 1 # Skip past the opening quote '"'
60
61 while index < length:
62 char = json_str[index]
63
64 if char == '"':
65 index += 1 # Skip past the closing quote '"'
66 break
67
68 if char == '\\':
69 index += 1 # Skip past the escape character '\'
70 string_val += json_str[index]
71 else:
72 string_val += char
73
74 index += 1
75
76 return string_val
77
78 def parse_object():
79 # Parses an object value
80 nonlocal index
81 obj = {}
82 index += 1 # Skip past the opening curly brace '{'
83
84 while index < length:
85 char = json_str[index]
86 if char == '}':
87 index += 1 # Skip past the closing curly brace '}'
88 break
89
90 if char == ',':
91 index += 1 # Skip past the comma
92 continue
93
94 key = parse_string()
95 index += 1 # Skip past the colon
96 value = parse_value()
97 obj[key] = value
98
99 return obj
100
101 def parse_value():
102 # Determines the appropriate parse function based on the current character
103 nonlocal index
104 char = json_str[index]
105
106 if char == '{':
107 return parse_object()
108 elif char == '[':
109 return parse_array()
110 elif char == '"':
111 return parse_string()
112 elif char == 't':
113 return parse_true()
114 elif char == 'f':
115 return parse_false()
116 elif char == 'n':
117 return parse_null()
118 else:
119 return parse_number()
120
121 # Initiates the parsing process
122 return parse_value()
123
1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5
6public class JsonParser {
7
8 // Entry method to parse a JSON string
9 public static Object jsonParse(String str) {
10 final int length = str.length();
11 int[] index = new int[] { 0 };
12
13 return parseValue(str, length, index);
14 }
15
16 // Parses a boolean `true` value
17 private static boolean parseTrue(String str, int length, int[] index) {
18 index[0] += 4;
19 return true;
20 }
21
22 // Parses a boolean `false` value
23 private static boolean parseFalse(String str, int length, int[] index) {
24 index[0] += 5;
25 return false;
26 }
27
28 // Parses a null value
29 private static Object parseNull(String str, int length, int[] index) {
30 index[0] += 4;
31 return null;
32 }
33
34 // Parses a number value
35 private static Number parseNumber(String str, int length, int[] index) {
36 StringBuilder numStr = new StringBuilder();
37 while (index[0] < length) {
38 char ch = str.charAt(index[0]);
39 if (ch == ',' || ch == '}' || ch == ']') {
40 break;
41 }
42 numStr.append(ch);
43 index[0]++;
44 }
45 return Double.parseDouble(numStr.toString()); // Number is assumed to be a double
46 }
47
48 // Parses an array value
49 private static List<Object> parseArray(String str, int length, int[] index) {
50 List<Object> array = new ArrayList<>();
51 index[0]++; // Skip past the opening bracket '['
52
53 while (index[0] < length) {
54 char ch = str.charAt(index[0]);
55 if (ch == ']') {
56 index[0]++; // Skip past the closing bracket ']'
57 break;
58 }
59
60 if (ch == ',') {
61 index[0]++; // Skip past the comma
62 continue;
63 }
64
65 Object value = parseValue(str, length, index);
66 array.add(value);
67 }
68
69 return array;
70 }
71
72 // Parses a string value
73 private static String parseString(String str, int length, int[] index) {
74 StringBuilder stringVal = new StringBuilder();
75 index[0]++; // Skip past the opening quote '"'
76
77 while (index[0] < length) {
78 char ch = str.charAt(index[0]);
79
80 if (ch == '"') {
81 index[0]++; // Skip past the closing quote '"'
82 break;
83 }
84
85 if (ch == '\\') {
86 index[0]++; // Skip past the escape character '\'
87 stringVal.append(str.charAt(index[0]));
88 } else {
89 stringVal.append(ch);
90 }
91
92 index[0]++;
93 }
94
95 return stringVal.toString();
96 }
97
98 // Parses an object value
99 private static Map<String, Object> parseObject(String str, int length, int[] index) {
100 Map<String, Object> object = new HashMap<>();
101 index[0]++; // Skip past the opening curly brace '{'
102
103 while (index[0] < length) {
104 char ch = str.charAt(index[0]);
105 if (ch == '}') {
106 index[0]++; // Skip past the closing curly brace '}'
107 break;
108 }
109
110 if (ch == ',') {
111 index[0]++; // Skip past the comma
112 continue;
113 }
114
115 String key = parseString(str, length, index);
116 index[0]++; // Skip past the colon
117 Object value = parseValue(str, length, index);
118 object.put(key, value);
119 }
120
121 return object;
122 }
123
124 // Determines the appropriate parse function based on the current character
125 private static Object parseValue(String str, int length, int[] index) {
126 char ch = str.charAt(index[0]);
127 switch (ch) {
128 case '{':
129 return parseObject(str, length, index);
130 case '[':
131 return parseArray(str, length, index);
132 case '"':
133 return parseString(str, length, index);
134 case 't':
135 return parseTrue(str, length, index);
136 case 'f':
137 return parseFalse(str, length, index);
138 case 'n':
139 return parseNull(str, length, index);
140 default:
141 return parseNumber(str, length, index);
142 }
143 }
144}
145
1#include <string>
2#include <cctype>
3
4// JSON parser in C++
5class JSONParser {
6private:
7 std::string str; // the JSON string to be parsed
8 size_t length; // the length of the JSON string
9 size_t index; // the current index in the JSON string
10
11 // Parses a literal `true` value
12 bool parseTrue() {
13 index += 4;
14 return true;
15 }
16
17 // Parses a literal `false` value
18 bool parseFalse() {
19 index += 5;
20 return false;
21 }
22
23 // Parses a literal `null` value
24 std::nullptr_t parseNull() {
25 index += 4;
26 return nullptr;
27 }
28
29 // Parses a number value
30 double parseNumber() {
31 std::string numStr;
32 while (index < length) {
33 char currentChar = str[index];
34 // Stop parsing if a comma, closing brace, or closing bracket is found
35 if (currentChar == ',' || currentChar == '}' || currentChar == ']') {
36 break;
37 }
38 numStr += currentChar;
39 index++;
40 }
41 return std::stod(numStr); // Convert string to double
42 }
43
44 // Parses an array value
45 std::vector<any> parseArray() {
46 std::vector<any> array;
47 index++; // skip past the opening bracket '['
48
49 while (index < length && str[index] != ']') {
50 if (str[index] == ',') {
51 index++; // skip past the comma
52 } else {
53 array.push_back(parseValue());
54 }
55 }
56
57 index++; // skip past the closing bracket ']'
58 return array;
59 }
60
61 // Parses a string value
62 std::string parseString() {
63 std::string stringVal;
64 index++; // skip past the opening quote '"'
65
66 while (index < length) {
67 char currentChar = str[index];
68
69 if (currentChar == '"') {
70 index++; // skip past the closing quote '"'
71 break;
72 }
73
74 // handle escaped characters
75 if (currentChar == '\\') {
76 index++; // skip past the escape character '\'
77 stringVal += str[index];
78 } else {
79 stringVal += currentChar;
80 }
81
82 index++;
83 }
84
85 return stringVal;
86 }
87
88 // Parses an object value
89 std::map<std::string, any> parseObject() {
90 std::map<std::string, any> object;
91 index++; // skip past the opening curly brace '{'
92
93 while (index < length && str[index] != '}') {
94 if (str[index] == ',') {
95 index++; // skip past the comma
96 } else {
97 std::string key = parseString();
98 index++; // skip past the colon
99 any value = parseValue();
100 object[key] = value;
101 }
102 }
103
104 index++; // skip past the closing curly brace '}'
105 return object;
106 }
107
108 // Determines the appropriate parse function based on the current character
109 any parseValue() {
110 char currentChar = str[index];
111 switch(currentChar) {
112 case '{': return parseObject();
113 case '[': return parseArray();
114 case '"': return parseString();
115 case 't': return parseTrue();
116 case 'f': return parseFalse();
117 case 'n': return parseNull();
118 default: return parseNumber();
119 }
120 }
121
122public:
123 any jsonParse(const std::string& jsonString) {
124 this->str = jsonString;
125 this->length = jsonString.length();
126 this->index = 0;
127
128 // Initiates the parsing process
129 return parseValue();
130 }
131};
132
133// Usage example:
134// JSONParser parser;
135// any result = parser.jsonParse("{\"key\": [true, false, null, 123]}");
136
1function jsonParse(str: string): any {
2 const length = str.length;
3 let index = 0;
4
5 // Parses a literal `true` value
6 function parseTrue(): boolean {
7 index += 4;
8 return true;
9 }
10
11 // Parses a literal `false` value
12 function parseFalse(): boolean {
13 index += 5;
14 return false;
15 }
16
17 // Parses a literal `null` value
18 function parseNull(): null {
19 index += 4;
20 return null;
21 }
22
23 // Parses a number value
24 function parseNumber(): number {
25 let numStr = '';
26 while (index < length) {
27 const char = str[index];
28 if (char === ',' || char === '}' || char === ']') {
29 break;
30 }
31 numStr += char;
32 index++;
33 }
34 return Number(numStr);
35 }
36
37 // Parses an array value
38 function parseArray(): any[] {
39 const array: any[] = [];
40 index++; // Skip past the opening bracket '['
41
42 while (index < length) {
43 const char = str[index];
44 if (char === ']') {
45 index++; // Skip past the closing bracket ']'
46 break;
47 }
48
49 if (char === ',') {
50 index++; // Skip past the comma
51 continue;
52 }
53
54 const value = parseValue();
55 array.push(value);
56 }
57
58 return array;
59 }
60
61 // Parses a string value
62 function parseString(): string {
63 let stringVal = '';
64 index++; // Skip past the opening quote '"'
65
66 while (index < length) {
67 const char = str[index];
68
69 if (char === '"') {
70 index++; // Skip past the closing quote '"'
71 break;
72 }
73
74 if (char === '\\') {
75 index++; // Skip past the escape character '\'
76 stringVal += str[index];
77 } else {
78 stringVal += char;
79 }
80
81 index++;
82 }
83
84 return stringVal;
85 }
86
87 // Parses an object value
88 function parseObject(): any {
89 const object: any = {};
90 index++; // Skip past the opening curly brace '{'
91
92 while (index < length) {
93 const char = str[index];
94 if (char === '}') {
95 index++; // Skip past the closing curly brace '}'
96 break;
97 }
98
99 if (char === ',') {
100 index++; // Skip past the comma
101 continue;
102 }
103
104 const key = parseString();
105 index++; // Skip past the colon
106 const value = parseValue();
107 object[key] = value;
108 }
109
110 return object;
111 }
112
113 // Determines the appropriate parse function based on the current character
114 function parseValue():