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

题目描述

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:

An integer containing value 123.

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 的列表中（如果栈中本身只有一个元素则不操作）
,：分隔符，不需要操作

代码如下：

#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