LeetCode 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.

---

给定一个嵌套的字符串，要求把它解析成一个NestedInteger。 解法1，使用栈。遇到左括号时，增加一个空的NestedInteger实例，压栈。遇到逗号时，把前面的数add到栈顶的NestedInteger中。遇到右括号时，把栈顶的NestedInteger弹栈，并add到新的栈顶（相当于前一个）NestedInteger中。最后栈顶只有一个元素，返回该元素即可。 代码如下： [cpp] class Solution { public: NestedInteger deserialize(string s) { auto isnumber = [](char c) {return c == ‘-‘ || isdigit(c); }; stack<NestedInteger> stk; stk.push(NestedInteger()); for (auto it = s.begin(); it != s.end();) { if (isnumber(*it)) { auto it2 = find_if_not(it, s.end(), isnumber); int v = stoi(string(it, it2)); stk.top().add(NestedInteger(v)); it = it2; } else { if (*it == ‘[‘) { stk.push(NestedInteger()); } else if (*it == ‘]’) { NestedInteger tmp = stk.top(); stk.pop(); stk.top().add(tmp); } ++it; } } return stk.top().getList().front(); } }; [/cpp] 本代码提交AC，用时19MS。 解法2，递归法。如果当前的字符串是一个裸的整数的话，类似于样例1，则直接返回以该数为参数的NestedInteger；否则剥掉左括号[，递归反序列化，把递归的结果add到当前的NestedInteger中。 代码如下： [cpp] class Solution { private: NestedInteger deserialize(istringstream &in) { int number; if (in >> number) return NestedInteger(number); in.clear(); in.get(); NestedInteger list; while (in.peek() != ‘]’) { list.add(deserialize(in)); if (in.peek() == ‘,’)in.get(); } in.get(); return list; } public: NestedInteger deserialize(string s) { istringstream in(s); return deserialize(in); } }; [/cpp] 本代码提交AC，用时19MS。 参考1，栈：https://discuss.leetcode.com/topic/54904/c-non-recursive-one-pass-solution-using-stack-a-possible-implementation-of-nestedinteger 参考2，递归：https://discuss.leetcode.com/topic/54258/python-c-solutions/10]]>