13、 ... and 、 Mini parser

13.1、 Question design requirements

   Given a string s Represents a nested list of integers , Implement a parser that parses it and returns the parsed results NestedInteger .

   Each element in the list can only be an integer or an integer nested list

 Example  1：
 Input ：s = "324",
 Output ：324
 explain ： You should return one  NestedInteger  object , Only integer values are included  324.

 Example  2：
 Input ：s = "[123,[456,[789]]]",
 Output ：[123,[456,[789]]]
 explain ： Return to one  NestedInteger  Object contains a nested list of two elements ：
1.  One  integer  Contains the value  123
2.  A nested list of two elements ：
  i.   One  integer  Contains the value  456
  ii.  A nested list containing one element 
       a.  One  integer  Contains the value  789

 Tips ：
1 <= s.length <= 5 * 104
s  By digital 、 square brackets  "[]"、 Minus sign  '-' 、 comma  ',' form 
 Use cases guarantee  s  It's analyzable  NestedInteger
 The range of all values in the input is  [-106, 106]

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/mini-parser

13.2、 Their thinking

   Traverse from left to right s, If you encounter “[” , It means a new NestedInteger example , You need to put it on the stack . If you encounter “]” or “,” , It means a number or NestedInteger End of instance , You need to add it to the top of the stack NestedInteger example . Finally, return the instance at the top of the stack .

13.3、 Algorithm

/** * //  This is an interface that allows you to create embedded lists  * //  You shouldn't realize it , Nor should we speculate about its implementation  * public interface NestedInteger { * //  Constructor initializes an empty nested list  * public NestedInteger(); * * //  Constructor initializes a single integer  * public NestedInteger(int value); * * //  If so NestedInteger Contains a single integer , Instead of nested lists , Then return to True * public boolean isInteger(); * * //  If NestedInteger Contains a single integer , Return this NestedInteger Saved single integer  * //  If so NestedInteger Contains nested lists , Then return to NULL * public Integer getInteger(); * * //  Put this NestedInteger Set to include a single integer  * public void setInteger(int value); * * //  Set this NestedInteger To save the nested list and add nested integers to it  * public void add(NestedInteger ni); * * //  If NestedInteger Contains nested lists , Return this NestedInteger Saved nested list  * //  If so NestedInteger Contains a single integer , Then return to the empty list  * public List<NestedInteger> getList(); * } */

//parseInt() function ： Used to parse a string , And return an integer 
//isDigit() function ： Check whether the parameter is decimal numeric character 

class Solution {
    
    // Traverse from left to right s, If you encounter "[", It means a new NestedInteger example , You need to put it on the stack .
    // If you encounter "]" or ",", It means a number or NestedInteger End of instance , You need to add it to the top of the stack NestedInteger example .
    // Finally, return the instance at the top of the stack .
    public NestedInteger deserialize(String s) {
    
        // No, "[", Just an integer , end 
        if(s.charAt(0) != '['){
    
            return new NestedInteger(Integer.parseInt(s));
        }
        // Define a stack to store data 
        Deque<NestedInteger> stack = new ArrayDeque<>();
        int num = 0;
        boolean negative = false;
        for (int i = 0; i < s.length(); i++) {
    
            // Take out the characters in the string one by one 
            char c = s.charAt(i);
            // The character is '-', Output true
            if (c == '-') {
    
                negative = true;
            }else if (Character.isDigit(c)){
    
                // If the character is a number , Pressure into the stack 
                num = num * 10 + c - '0';
            }else if (c == '['){
    
                // If the character is '[', Pressure into the stack 
                stack.push(new NestedInteger());
            }else if (c == ',' || c == ']'){
    
                // If you encounter ']' or ',', Put numbers or NestedInteger The instance is added to the top of the stack NestedInteger example 
                if (Character.isDigit(s.charAt(i-1))){
    
                    if (negative){
    
                        num *= -1;
                    }
                    stack.peek().add(new NestedInteger(num));
                }
                num = 0;
                negative = false;
                if (c == ']' && stack.size() > 1){
    
                    NestedInteger ni = stack.pop();
                    stack.peek().add(ni);
                }
            }
        }
        return stack.pop();
    }
}