Leetcode 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:
|
1 2 3 4 |
Given s = "324", You should return a NestedInteger object which contains a single integer 324. |
Example 2:
|
1 2 3 4 5 6 7 8 9 10 |
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. |
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
|
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 |
/** * // 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(); * } */ public class Solution { public NestedInteger deserialize(String ss) { if (ss.charAt(0) != '['){ return new NestedInteger(Integer.valueOf(ss)); } Stack<NestedInteger> s = new Stack<>(); Integer num = null; int minusFlag = 1; NestedInteger cur = null; for(char c: ss.toCharArray()) { if (c == '[') { if (cur == null) { cur = new NestedInteger(); } else { s.push(cur); cur = new NestedInteger(); } }else if(c == ']') { if (num != null){ cur.add(new NestedInteger(num * minusFlag)); } if (!s.isEmpty()) { s.peek().add(cur); cur = s.pop(); } num = null; minusFlag = 1; }else if(c == ',') { if(num != null) { cur.add(new NestedInteger(num * minusFlag)); num = null; minusFlag = 1; } else { //"[324,[22,1],4,5,[3,4,[5]]]" //do nothing here } }else if(c == '-') { minusFlag = -1; }else if(c >= '0' && c <= '9') { if(num == null) num = c - '0'; else num = num * 10 + (c - '0'); } else { //can hangle othere characters } } return cur; } } |
