Tuesday, October 25, 2016

Mini Parser

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.


Usually when we deal with "nested" or "parentheses" or layers, we need a Stack. The Stack is used to track elements in different layers. In this problem, whenever we see a '[', we know a new layer starts, and this layer is another NestedInteger, so we push a new NestedInteger in it. If we see a ']', we know current layer ends, so we pop it out and add it to last layer. If current layer is the outer most layer, we return the NestedInteger. The rest is trivial, a ',' means the ending of last NestedInteger, so we push the left number into current layer (head of the stack), while a number is a number, we add it to current number.


public NestedInteger deserialize(String s) {
        if (s.charAt(0) != '[') {
            return new NestedInteger(Integer.valueOf(s));
        }
        Stack layers = new Stack<>();
        String currNum = "";
        int pos = 0;
        int len = s.length();
        NestedInteger toReturn = new NestedInteger();
        while (pos < len) {
            char c = s.charAt(pos);
            if (c == '[') {
                layers.push(new NestedInteger());
            } else if (c == ']') {
                if (!"".equals(currNum)) {
                    layers.peek().add(new NestedInteger(Integer.valueOf(currNum)));
                    currNum = "";
                }
                NestedInteger currNested = layers.pop();
                if (layers.isEmpty()) {
                    toReturn = currNested;
                    break;
                } else {
                    layers.peek().add(currNested);
                }
            } else if (c == ',') {
                if (!"".equals(currNum)) {
                    layers.peek().add(new NestedInteger(Integer.valueOf(currNum)));
                    currNum = "";
                }
            } else {
                currNum += c;
            }
            pos++;
        }
        return toReturn;
    }


No comments:

Post a Comment