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 II，Flatten 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; } };
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; } };
本文转自博客园Grandyang的博客，原文链接：迷你解析器[LeetCode] Mini Parser ，如需转载请自行联系原博主。
