<p>Given a string s represents the serialization of a nested list, implement a parser to deserialize it and return <em>the deserialized</em> <code>NestedInteger</code>.</p>

<p>Each element is either an integer or a list whose elements may also be integers or other lists.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;324&quot;
<strong>Output:</strong> 324
<strong>Explanation:</strong> You should return a NestedInteger object which contains a single integer 324.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;[123,[456,[789]]]&quot;
<strong>Output:</strong> [123,[456,[789]]]
<strong>Explanation:</strong> 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
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>s</code> consists of digits, square brackets <code>&quot;[]&quot;</code>, negative sign <code>&#39;-&#39;</code>, and commas <code>&#39;,&#39;</code>.</li>
	<li><code>s</code> is the serialization of valid <code>NestedInteger</code>.</li>
	<li>All the values in the input are in the range <code>[-10<sup>6</sup>, 10<sup>6</sup>]</code>.</li>
</ul>

/**
 * // 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 {
    NestedInteger parse(string s,int &si){
        int k =INT_MAX;
        NestedInteger ans =NestedInteger (); 
        int sign =1;
        for(int i=1;i<s.length();i++){
            if(s[i]==','){
                if(k!=INT_MAX){
                    ans.add(NestedInteger(k*sign));
                }
                k=INT_MAX;
                sign=1;
            }
            else if(s[i]=='['){
                int pos;
                NestedInteger cal = parse(s.substr(i,s.size()),pos);
                //cout<<pos<<" ";
                ans.add(cal);
                i+=pos;
            }else if(s[i]==']'){
                if(k!=INT_MAX){
                    ans.add(NestedInteger(k*sign));
                    k=INT_MAX;
                    sign =1;
                }
                si=i;
                return ans;
            }else{
                if(s[i]=='-'){
                    sign =-1;
                }else if(k==INT_MAX){
                    k = s[i]-'0';
                }else {
                    k*=10;
                    k+=s[i]-'0';
                }
            }
           
        }
        if(k!=INT_MAX){
             si=s.length()-1;
             ans.add(NestedInteger(k*sign));
             k=INT_MAX;
             sign=1;
        }
        return ans;
    }
public:
    NestedInteger deserialize(string s) {
        if(s[0]!='['){
            int k=0;
            for(int i=0;i<s.length();i++){
                if(s[i]=='-'){
                    continue;
                }
                k*=10;
                k+=s[i]-'0';
            }
             if(s[0]=='-'){
                return NestedInteger(k*(-1));
            }
            return NestedInteger(k);
        }
        int st=0;
        return parse(s,st);
    }
};
20000