0385. Mini Parser ================= 题目信息 -------- :题号: 0385 :难度: Medium :主题: 序列化字符串、嵌套列表、有符号整数、结构恢复 :原题: `LeetCode 0385 `_ :重点: 输入可能是单个整数或列表、括号层级和元素顺序必须保留、允许负数与空嵌套列表 题目重述 -------- 给定一个合法字符串 ``s``,它序列化表示一个 ``NestedInteger``:字符串可能直接是一个有符号整数,也可能是由方括号包围、逗号分隔的嵌套整数列表。需要把字符串反序列化为具有相同整数值、嵌套层级和元素顺序的 ``NestedInteger`` 对象。 ``s`` 的长度位于 ``[1, 5 * 10^4]``,只包含数字、负号、方括号和逗号,不包含空格。所有整数位于 ``[-10^6, 10^6]``,输入保证语法有效。单独的整数应得到整数对象,而不是包含一个元素的列表。 自建示例 -------- 单独的负整数: .. code-block:: text 输入:s = "-12" 输出:表示整数 -12 的 NestedInteger 解释:输入没有外层方括号,因此结果本身是整数,不是列表。 包含空列表的多层结构: .. code-block:: text 输入:s = "[7,[-2,3],[]]" 输出:表示 [7,[-2,3],[]] 的 NestedInteger 解释:三个顶层元素的顺序保持不变,第二个元素是嵌套列表,第三个元素是空列表。 栈表示当前尚未闭合的列表 -------------------------- 若输入不以 ``[`` 开头,它就是一个完整整数,直接解析即可。遇到左括号时压入一个空列表;读到整数时加入栈顶列表;读到右括号时弹出完整的当前列表,并把它作为一个元素加入外层列表。逗号只负责分隔,不改变结构。 栈顶始终对应当前最内层未闭合的 ``[``,所以嵌套层级和元素顺序由读取顺序自然保留;``[]`` 在压栈后立即弹出,得到空列表。 C++ 实现 -------- .. code-block:: cpp class Solution { public: NestedInteger deserialize(std::string s) { if (s[0] != '[') return NestedInteger(std::stoi(s)); std::stack lists; lists.push(NestedInteger()); int i = 1; while (i < static_cast(s.size())) { if (s[i] == '[') { lists.push(NestedInteger()); ++i; } else if (s[i] == ']') { NestedInteger current = lists.top(); lists.pop(); ++i; if (lists.empty()) return current; lists.top().add(current); } else if (s[i] == ',') { ++i; } else { int sign = 1; if (s[i] == '-') { sign = -1; ++i; } int value = 0; while (i < static_cast(s.size()) && std::isdigit( static_cast(s[i]))) { value = value * 10 + (s[i] - '0'); ++i; } lists.top().add(NestedInteger(sign * value)); } } return NestedInteger(); } }; 代码分析 -------- 每个数字只解析一次,每个左括号入栈一次、右括号出栈一次;遇到顶层右括号时返回完整对象,单整数分支避免错误地包上一层列表。时间复杂度为 ``O(|s|)``,额外空间为 ``O(h)``,其中 ``h`` 为最大嵌套深度。