Mini Parser

leetcode 385.

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.

Solution.

If it is ‘-‘, then sign = -1

If it is digit, then calculate digit

If it is ‘[‘, then push to stack.

If it is ‘]’, pop stack

If it is ‘,’, continue

There maybe digit before ‘,’ or ‘]’. So when there is ‘,’ or ‘]’, check if add digit

Assuming stack.peek() is curr = [4, 5, 6, [newList]], curr add 4, 5, 6 separately. When peek curr meets ‘]’, we create the newList, and add newList to curr. And newList to stack to be the top element.

public NestedInteger deserialize(String s) {
    Stack<NestedInteger> stack = new Stack();
    stack.add(new NestedInteger()); // top level is a dummy NestedInteger
    int sign = 1, digit = 0;
    for (int i = 0; i < s.length(); i++) {
        char ch = s.charAt(i);
        if (ch == '-') {
            sign = -1;
        }
        else if (Character.isDigit(ch)) {
            digit = digit * 10 + ch - '0';
        }
        else if (ch == '[') {   // peek element will include this new NestdInteger
            NestedInteger curr = new NestedInteger();
            stack.peek().add(curr);
            stack.add(curr);
        }
        else if (ch == ',' && Character.isDigit(s.charAt(i - 1))) {
            stack.peek().add(new NestedInteger(digit * sign));
            digit = 0;
            sign = 1;
        }
        else if (ch == ']') {
            if (Character.isDigit(s.charAt(i - 1))) {
                stack.peek().add(new NestedInteger(digit * sign));
                digit = 0;
                sign = 1;
            }
            stack.pop();
        }
    }
    if (s.length() > 0 && Character.isDigit(s.charAt(s.length() - 1))) {    // handle "321". Only digit
        stack.peek().add(new NestedInteger(digit * sign));
    }
    return stack.pop().getList().get(0);
}

Check my code on github.