2759. 将 JSON 字符串转换为对象 🔒

🔴 🔗 力扣open in new window LeetCodeopen in new window

题目

Given a string str, return parsed JSON parsedStr. You may assume the str is a valid JSON string hence it only includes strings, numbers, arrays, objects, booleans, and null. str will not include invisible characters and escape characters.

Please solve it without using the built-in JSON.parse method.

Example 1:

Input: str = '{"a":2,"b":[1,2,3]}'
Output:
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:

str is a valid JSON string
1 <= str.length <= 10^5

题目大意

给定一个字符串 str ，返回 JSON 解析后的 parsedStr 。你可以假设 str 是一个有效的 JSON 字符串，因此它只包含字符串、数字、数组、对象、布尔值和 null。str 不会包含不可见字符和转义字符。

请在不使用内置的 JSON.parse 方法的情况下解决此问题。

示例 1：

输入： str = '{"a":2,"b":[1,2,3]}'
输出：
解释： 返回由 JSON 字符串表示的对象。

示例 2：

输入： str = 'true'
输出： true
解释： 原始类型是有效的 JSON。

示例 3：

输入： str = '[1,5,"false",{"a":2}]'
输出：[1,5,"false",{"a":2}]
解释： 返回由 JSON 字符串表示的数组。

提示：

str 是一个有效的 JSON 字符串
1 <= str.length <= 10^5

解题思路

要实现一个自定义的 JSON 解析器，可以利用递归逐步解析 JSON 字符串的各个部分。解析过程需要从头开始扫描字符串，识别出字符串、数字、对象、数组、布尔值和 null 的格式。

设置初始状态：
- 定义一个全局变量 i，用来指示当前正在解析的字符串 str 中的索引位置。
- jsonParse 的核心函数是 parseValue，用于识别当前字符并递归调用其他解析函数来处理不同的数据类型。
解析不同的数据类型：
- 布尔值 true：如果当前字符为 't'，调用 parseTrue，将指针 i 向前移动 4 个字符（true的长度），并返回 true。
- 布尔值 false：如果当前字符为 'f'，调用 parseFalse，将指针 i 向前移动 5 个字符（false的长度），并返回 false。
- 空值 null：如果当前字符为 'n'，调用 parseNull，将指针 i 向前移动 4 个字符（null的长度），并返回 null。
字符串解析：
- 如果当前字符为双引号 "，调用 parseString 函数。
- parseString 函数在起始位置跳过 "，然后循环读取字符，直到再次遇到 "，构造字符串并返回。
- 最后，指针 i 再次向前移动一位，跳过结尾的 "。
数字解析：
- 如果当前字符是 - 或数字字符，调用 parseNumber 函数。
- parseNumber 从当前指针位置开始检查字符，直到找到数字的结束位置，支持整数和小数格式。
- 最后，将数字部分转化为 Number 类型并返回。
对象解析：
- 如果当前字符是 {，调用 parseObject。
- parseObject 会构建一个空对象，然后在循环中依次解析键值对：
  - 调用 parseString 解析键名。
  - 跳过冒号 : 后，调用 parseValue 解析对应的值。
  - 遇到 , 时继续解析下一对键值对，遇到 } 表示对象解析结束。
- 空对象 {} 特殊情况：如果下一个字符直接是 }，则直接返回空对象。
数组解析：
- 如果当前字符是 [，调用 parseArray。
- parseArray 会构建一个空数组，然后在循环中依次解析每个元素：
  - 调用 parseValue 解析当前元素，并将结果加入数组。
  - 遇到 , 时继续解析下一个元素，遇到 ] 表示数组解析结束。
- 空数组 [] 特殊情况：如果下一个字符直接是 ]，则直接返回空数组。
控制流：
- parseValue 函数根据当前字符确定类型，调用不同的解析函数进行递归解析。
- 通过递归，每个数据类型函数会处理它们的嵌套情况，例如对象内的数组、数组内的对象等。

复杂度分析

时间复杂度：O(n)，其中 n 是 JSON 字符串的长度，每个字符在整个解析过程中只访问一次。
空间复杂度：O(d)，其中 d 是对象或数组的嵌套深度，递归调用栈的最大深度决定了所需的辅助空间。

代码

/**
 * @param {string} str
 * @return {null|boolean|number|string|Array|Object}
 */
var jsonParse = function (str) {
	let i = 0;
	// 解析布尔值 true
	const parseTrue = () => {
		i += 4;
		return true;
	};
	// 解析布尔值 false
	const parseFalse = () => {
		i += 5;
		return false;
	};
	// 解析空值 null
	const parseNull = () => {
		i += 4;
		return null;
	};
	// 解析字符串
	const parseString = () => {
		i++; // 跳过开始的双引号
		let result = '';
		while (str[i] !== '"') {
			result += str[i++];
		}
		i++; // 跳过结束的双引号
		return result;
	};
	// 解析数字
	const parseNumber = () => {
		let start = i;
		if (str[i] === '-') i++;
		while (isDigit(str[i])) i++;
		if (str[i] === '.') {
			i++;
			while (isDigit(str[i])) i++;
		}
		return Number(str.slice(start, i));
	};
	// 解析对象
	const parseObject = () => {
		i++; // 跳过开始的 '{'
		let obj = {};
		// 空对象的情况
		if (str[i] === '}') {
			i++;
			return obj;
		}
		while (true) {
			let key = parseString();
			i++; // 跳过冒号 ':'
			obj[key] = parseValue();
			if (str[i] === '}') {
				i++;
				break;
			}
			i++; // 跳过逗号 ','
		}
		return obj;
	};
	// 解析数组
	const parseArray = () => {
		i++; // 跳过左方括号 '['
		let arr = [];
		// 空数组的情况
		if (str[i] === ']') {
			i++;
			return arr;
		}
		while (true) {
			arr.push(parseValue());
			if (str[i] === ']') {
				i++;
				break;
			}
			i++; // 跳过逗号 ','
		}
		return arr;
	};

	const isDigit = (char) => {
		return char >= '0' && char <= '9';
	};

	const parseValue = () => {
		const c = str[i];
		if (c === '"') return parseString();
		if (c === '{') return parseObject();
		if (c === '[') return parseArray();
		if (c === 't') return parseTrue();
		if (c === 'f') return parseFalse();
		if (c === 'n') return parseNull();
		if (c === '-' || isDigit(c)) return parseNumber();
		throw new Error('Invalid JSON');
	};

	return parseValue();
};
let str = '{"a":2,"b":[1,2,3]}';
console.log(jsonParse(str));

2759. 将 JSON 字符串转换为对象 🔒

# 2759. 将 JSON 字符串转换为对象 🔒

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

2759. 将 JSON 字符串转换为对象 🔒

题目

题目大意

解题思路

复杂度分析

代码