Question

385. Mini Parser

中文文档

Description

Given a string s represents the serialization of a nested list, implement a parser to deserialize it and return _the deserialized_ NestedInteger.

Each element is either an integer or a list whose elements may also be integers or other lists.

 

Example 1:

Input: s = "324"
Output: 324
Explanation: You should return a NestedInteger object which contains a single integer 324.

Example 2:

Input: s = "[123,[456,[789]]]"
Output: [123,[456,[789]]]
Explanation: 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

 

Constraints:

• 1 <= s.length <= 5 * 104
• s consists of digits, square brackets "[]", negative sign '-', and commas ','.
• s is the serialization of valid NestedInteger.
• All the values in the input are in the range [-106, 106].

Solutions

Solution 1: Recursion

We first judge whether the string $s$ is empty or an empty list. If so, simply return an empty NestedInteger. If $s$ is an integer, we simply return a NestedInteger containing this integer. Otherwise, we traverse the string $s$ from left to right. If the current depth is $0$ and we encounter a comma or the end of the string $s$, we take a substring and recursively call the function to parse the substring and add the return value to the list. Otherwise, if the current encounter is a left parenthesis, we increase the depth by $1$ and continue to traverse. If we encounter a right parenthesis, we decrease the depth by $1$ and continue to traverse.

After the traversal is over, return the answer.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string $s$.

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger:
#  def __init__(self, value=None):
#    """
#    If value is not specified, initializes an empty list.
#    Otherwise initializes a single integer equal to value.
#    """
#
#  def isInteger(self):
#    """
#    @return True if this NestedInteger holds a single integer, rather than a nested list.
#    :rtype bool
#    """
#
#  def add(self, elem):
#    """
#    Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
#    :rtype void
#    """
#
#  def setInteger(self, value):
#    """
#    Set this NestedInteger to hold a single integer equal to value.
#    :rtype void
#    """
#
#  def getInteger(self):
#    """
#    @return the single integer that this NestedInteger holds, if it holds a single integer
#    Return None if this NestedInteger holds a nested list
#    :rtype int
#    """
#
#  def getList(self):
#    """
#    @return the nested list that this NestedInteger holds, if it holds a nested list
#    Return None if this NestedInteger holds a single integer
#    :rtype List[NestedInteger]
#    """
class Solution:
  def deserialize(self, s: str) -> NestedInteger:
    if not s or s == '[]':
      return NestedInteger()
    if s[0] != '[':
      return NestedInteger(int(s))
    ans = NestedInteger()
    depth, j = 0, 1
    for i in range(1, len(s)):
      if depth == 0 and (s[i] == ',' or i == len(s) - 1):
        ans.add(self.deserialize(s[j:i]))
        j = i + 1
      elif s[i] == '[':
        depth += 1
      elif s[i] == ']':
        depth -= 1
    return ans

/**
 * // 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) {
    if ("".equals(s) || "[]".equals(s)) {
      return new NestedInteger();
    }
    if (s.charAt(0) != '[') {
      return new NestedInteger(Integer.parseInt(s));
    }
    NestedInteger ans = new NestedInteger();
    int depth = 0;
    for (int i = 1, j = 1; i < s.length(); ++i) {
      if (depth == 0 && (s.charAt(i) == ',' || i == s.length() - 1)) {
        ans.add(deserialize(s.substring(j, i)));
        j = i + 1;
      } else if (s.charAt(i) == '[') {
        ++depth;
      } else if (s.charAt(i) == ']') {
        --depth;
      }
    }
    return ans;
  }
}

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *   // Constructor initializes an empty nested list.
 *   NestedInteger();
 *
 *   // Constructor initializes a single integer.
 *   NestedInteger(int value);
 *
 *   // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *   bool isInteger() const;
 *
 *   // Return the single integer that this NestedInteger holds, if it holds a single integer
 *   // The result is undefined if this NestedInteger holds a nested list
 *   int getInteger() const;
 *
 *   // Set this NestedInteger to hold a single integer.
 *   void setInteger(int value);
 *
 *   // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *   void add(const NestedInteger &ni);
 *
 *   // Return the nested list that this NestedInteger holds, if it holds a nested list
 *   // The result is undefined if this NestedInteger holds a single integer
 *   const vector<NestedInteger> &getList() const;
 * };
 */
class Solution {
public:
  NestedInteger deserialize(string s) {
    if (s == "" || s == "[]") {
      return NestedInteger();
    }
    if (s[0] != '[') {
      return NestedInteger(stoi(s));
    }
    NestedInteger ans;
    int depth = 0;
    for (int i = 1, j = 1; i < s.size(); ++i) {
      if (depth == 0 && (s[i] == ',' || i == s.size() - 1)) {
        ans.add(deserialize(s.substr(j, i - j)));
        j = i + 1;
      } else if (s[i] == '[') {
        ++depth;
      } else if (s[i] == ']') {
        --depth;
      }
    }
    return ans;
  }
};

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * type NestedInteger struct {
 * }
 *
 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
 * func (n NestedInteger) IsInteger() bool {}
 *
 * // Return the single integer that this NestedInteger holds, if it holds a single integer
 * // The result is undefined if this NestedInteger holds a nested list
 * // So before calling this method, you should have a check
 * func (n NestedInteger) GetInteger() int {}
 *
 * // Set this NestedInteger to hold a single integer.
 * func (n *NestedInteger) SetInteger(value int) {}
 *
 * // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 * func (n *NestedInteger) Add(elem NestedInteger) {}
 *
 * // Return the nested list that this NestedInteger holds, if it holds a nested list
 * // The list length is zero if this NestedInteger holds a single integer
 * // You can access NestedInteger's List element directly if you want to modify it
 * func (n NestedInteger) GetList() []*NestedInteger {}
 */
func deserialize(s string) *NestedInteger {
  ans := &NestedInteger{}
  if s == "" || s == "[]" {
    return ans
  }
  if s[0] != '[' {
    v, _ := strconv.Atoi(s)
    ans.SetInteger(v)
    return ans
  }
  depth := 0
  for i, j := 1, 1; i < len(s); i++ {
    if depth == 0 && (s[i] == ',' || i == len(s)-1) {
      (*ans).Add(*deserialize(s[j:i]))
      j = i + 1
    } else if s[i] == '[' {
      depth++
    } else if s[i] == ']' {
      depth--
    }
  }
  return ans
}

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   If value is provided, then it holds a single integer
 *   Otherwise it holds an empty nested list
 *   constructor(value?: number) {
 *     ...
 *   };
 *
 *   Return true if this NestedInteger holds a single integer, rather than a nested list.
 *   isInteger(): boolean {
 *     ...
 *   };
 *
 *   Return the single integer that this NestedInteger holds, if it holds a single integer
 *   Return null if this NestedInteger holds a nested list
 *   getInteger(): number | null {
 *     ...
 *   };
 *
 *   Set this NestedInteger to hold a single integer equal to value.
 *   setInteger(value: number) {
 *     ...
 *   };
 *
 *   Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
 *   add(elem: NestedInteger) {
 *     ...
 *   };
 *
 *   Return the nested list that this NestedInteger holds,
 *   or an empty list if this NestedInteger holds a single integer
 *   getList(): NestedInteger[] {
 *     ...
 *   };
 * };
 */

function deserialize(s: string): NestedInteger {
  if (s === '' || s === '[]') {
    return new NestedInteger();
  }
  if (s[0] !== '[') {
    return new NestedInteger(+s);
  }
  const ans: NestedInteger = new NestedInteger();
  let depth = 0;
  for (let i = 1, j = 1; i < s.length; ++i) {
    if (depth === 0 && (s[i] === ',' || i === s.length - 1)) {
      ans.add(deserialize(s.slice(j, i)));
      j = i + 1;
    } else if (s[i] === '[') {
      ++depth;
    } else if (s[i] === ']') {
      --depth;
    }
  }
  return ans;
}

Solution 2: Stack

We can use a stack to simulate the recursive process.

We first judge whether the string $s$ is an integer. If so, we simply return a NestedInteger containing this integer. Otherwise, we traverse the string $s$ from left to right. For the character $c$ currently traversed:

• If $c$ is a negative sign, we set the negative sign to true;
• If $c$ is a number, we add the number to the current number $x$, where the initial value of $x$ is $0$;
• If $c$ is a left parenthesis, we push a new NestedInteger onto the stack;
• If $c$ is a right parenthesis or comma, we judge whether the previous character of the current character is a number. If so, we add the current number $x$ to the top NestedInteger of the stack according to the negative sign, and then reset the negative sign to false and the current number $x$ to $0$. If $c$ is a right parenthesis and the size of the current stack is greater than $1$, we pop the top NestedInteger of the stack and add it to the top NestedInteger of the stack.

After the traversal is over, return the top NestedInteger of the stack.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string $s$.

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger:
#  def __init__(self, value=None):
#    """
#    If value is not specified, initializes an empty list.
#    Otherwise initializes a single integer equal to value.
#    """
#
#  def isInteger(self):
#    """
#    @return True if this NestedInteger holds a single integer, rather than a nested list.
#    :rtype bool
#    """
#
#  def add(self, elem):
#    """
#    Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
#    :rtype void
#    """
#
#  def setInteger(self, value):
#    """
#    Set this NestedInteger to hold a single integer equal to value.
#    :rtype void
#    """
#
#  def getInteger(self):
#    """
#    @return the single integer that this NestedInteger holds, if it holds a single integer
#    Return None if this NestedInteger holds a nested list
#    :rtype int
#    """
#
#  def getList(self):
#    """
#    @return the nested list that this NestedInteger holds, if it holds a nested list
#    Return None if this NestedInteger holds a single integer
#    :rtype List[NestedInteger]
#    """
class Solution:
  def deserialize(self, s: str) -> NestedInteger:
    if s[0] != '[':
      return NestedInteger(int(s))
    stk, x, neg = [], 0, False
    for i, c in enumerate(s):
      if c == '-':
        neg = True
      elif c.isdigit():
        x = x * 10 + int(c)
      elif c == '[':
        stk.append(NestedInteger())
      elif c in ',]':
        if s[i - 1].isdigit():
          if neg:
            x = -x
          stk[-1].add(NestedInteger(x))
        x, neg = 0, False
        if c == ']' and len(stk) > 1:
          t = stk.pop()
          stk[-1].add(t)
    return stk.pop()

/**
 * // 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) {
    if (s.charAt(0) != '[') {
      return new NestedInteger(Integer.parseInt(s));
    }
    Deque<NestedInteger> stk = new ArrayDeque<>();
    int x = 0;
    boolean neg = false;
    for (int i = 0; i < s.length(); ++i) {
      char c = s.charAt(i);
      if (c == '-') {
        neg = true;
      } else if (Character.isDigit(c)) {
        x = x * 10 + c - '0';
      } else if (c == '[') {
        stk.push(new NestedInteger());
      } else if (c == ',' || c == ']') {
        if (Character.isDigit(s.charAt(i - 1))) {
          if (neg) {
            x = -x;
          }
          stk.peek().add(new NestedInteger(x));
        }
        x = 0;
        neg = false;
        if (c == ']' && stk.size() > 1) {
          NestedInteger t = stk.pop();
          stk.peek().add(t);
        }
      }
    }
    return stk.peek();
  }
}

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *   // Constructor initializes an empty nested list.
 *   NestedInteger();
 *
 *   // Constructor initializes a single integer.
 *   NestedInteger(int value);
 *
 *   // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *   bool isInteger() const;
 *
 *   // Return the single integer that this NestedInteger holds, if it holds a single integer
 *   // The result is undefined if this NestedInteger holds a nested list
 *   int getInteger() const;
 *
 *   // Set this NestedInteger to hold a single integer.
 *   void setInteger(int value);
 *
 *   // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *   void add(const NestedInteger &ni);
 *
 *   // Return the nested list that this NestedInteger holds, if it holds a nested list
 *   // The result is undefined if this NestedInteger holds a single integer
 *   const vector<NestedInteger> &getList() const;
 * };
 */
class Solution {
public:
  NestedInteger deserialize(string s) {
    if (s[0] != '[') {
      return NestedInteger(stoi(s));
    }
    stack<NestedInteger> stk;
    int x = 0;
    bool neg = false;
    for (int i = 0; i < s.size(); ++i) {
      if (s[i] == '-') {
        neg = true;
      } else if (isdigit(s[i])) {
        x = x * 10 + s[i] - '0';
      } else if (s[i] == '[') {
        stk.push(NestedInteger());
      } else if (s[i] == ',' || s[i] == ']') {
        if (isdigit(s[i - 1])) {
          if (neg) {
            x = -x;
          }
          stk.top().add(NestedInteger(x));
        }
        x = 0;
        neg = false;
        if (s[i] == ']' && stk.size() > 1) {
          auto t = stk.top();
          stk.pop();
          stk.top().add(t);
        }
      }
    }
    return stk.top();
  }
};

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * type NestedInteger struct {
 * }
 *
 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
 * func (n NestedInteger) IsInteger() bool {}
 *
 * // Return the single integer that this NestedInteger holds, if it holds a single integer
 * // The result is undefined if this NestedInteger holds a nested list
 * // So before calling this method, you should have a check
 * func (n NestedInteger) GetInteger() int {}
 *
 * // Set this NestedInteger to hold a single integer.
 * func (n *NestedInteger) SetInteger(value int) {}
 *
 * // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 * func (n *NestedInteger) Add(elem NestedInteger) {}
 *
 * // Return the nested list that this NestedInteger holds, if it holds a nested list
 * // The list length is zero if this NestedInteger holds a single integer
 * // You can access NestedInteger's List element directly if you want to modify it
 * func (n NestedInteger) GetList() []*NestedInteger {}
 */
func deserialize(s string) *NestedInteger {
  if s[0] != '[' {
    v, _ := strconv.Atoi(s)
    ans := NestedInteger{}
    ans.SetInteger(v)
    return &ans
  }
  stk := []*NestedInteger{}
  x := 0
  neg := false
  for i, c := range s {
    if c == '-' {
      neg = true
    } else if c >= '0' && c <= '9' {
      x = x*10 + int(c-'0')
    } else if c == '[' {
      stk = append(stk, &NestedInteger{})
    } else if c == ',' || c == ']' {
      if s[i-1] >= '0' && s[i-1] <= '9' {
        if neg {
          x = -x
        }
        t := NestedInteger{}
        t.SetInteger(x)
        stk[len(stk)-1].Add(t)
      }
      x = 0
      neg = false
      if c == ']' && len(stk) > 1 {
        t := stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        stk[len(stk)-1].Add(*t)
      }
    }
  }
  return stk[0]
}

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   If value is provided, then it holds a single integer
 *   Otherwise it holds an empty nested list
 *   constructor(value?: number) {
 *     ...
 *   };
 *
 *   Return true if this NestedInteger holds a single integer, rather than a nested list.
 *   isInteger(): boolean {
 *     ...
 *   };
 *
 *   Return the single integer that this NestedInteger holds, if it holds a single integer
 *   Return null if this NestedInteger holds a nested list
 *   getInteger(): number | null {
 *     ...
 *   };
 *
 *   Set this NestedInteger to hold a single integer equal to value.
 *   setInteger(value: number) {
 *     ...
 *   };
 *
 *   Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
 *   add(elem: NestedInteger) {
 *     ...
 *   };
 *
 *   Return the nested list that this NestedInteger holds,
 *   or an empty list if this NestedInteger holds a single integer
 *   getList(): NestedInteger[] {
 *     ...
 *   };
 * };
 */

function deserialize(s: string): NestedInteger {
  if (s[0] !== '[') {
    return new NestedInteger(+s);
  }
  const stk: NestedInteger[] = [];
  let x = 0;
  let neg = false;
  for (let i = 0; i < s.length; ++i) {
    if (s[i] === '-') {
      neg = true;
    } else if (s[i] === '[') {
      stk.push(new NestedInteger());
    } else if (s[i] >= '0' && s[i] <= '9') {
      x = x * 10 + s[i].charCodeAt(0) - '0'.charCodeAt(0);
    } else if (s[i] === ',' || s[i] === ']') {
      if (s[i - 1] >= '0' && s[i - 1] <= '9') {
        stk[stk.length - 1].add(new NestedInteger(neg ? -x : x));
      }
      x = 0;
      neg = false;
      if (s[i] === ']' && stk.length > 1) {
        const t = stk.pop()!;
        stk[stk.length - 1].add(t);
      }
    }
  }
  return stk[0];
}