0%

[Leetcode]385. Mini Parser(C++)

题目描述

题目链接:385. Mini Parser

Given a string s represents the serialization of a nested list, implement a parser to deserialize it and return the deserialized NestedInteger.

Each element is either an integer or a list whose elements may also be integers or other lists.

例子

例子 1

Input: s = "324"
Output: 324
Explanation: You should return a NestedInteger object which contains a single integer 324.

例子 2

Input: s = "[123,[456,[789]]]"
Output: [123,[456,[789]]]
Explanation: Return a NestedInteger object containing a nested list with 2 elements:

  1. An integer containing value 123.
  2. A nested list containing two elements:
    i. An integer containing value 456.
    ii. A nested list with one element:
     a. An integer containing value 789
    

Constraints

1 <= s.length <= 5 * 10^4
s consists of digits, square brackets "[]", negative sign '-', and commas ','.
s is the serialization of valid NestedInteger.

解题思路

从例子中可以发现,序列化后的字符串可以看成由以下几部分组成:

  • 数字:以 - 或者数字开头
  • [:标志一个 NestedInteger 的开始
  • ]:表示一个 NestedInteger 的结束
  • ,:分割不同元素

由于 NestedInteger 之间有互相嵌套关系,我们可以用一个栈来维护其关系,具体思路是,遍历字符串,根据不同部分进行不同操作:

  • 数字:如果栈为空表示前面没有出现过嵌套列表,因此压入一个新的 NestedInteger (以当前数字为初值),否则表示当前已经在一个 NestedInteger 中,因此应该将当前数字作为一个新的 NestedInteger 添加到当前栈顶的元素的列表中
  • [:表示一个新的 NestedInteger 的开始,压入一个空元素
  • ]:表示当前 NestedInteger 已经结束,将栈顶元素取出,添加到前一个 NestedInteger 的列表中(如果栈中本身只有一个元素则不操作)
  • ,:分隔符,不需要操作

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stack>
#include <string>

class Solution {
public:
NestedInteger deserialize(std::string s) {
std::stack<NestedInteger> stk;
int idx = 0;
while (idx < s.length()) {
if (std::isdigit(s[idx]) || s[idx] == '-') {
int sign = 1;
if (s[idx] == '-') {
sign = -1;
idx++;
}
int val = 0;
while (idx < s.length() && std::isdigit(s[idx])) {
val *= 10;
val += s[idx] - '0';
idx++;
}
val *= sign;

if (stk.empty()) {
stk.push(NestedInteger(val));
} else {
stk.top().add(NestedInteger(val));
}
} else if (s[idx] == '[') {
stk.push(NestedInteger());
idx++;
} else if (s[idx] == ']') {
if (stk.size() > 1) {
auto ni = stk.top();
stk.pop();
stk.top().add(ni);
}
idx++;
} else {
idx++;
}
}

return stk.top();
}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 385.MiniParser.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions