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.

Difficulty: interview

Starter code:

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def __init__(self, value=None):
#        """
#        If value is not specified, initializes an empty list.
#        Otherwise initializes a single integer equal to value.
#        """
#
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def add(self, elem):
#        """
#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
#        :rtype void
#        """
#
#    def setInteger(self, value):
#        """
#        Set this NestedInteger to hold a single integer equal to value.
#        :rtype void
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """
class Solution:
    def deserialize(self, s: str) -> NestedInteger:
        

Solutions:
# """
 # This is the interface that allows for creating nested lists.
 # You should not implement it, or speculate about its implementation
 # """
 #class NestedInteger:
 #    def __init__(self, value=None):
 #        """
 #        If value is not specified, initializes an empty list.
 #        Otherwise initializes a single integer equal to value.
 #        """
 #
 #    def isInteger(self):
 #        """
 #        @return True if this NestedInteger holds a single integer, rather than a nested list.
 #        :rtype bool
 #        """
 #
 #    def add(self, elem):
 #        """
 #        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
 #        :rtype void
 #        """
 #
 #    def setInteger(self, value):
 #        """
 #        Set this NestedInteger to hold a single integer equal to value.
 #        :rtype void
 #        """
 #
 #    def getInteger(self):
 #        """
 #        @return the single integer that this NestedInteger holds, if it holds a single integer
 #        Return None if this NestedInteger holds a nested list
 #        :rtype int
 #        """
 #
 #    def getList(self):
 #        """
 #        @return the nested list that this NestedInteger holds, if it holds a nested list
 #        Return None if this NestedInteger holds a single integer
 #        :rtype List[NestedInteger]
 #        """
 
 class Solution:
     def deserialize(self, s):
         """
         :type s: str
         :rtype: NestedInteger
         """
         
         root_ni = NestedInteger()
         
         ni_stack = collections.deque()
         current_ni = root_ni
         
         active_number = None
         is_positive = True
         
         for i, c in enumerate(s):
             if c == '-':
                 is_positive = False
                 active_number = 0
 
             elif c.isdigit():
                 # Check if the previous was a digit as well.
                 if active_number is None:
                     active_number = int(c)
                 else:
                     active_number = int(c) + active_number * 10
 
             else:
                 if active_number is not None:
                     if not is_positive:
                         active_number *= -1
 
                     current_ni.add(active_number)
                     active_number = None
                     is_positive = True
 
                 if c == '[' and i > 0:
                     ni_stack.append(current_ni)
                     current_ni = NestedInteger()
 
                 elif c == ']' and len(ni_stack) > 0:
                     ni_stack[-1].add(current_ni)
                     current_ni = ni_stack.pop()
 
         if active_number is not None:
             if not is_positive:
                 active_number *= -1
 
             if not current_ni.getList():
                 current_ni.setInteger(active_number)
             else:
                 current_ni.add(active_number)
             
         return root_ni
         
         

# """
 # This is the interface that allows for creating nested lists.
 # You should not implement it, or speculate about its implementation
 # """
 #class NestedInteger:
 #    def __init__(self, value=None):
 #        """
 #        If value is not specified, initializes an empty list.
 #        Otherwise initializes a single integer equal to value.
 #        """
 #
 #    def isInteger(self):
 #        """
 #        @return True if this NestedInteger holds a single integer, rather than a nested list.
 #        :rtype bool
 #        """
 #
 #    def add(self, elem):
 #        """
 #        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
 #        :rtype void
 #        """
 #
 #    def setInteger(self, value):
 #        """
 #        Set this NestedInteger to hold a single integer equal to value.
 #        :rtype void
 #        """
 #
 #    def getInteger(self):
 #        """
 #        @return the single integer that this NestedInteger holds, if it holds a single integer
 #        Return None if this NestedInteger holds a nested list
 #        :rtype int
 #        """
 #
 #    def getList(self):
 #        """
 #        @return the nested list that this NestedInteger holds, if it holds a nested list
 #        Return None if this NestedInteger holds a single integer
 #        :rtype List[NestedInteger]
 #        """
 
 class Solution:
     def deserialize(self, s):
         """
         :type s: str
         :rtype: NestedInteger
         """
         return eval(s)
 #     def deserialize(self, s):
 #         def nestedInteger(x):
 #             if isinstance(x, int):
 #                 return NestedInteger(x)
 #             lst = NestedInteger()
 #             for y in x:
 #                 lst.add(nestedInteger(y))
 #             return lst
 #         return nestedInteger(eval(s))
         
         

# """
 # This is the interface that allows for creating nested lists.
 # You should not implement it, or speculate about its implementation
 # """
 #class NestedInteger:
 #    def __init__(self, value=None):
 #        """
 #        If value is not specified, initializes an empty list.
 #        Otherwise initializes a single integer equal to value.
 #        """
 #
 #    def isInteger(self):
 #        """
 #        @return True if this NestedInteger holds a single integer, rather than a nested list.
 #        :rtype bool
 #        """
 #
 #    def add(self, elem):
 #        """
 #        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
 #        :rtype void
 #        """
 #
 #    def setInteger(self, value):
 #        """
 #        Set this NestedInteger to hold a single integer equal to value.
 #        :rtype void
 #        """
 #
 #    def getInteger(self):
 #        """
 #        @return the single integer that this NestedInteger holds, if it holds a single integer
 #        Return None if this NestedInteger holds a nested list
 #        :rtype int
 #        """
 #
 #    def getList(self):
 #        """
 #        @return the nested list that this NestedInteger holds, if it holds a nested list
 #        Return None if this NestedInteger holds a single integer
 #        :rtype List[NestedInteger]
 #        """
 
 class Solution:    
     def convertListToNestedInteger(self, nestList):
         if type(nestList) == type(0):
             return NestedInteger(nestList)
         rtype = NestedInteger()
         for item in nestList:
             if type(item) == type(0):
                 rtype.add(item)
             else:
                 nestedList = self.convertListToNestedInteger(item)
                 rtype.add(nestedList)
         return rtype
         
     def deserializeHelper(self, st):
         if len(st) > 0:
             if st[0] != '[':
                 return int(st)
         assert(len(st) > 1)
         assert(st[0] == '[')
         assert(st[-1] == ']')
         l = st[1:].find('[')
         r = st[:-1].rfind(']')
         assert(l*r >= 0)
         if l > 0:
             nums = [int(s) for s in st[1:l].split(',') if s.strip() != '']
             rest = self.deserializeHelper('[' + st[l+1:] )
             for item in rest:
                 nums.append(item)
             #nums.append(rest)
             return nums
         elif l < 0:
             nums = [int(s) for s in st[1:l].split(',') if s.strip() != '']
             return nums
         r = self.matchingBracket(st)
         ret = [self.deserializeHelper(st[l+1:r+1])]
         if st[r+1] != ']':
             rest = self.deserializeHelper('[' + st[r+2:])
             for item in rest:
                 ret.append(item)
         return ret
 
     def matchingBracket(self, st):
         sum = 1
         #print(st)
         for r in range(2,len(st)):
             #print(sum, st[r])
             if st[r] == '[':
                 sum += 1
             elif st[r] == ']':
                 sum -= 1
             if sum == 0:
                 return r
         raise Exception("Invalid String")
         return None
     
     def deserialize(self, s):
         """
         :type s: str
         :rtype: NestedInteger
         """
         nestList = self.deserializeHelper(s)
         return self.convertListToNestedInteger(nestList)
         

# """
 # This is the interface that allows for creating nested lists.
 # You should not implement it, or speculate about its implementation
 # """
 #class NestedInteger:
 #    def __init__(self, value=None):
 #        """
 #        If value is not specified, initializes an empty list.
 #        Otherwise initializes a single integer equal to value.
 #        """
 #
 #    def isInteger(self):
 #        """
 #        @return True if this NestedInteger holds a single integer, rather than a nested list.
 #        :rtype bool
 #        """
 #
 #    def add(self, elem):
 #        """
 #        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
 #        :rtype void
 #        """
 #
 #    def setInteger(self, value):
 #        """
 #        Set this NestedInteger to hold a single integer equal to value.
 #        :rtype void
 #        """
 #
 #    def getInteger(self):
 #        """
 #        @return the single integer that this NestedInteger holds, if it holds a single integer
 #        Return None if this NestedInteger holds a nested list
 #        :rtype int
 #        """
 #
 #    def getList(self):
 #        """
 #        @return the nested list that this NestedInteger holds, if it holds a nested list
 #        Return None if this NestedInteger holds a single integer
 #        :rtype List[NestedInteger]
 #        """
 
 import re
 
 class Solution:
     def deserialize(self, s):
         """
         :type s: str
         :rtype: NestedInteger
         """
         s = re.sub("\[","[,", s)
         s = re.sub("\]",",]", s)
         s = s.split(",")
 
         if not s[0] == "[":
             return NestedInteger(int(s[0]))
         
         obj = NestedInteger()
         self.parse_recursive_list(s, 1, obj)
         return obj
         
     def parse_recursive_list(self, s, i, obj):
         while i<len(s):
             if s[i] == '':
                 i += 1
                 continue
             if s[i] == "[":
                 new_obj = NestedInteger()
                 i = self.parse_recursive_list(s, i+1, new_obj)
                 obj.add(new_obj)
             elif s[i] == ']':
                 return i+1
             else:
                 integer = int(s[i])
                 obj.add(NestedInteger(integer))
                 i += 1
         return i