385. Mini-parsers: Stack application simulations

Make writing a habit together! This is the 15th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Topic describes

This is 385. Mini parser on LeetCode, medium difficulty.

Tag: “stack”, “simulation”

Given a string s representing a nested list of integers, implement a parser that parses it and returns the parsed result, NestedInteger.

Each element in a list can only be an integer or a nested list of integers

Example 1:

Input: s = "324", output: 324 Explanation: You should return a NestedInteger object containing only the integer value 324.Copy the code

Example 2:

Input: s = "[123,[456,[789]] ", output: [123,[456,[789]]] Explanation: Return a NestedInteger object containing a nested list of two elements: 1. An integer contains the value 123 2. A nested list containing two elements: I. An INTEGER contains the value 456 ii. A nested list containing one element A. An integer contains the value 789Copy the code

Tip:

• 
  $1 <= s.length <= 5 * 10^4$
• sBy numbers, square brackets"[]"And minus signThe '-', comma,', 'composition
• Use cases to ensuresIt’s resolvableNestedInteger
• The range of all values in the input is [−106,106][-10^6, 10^6][−106,106]

The stack

Each occurrence of [means that there is a nested instance of NestedInteger, Also, each NestedInteger instance (whether nested or numeric) belongs to the NestedInteger instance of the nearest nested type to its left (that is, the nearest [) to its left), so we can use stacks to handle it.

A brief case discussion of several types of characters:

• .: Skip it;
• - 或 digital: Creates a numeric string by extracting consecutive numeric stringsNestedIntegerInstance and push it onto the stack;
• [: creates a nested typeNestedIntegerInstance is pushed onto the stack and, for convenience, an “identifier” is pushedNestedIntegerObject;
• ]: Fetches elements from the stack until an identifier is encounteredNestedIntegerObject (indicating found and current]Pairs of[),[ 和 ]Between all elements added to[Generation refers to nestingNestedIntegerIn the instance, and then the[Generation refers to nestingNestedIntegerThe instance is put back on the stack.

Process the entire s according to the above logic, and the final element at the top of the stack is the answer.

Code:

class Solution {
    static NestedInteger ph = new NestedInteger(0);
    public NestedInteger deserialize(String s) {
        Deque<NestedInteger> d = new ArrayDeque<>();
        char[] cs = s.toCharArray();
        int n = cs.length, i = 0;
        while (i < n) {
            if (cs[i] == ', ' && ++i >= 0) continue;
            if (cs[i] == The '-' || (cs[i] >= '0' && cs[i] <= '9')) {
                int j = cs[i] == The '-' ? i + 1 : i, num = 0;
                while (j < n && (cs[j] >= '0' && cs[j] <= '9')) num = num * 10 + (cs[j++] - '0');
                d.addLast(new NestedInteger(cs[i] == The '-' ? -num : num));
                i = j;
            } else if (cs[i] == '[') {
                d.addLast(new NestedInteger());
                d.addLast(ph);
                i++;
            } else {
                List<NestedInteger> list = new ArrayList<>();
                while(! d.isEmpty()) { NestedInteger poll = d.pollLast();if (poll == ph) break;
                    list.add(poll);
                }
                for (int j = list.size() - 1; j >= 0; j--) d.peekLast().add(list.get(j)); i++; }}returnd.peekLast(); }}Copy the code

• Time complexity: O(n)O(n)O(n)
• Space complexity: O(n)O(n)O(n)

The last

This is the 385th article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 questions on LeetCode as of the start date, some of which have locks. We will first brush all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.