Problem Statement
Given a string str, the task is to return parsedStr, which represents the JSON object constructed from the string representation. The string str is guaranteed to represent a valid JSON object and includes data types such as strings, numbers, arrays, objects, booleans, and null. It has been specified that str does not contain any invisible characters or escape sequences. Crucially, the solution must be implemented without utilizing the built-in JSON.parse method, requiring a manual parsing approach.
Examples
Example 1
Input:
str = '{"a":2,"b":[1,2,3]}'Output:
{"a":2,"b":[1,2,3]}Explanation:
Returns the object represented by the JSON string.
Example 2
Input:
str = 'true'
Output:
true
Explanation:
Primitive types are valid JSON.
Example 3
Input:
str = '[1,5,"false",{"a":2}]'Output:
[1,5,"false",{"a":2}]Explanation:
Returns the array represented by the JSON string.
Constraints
stris a valid JSON string1 <= str.length <= 105
Approach and Intuition
Parsing a JSON string manually requires interpreting the textual format of JSON and converting it into respective JavaScript objects. Here’s how to approach this problem:
Recognize the type of data structure initially represented by the string—whether it primarily encloses an object
{}or an array[]. This determination guides the parsing process.Implement a state machine or recursive parsing technique that can handle nested structures:
- Determine if the current segment of the string represents an object, an array, a number, a boolean, a string, or null.
- For objects, parse pair-wise looking for keys and their corresponding values until the closing brace is encountered.
- For arrays, sequentially read array elements until the closing bracket is found.
- For primitive types (strings, numbers, booleans, null), directly convert the read segments into JavaScript primitives based on their recognizable format (e.g., boolean true or false, numeric formats, etc.).
Handling specific character sequences that denote different data types or control structures:
- Quotation marks
"indicate the start and end of a string. - Commas
,divide elements in arrays or key-value pairs in objects. - Colons
:separate keys from values in objects. - Brackets
[]& braces{}are used to denote the boundaries of arrays and objects, respectively.
- Quotation marks
For recursive implementation, use functions that call themselves when they encounter nested arrays or objects until the deepest levels are parsed and then unwind to construct the full data structure.
Validate input data correctly to avoid errors during parsing, considering the constraints and ensuring no unexpected data breaks the parser.
By following these steps and carefully organizing the parsing logic to recognize and handle various components of a JSON string, it’s possible to manually decode JSON strings into their corresponding JavaScript objects or arrays. Each step crucially depends on correctly identifying and processing parts of the string based on JSON syntax rules.
Solutions
- JavaScript
var parseJson = function(inputStr) {
const totalLength = inputStr.length;
const elementsStack = [];
let currentElement = null;
let mainElement = null;
let objectKey = null;
for(let index = 0; index < totalLength; index++){
if(inputStr[index] === ",") continue;
switch(inputStr[index]) {
case '[':
case '{':
const newElement = inputStr[index] === '[' ? [] : {};
if (mainElement === null) mainElement = newElement;
if (currentElement !== null) {
if (Array.isArray(currentElement)) {
currentElement.push(newElement);
} else {
currentElement[objectKey] = newElement;
objectKey = null;
}
}
elementsStack.push(currentElement);
currentElement = newElement;
break;
case ']':
case '}':
currentElement = elementsStack.pop();
break;
default:
let value = null;
if(inputStr[index] === '"') {
let subIndex = index + 1;
while(subIndex < totalLength && inputStr[subIndex] !== '"') subIndex++;
value = inputStr.substring(index + 1, subIndex);
index = subIndex;
} else if(inputStr[index] === '-' || (inputStr[index] >= '0' && inputStr[index] <= '9')) {
let subIndex = index;
while(subIndex + 1 < totalLength && (inputStr[subIndex + 1] === '-' ||
(inputStr[subIndex + 1] >= '0' && inputStr[subIndex + 1] <= '9') ||
inputStr[subIndex + 1] === '.')) {
subIndex++;
}
value = Number(inputStr.substring(index, subIndex + 1));
index = subIndex;
} else {
if(index + 4 <= totalLength && inputStr.substring(index, index + 4) === "true") {
value = true;
index += 3;
} else if(index + 5 <= totalLength && inputStr.substring(index, index + 5) === "false") {
value = false;
index += 4;
} else {
value = null;
index += 3;
}
}
if (mainElement === null) mainElement = value;
if (inputStr[index + 1] === ':') {
objectKey = value;
index++;
} else if(Array.isArray(currentElement)) {
currentElement.push(value);
} else if(objectKey !== null) {
currentElement[objectKey] = value;
objectKey = null;
} else {
currentElement = value;
}
break;
}
}
return mainElement;
};
In this JavaScript solution, you will process a JSON-formatted string and convert it to a JavaScript object or array. The process uses an iterative method by looping through each character in the string and handling different data types and structures (arrays, objects, numbers, booleans, and null values).
The key steps involved in the solution include:
- Initialize control variables, including a
totalLengthfor the string's length,elementsStackto manage nested objects and arrays, andcurrentElementto keep track of the current position within the nested structures. - Use a for-loop to iterate over the input string, character by character, making decisions based on the encountered character.
- Handle object and array opening characters (
{and[), creating a new object or array and updating the stack and current element. - Manage closing characters (
}and]) by popping from the stack to update the current element to its parent element. - Process primitive data values (strings, numbers, booleans, and null) by identifying the value start and end points within the string, then converting and assigning them appropriately within the current object or array.
- Handle object and array opening characters (
- Handle colon (
:) characters to set up keys for objects. - Complete the loop and return the fully constructed
mainElement, which represents the parsed JSON as a JavaScript object or array structure.
This approach skips any commas (,) as they don't impact the data structure and leverages both stacks for maintaining hierarchy and appropriately scoped variables for data conversion and association. The function ensures elements within the JSON string are correctly structured into their corresponding JavaScript representations, supporting nested and complex objects and arrays.
No comments yet.