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.

Notes
Example: "[1,2,[3,4,5],[[]],6,[]]"
这种题总是想想感觉要做出来了，但是细节怎么都搞不对啊。说一下基本思路： 用一个stack存NestedInteger。

• 遇到左括号：新开一个空的NestedInteger压入栈；
• 遇到一个完整数字：加入栈顶的NestedInteger
• 遇到右括号：合并栈顶的两个NestedInteger

Python code

def parse(s):
  n = len(s)
  tmp_i = ""
  stack = [[]]
  for i in range(n):
    print stack
    if ( s[i] == " " ): continue
    if ( s[i] != "," and s[i] != "[" and s[i] != "]"):
      tmp_i += s[i]
      continue
    if ( s[i] == "," or s[i] == "]" ):
      if ( tmp_i != "" ): stack[-1].append(int(tmp_i))
      tmp_i = ""
    if ( s[i] == "[" and i != 0 ):
      stack.append([])
    if ( s[i] == "]" ):
      if ( len(stack) == 1 ): continue
      else:
        top_ni = stack[-1]
        stack.pop(-1)
        stack[-1].append(top_ni)
  return stack[-1]

Solution

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Constructor initializes an empty nested list.
 *     NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     NestedInteger(int value);
 *
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Set this NestedInteger to hold a single integer.
 *     void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     void add(const NestedInteger &ni);
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class Solution {
public:
    NestedInteger deserialize(string s) {
        int n = s.size();
        NestedInteger res;
        if ( n == 0 ) return res;
        if ( s[0] != '[' ) {
            res.setInteger(stoi(s));
            return res;
        }
        stack<NestedInteger> st;
        string tmp_i = "";
        for ( int i = 0; i <= n-1; i++ ) {
            if ( s[i] == ' ' ) continue;
            if ( s[i] != '[' and s[i] != ']' and s[i] != ',' ) tmp_i += s[i];
            if ( s[i] == ',' or s[i] == ']' ) {
                if ( tmp_i != "" ) st.top().add(stoi(tmp_i));
                tmp_i = "";
            }
            if ( s[i] == '[' ) {
                NestedInteger tmp_ni;
                st.push(tmp_ni);
            }
            if ( s[i] == ']' ) {
                if ( st.size() == 1 ) continue;
                auto top_ni = st.top();
                st.pop();
                st.top().add(top_ni);
            }
        }
        return st.top();
    }
};