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,[,-,,].
The following NestedInteger interface is already provided:
/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* interface NestedInteger {
*
* // Constructor initializes an empty nested list.
* public NestedInteger();
*
* // Constructor initializes a single integer.
* public NestedInteger(int value);
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* bool IsInteger();
*
* // @return the single integer that this NestedInteger holds, if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* int GetInteger();
*
* // Set this NestedInteger to hold a single integer.
* public void SetInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* public void Add(NestedInteger ni);
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return null if this NestedInteger holds a single integer
* IList<NestedInteger> GetList();
* }
*/
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* interface NestedInteger {
*
* // Constructor initializes an empty nested list.
* public NestedInteger();
*
* // Constructor initializes a single integer.
* public NestedInteger(int value);
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* bool IsInteger();
*
* // @return the single integer that this NestedInteger holds, if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* int GetInteger();
*
* // Set this NestedInteger to hold a single integer.
* public void SetInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* public void Add(NestedInteger ni);
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return null if this NestedInteger holds a single integer
* IList<NestedInteger> GetList();
* }
*/
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.
Answer: The way we go about solving this is to read the string character by character and perform
an operation based on the character. It is a state machine where the state may change based on
whatever the current input character is. Important transitions happen when characters like '[', ']',
',' are seen. We use a stack to keep track of the parent at any point of time.
Solution is as follows:
public NestedInteger Deserialize(string s)
{
if (string.IsNullOrEmpty(s))
{
return null;
}
var st = new Stack<NestedInteger>();
int value = 0;
int numDigits = 0;
NestedInteger curr = null;
NestedInteger rtnValue = null;
var negativeMultiplier = 1;
for (int i = 0; i < s.Length; i++)
{
// A new NestedInteger object needs to be created.
if (s[i] == '[')
{
value = 0;
var n = new NestedInteger();
// This is the first object/outer-most from the string
if (rtnValue == null)
{
rtnValue = n;
}
else
{
curr.Add(n);
st.Push(curr);
}
curr = n;
}
else if (s[i] == ',')
{
if (numDigits > 0)
{
var n = new NestedInteger(negativeMultiplier * value);
curr.Add(n);
}
value = 0;
negativeMultiplier = 1;
numDigits = 0;
}
else if (s[i] == ']')
{
if (numDigits > 0)
{
var n = new NestedInteger(negativeMultiplier * value);
curr.Add(n);
}
value = 0;
numDigits = 0;
if (st.Count > 0)
{
curr = st.Pop();
}
else
{
curr = null;
}
negativeMultiplier = 1;
}
else if (s[i] >= '0' && s[i] <='9')
{
numDigits++;
value = value * 10 + int.Parse(s[i].ToString());
}
else if (s[i] == '-')
{
negativeMultiplier = -1;
}
else
{
throw new Exception ("Incorrect string");
}
}
// This will be executed for something like example 2
if (rtnValue == null)
{
if (numDigits > 0)
{
rtnValue = new NestedInteger(negativeMultiplier * value);
}
else
{
rtnValue = new NestedInteger();
}
}
return rtnValue;
}
