Leetcode mini parser

Tags: ,

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:

Example 2:

 

Analysis

Define num to store the current number, and minusFlag to denote whether the current number is negative. In the scanning process, we can calculate num using num = num * 10 + currentDigit.

Define a stack S to store the nestedIntegers, and define cur as the NestedInteger for the current number num.

Initialization:

num = null

minusFlag = 1

foreach character c in the input sequence:

If the current character c is ‘[‘, it is time to create a new NestedInteger assigned to cur. If the previous cur is not null, it should be pushed into the stack before creating a new one. 

If the current character is a digit, update the num = num * 10 + (digit - '0') if num != null else num = digit - '0'

If the current character is ‘-‘, set minusFlag  =  -1. 

If the current character is corma(‘,’):  cur.add(new NestedInteger(num * minusFlag)) if num != null, num = null, minusFlag = 1.

If the current character is ‘]’:  

    cur.add(new NestedInteger(num * minusFlag)) if num != null, num = null, minusFlag = 1.
   if stack not empty: stack.peek().add(cur), cur = stack.pop(), num = null, minusFlag = 1.

return cur

Java Solution