385_迷你语法分析器

难度：中等

题目

给定一个字符串 s 表示一个整数嵌套列表，实现一个解析它的语法分析器并返回解析的结果 NestedInteger 。

列表中的每个元素只可能是整数或整数嵌套列表

示例

示例一：

输入：s = “324”,
输出：324
解释：你应该返回一个 NestedInteger 对象，其中只包含整数值 324。

示例二：

输入：s = “[123,[456,[789]]]”,
输出：[123,[456,[789]]]
解释：返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表：

  1. 一个 integer 包含值 123
  2. 一个包含两个元素的嵌套列表：
    i. 一个 integer 包含值 456
    ii. 一个包含一个元素的嵌套列表
      a. 一个 integer 包含值 789

提示

  • $1 <= s.length <= 5 * 10^4$
  • s 由数字、方括号 “[]”、负号 ‘-‘ 、逗号 ‘,’组成
  • 用例保证 s 是可解析的 NestedInteger
  • 输入中的所有值的范围是 $[-10^6, 10^6]$

解题

题目意思是解析字符串，还原成 NestedInteger 对象，NestedInteger 对象可以实例化成两类，要么是空或者数组，要么是数字

使用 start 来标记起始位置，用来截取一个完整的对象字符串，用 count 来标记层数，当 count 等于 0 时，说明当前字符串为数字，当字符大于 0 时，说明当前字符串为数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public NestedInteger deserialize(String s) {
  if(s.isEmpty()) return new NestedInteger();
  if(s.charAt(0)!='[') return new NestedInteger(Integer.valueOf(s));
  if(s.length()<=2) return new NestedInteger();
  NestedInteger res = new NestedInteger();
  for(int start=1, i=1,count=0; i<s.length();i++){
    // count == 0表示非List，遇到','则递归解析；
    // count > 0，表示已经进入List状态，这时不处理','，
    // 这时的逗号是List里面的，属于子问题，由DFS处理
    if(count==0 && (s.charAt(i)==','|| i==s.length()-1)){
      res.add(deserialize(s.substring(start,i)));
      start = i+1;
    }else if(s.charAt(i)=='['){
      count++;
    }else if(s.charAt(i)==']'){
      count--;
    }
  }
  return res;
}