385. Mini Parser

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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.

Code

/**
 * // 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 empty list if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    public NestedInteger deserialize(String s) {
        Stack<NestedInteger> stack = new Stack<>();

        NestedInteger root = new NestedInteger();
        // 字符串中只有一个数字
        if(!s.startsWith("[")){
            return new NestedInteger(Integer.valueOf(s));
        }

        stack.push(root);

        int i = 1;
        while(i < s.length() - 1){
            char c = s.charAt(i);
            // 要考虑符号
            if (Character.isDigit(c) || c == '+' || c == '-'){
                boolean isNeg = false;

                if(c == '+'){
                    i++;
                }

                if(c == '-'){
                    isNeg = true;
                    i++;
                }

                int num = s.charAt(i) - '0';

                while(i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))){
                    num = num * 10 + (s.charAt(i + 1) - '0');
                    i++;
                }

                num = isNeg ? -num : num;
                NestedInteger temp = new NestedInteger(num);
                stack.peek().add(temp);
                i++;
            } else if (c == '['){
                stack.push(new NestedInteger());
                i++;
            } else if (c == ']'){
                NestedInteger curr = stack.pop();
                stack.peek().add(curr);
                i++;
            } else if (c == ','){
                i++;
            }
        }

        return stack.pop();
    }
}