Skip to content

385. Mini Parser 👎

  • Time: $O(n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  NestedInteger deserialize(string s) {
    if (s[0] != '[')
      return NestedInteger(stoi(s));

    stack<NestedInteger> stack;
    int start;  // the start index of a number

    for (int i = 0; i < s.length(); ++i) {
      switch (s[i]) {
        case '[':
          stack.push(NestedInteger());
          start = i + 1;
          break;
        case ',':
          if (i > start) {
            const int num = stoi(s.substr(start, i));
            stack.top().add(NestedInteger(num));
          }
          start = i + 1;
          break;
        case ']':
          NestedInteger popped = stack.top();
          stack.pop();
          if (i > start) {
            const int num = stoi(s.substr(start, i));
            popped.add(NestedInteger(num));
          }
          if (stack.empty())
            return popped;
          else
            stack.top().add(popped);
          start = i + 1;
          break;
      }
    }

    throw;
  }
};

 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
class Solution {
  public NestedInteger deserialize(String s) {
    if (s.charAt(0) != '[')
      return new NestedInteger(Integer.parseInt(s));

    Deque<NestedInteger> stack = new ArrayDeque<>();
    int start; // the start index of a number

    for (int i = 0; i < s.length(); ++i)
      switch (s.charAt(i)) {
        case '[':
          stack.push(new NestedInteger());
          start = i + 1;
          break;
        case ',':
          if (i > start) {
            final int num = Integer.parseInt(s.substring(start, i));
            stack.peek().add(new NestedInteger(num));
          }
          start = i + 1;
          break;
        case ']':
          NestedInteger popped = stack.pop();
          if (i > start) {
            final int num = Integer.parseInt(s.substring(start, i));
            popped.add(new NestedInteger(num));
          }
          if (!stack.isEmpty())
            stack.peek().add(popped);
          else
            return popped;
          start = i + 1;
          break;
      }

    throw new IllegalArgumentException();
  }
}

 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
class Solution:
  def deserialize(self, s: str) -> NestedInteger:
    if s[0] != '[':
      return NestedInteger(int(s))

    stack = []

    for i, c in enumerate(s):
      if c == '[':
        stack.append(NestedInteger())
        start = i + 1
      elif c == ',':
        if i > start:
          num = int(s[start:i])
          stack[-1].add(NestedInteger(num))
        start = i + 1
      elif c == ']':
        popped = stack.pop()
        if i > start:
          num = int(s[start:i])
          popped.add(NestedInteger(num))
        if stack:
          stack[-1].add(popped)
        else:
          return popped
        start = i + 1