385. Mini Parser

 

Given a nested list of integers represented as a string, implement a parser to deserialize it.

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

Note: You may assume that the string is well-formed:

  • String is non-empty.
  • String does not contain white spaces.
  • String contains only digits 0-9[- ,].

 

Example 1:

Given s = "324",

You should return a NestedInteger object which contains a single integer 324.

 

Example 2:

Given s = "[123,[456,[789]]]",

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.

 

这道题让我们实现一个迷你解析器用来把一个字符串解析成NestInteger类,关于这个嵌套链表类的题我们之前做过三道,Nested List Weight Sum IIFlatten Nested List Iterator,和Nested List Weight Sum。应该对这个类并不陌生了,我们可以先用递归来做,思路是,首先判断s是否为空,为空直接返回,不为空的话看首字符是否为’[‘,不是的话说明s为一个整数,我们直接返回结果。如果首字符是’[‘,且s长度小于等于2,说明没有内容,直接返回结果。反之如果s长度大于2,我们从i=1开始遍历,我们需要一个变量start来记录某一层的其实位置,用cnt来记录跟其实位置是否为同一深度,cnt=0表示同一深度,由于中间每段都是由逗号隔开,所以当我们判断当cnt为0,且当前字符是逗号或者已经到字符串末尾了,我们把start到当前位置之间的字符串取出来递归调用函数,把返回结果加入res中,然后start更新为i+1。如果遇到’[‘,计数器cnt自增1,若遇到’]’,计数器cnt自减1。参见代码如下:

 

解法一:

class Solution {
public:
    NestedInteger deserialize(string s) {
        if (s.empty()) return NestedInteger();
        if (s[0] != '[') return NestedInteger(stoi(s));
        if (s.size() <= 2) return NestedInteger();
        NestedInteger res;
        int start = 1, cnt = 0;
        for (int i = 1; i < s.size(); ++i) {
            if (cnt == 0 && (s[i] == ',' || i == s.size() - 1)) {
                res.add(deserialize(s.substr(start, i - start)));
                start = i + 1;
            } else if (s[i] == '[') ++cnt;
            else if (s[i] == ']') --cnt;
        }
        return res;
    }
};

 

我们也可以使用迭代的方法来做,这样就需要使用栈来辅助,变量start记录起始位置,我们遍历字符串,如果遇到’[‘,我们给栈中加上一个空的NestInteger,如果遇到的字符数逗号或者’]’,如果i>start,那么我们给栈顶元素调用add来新加一个NestInteger,初始化参数传入start到i之间的子字符串转为的整数,然后更新start=i+1,当遇到的’]’时,如果此时栈中元素多于1个,那么我们将栈顶元素取出,加入新的栈顶元素中通过调用add函数,参见代码如下:

 

解法二:

class Solution {
public:
    NestedInteger deserialize(string s) {
        if (s.empty()) return NestedInteger();
        if (s[0] != '[') return NestedInteger(stoi(s));
        stack<NestedInteger> st;
        int start = 1;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '[') {
                st.push(NestedInteger());
                start = i + 1;
            } else if (s[i] == ',' || s[i] == ']') {
                if (i > start) {
                    st.top().add(NestedInteger(stoi(s.substr(start, i - start))));
                }
                start = i + 1;
                if (s[i] == ']') {
                    if (st.size() > 1) {
                        NestedInteger t = st.top(); st.pop();
                        st.top().add(t);
                    }
                }
            }
        }
        return st.top();
    }
};

 

还有一种方法是利用C++ STL中的字符串流处理类istringstream,我们需要对几个函数有些了解,比如clear()是重置字符流中的字符串,get()是获得下一个字符,peek()是返回首字符,>>num是读取出合法的整数,如果无法读取出整数,需要调用clear()来重置字符串,否则调用get()会出错。思路跟上面的递归解法相同,参见代码如下:

 

解法三:

class Solution {
public:
    NestedInteger deserialize(string s) {
        istringstream in(s);
        return deserialize(in);
    }
    NestedInteger deserialize(istringstream& in) {
        int num;
        if (in >> num) return NestedInteger(num);
        in.clear();
        in.get();
        NestedInteger list;
        while (in.peek() != ']') {
            list.add(deserialize(in));
            if (in.peek() == ',') {
                in.get();
            }
        }
        in.get();
        return list;
    }
};

 

类似题目:

Nested List Weight Sum II

Flatten Nested List Iterator

Nested List Weight Sum

 

参考资料:

https://discuss.leetcode.com/topic/54258/python-c-solutions/3

https://discuss.leetcode.com/topic/54341/iterative-c-using-stack

https://discuss.leetcode.com/topic/54277/short-java-recursive-solution

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation