LeetCode [385] Mini Parser

 385. Mini Parser

Medium

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

/** * // This is the interface that allows for creating nested lists. * // You should not implement it, or speculate about its implementation * public 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. * public boolean isInteger(); * * // @return the single integer that this NestedInteger holds, if it holds a single integer * // Return null if this NestedInteger holds a nested list * public Integer 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 * public List<NestedInteger> getList(); * } */ /* 1. What is the invariant? -- The top of stack should be the answer 2. What are the rules? -- A number makes a NestedInteger node -- A pair of [] makes a NestedInteger list 3. What is the strategy? -- Each element of stack is a NestedInteger list 4. What is the special case? -- If there is only one number in the string, the stack top is a NestedInteger node 5. How to approach? -- Whenever see '[', we create a new NestedInteger list and push to the stack -- Whenever see ']', we complete a NestedInteger list. ----If the stack is empty, the completed NestedInteger list is our answer so we push it back to the stack. ----Otherwise, the completed NestedInteger is part of an unfinished list, which is also the top of the stack. So we add it to the stack's top element. */ class Solution { public NestedInteger deserialize(String s) { Stack<NestedInteger> stk = new Stack(); int i = 0; while(i<s.length()){ char c = s.charAt(i); if(Character.isDigit(c) || c=='-'){ int j = i; while(j<s.length() && (Character.isDigit(s.charAt(j)) || s.charAt(j)=='-')) j++; String num = s.substring(i, j); NestedInteger node = new NestedInteger(Integer.valueOf(num)); if(stk.empty()) stk.push(node); else{ NestedInteger top = stk.peek(); top.add(node); } i = j; }else if(c == '['){ stk.push(new NestedInteger()); i++; }else if(c == ','){ i++; }else if(c == ']'){ NestedInteger complete = stk.pop(); if(!stk.empty()){ stk.peek().add(complete); }else{ stk.push(complete); } i++; } } if(stk.empty()) return null; else return stk.pop(); } }