1.题目基本信息

1.1.题目描述

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

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

1.2.题目地址

https://leetcode.cn/problems/mini-parser/description/

2.解题方法

2.1.解题思路

栈 / 深度优先搜索

2.2.解题步骤

栈思路步骤：

• 第一步，构建维护变量。stack维护栈，栈顶元素维护当前遍历字符的对象所在的嵌套对象

• 第二步，遍历s的每个字符，根据字符的情况更新维护变量stack

深度优先搜索关键：

• 定义并构建深搜函数。index指定dfs中当前指针的位置；每次dfs()获取从s[index]开始的一个元素。

3.解题代码

python代码

class Solution:
    def deserialize(self, s: str) -> NestedInteger:
        # 思路2：栈
        n = len(s)
        # 第一步，构建维护变量。stack维护栈，栈顶元素维护当前遍历字符的对象所在的嵌套对象
        stack = []
        # 第二步，遍历s的每个字符，根据字符的情况更新维护变量stack
        i = 0
        while i < n:
            if s[i] == "[":
                stack.append(NestedInteger())
                i += 1
            elif s[i] == ",":
                i += 1
            elif s[i] == "]":
                if len(stack) > 1:
                    stack[-2].add(stack.pop())
                i += 1
            elif s[i] == "-" or s[i].isdigit():
                flag = 1
                if s[i] == "-":
                    flag = -1
                    i += 1
                j = i
                num = 0
                while j < n and s[j].isdigit():
                    num = num * 10 + int(s[j])
                    j += 1
                i = j
                num *= flag
                if len(stack) > 0:
                    stack[-1].add(NestedInteger(num))
                else:
                    stack.append(NestedInteger(num))
        return stack[-1]

    def deserialize1(self, s: str) -> NestedInteger:
        # 思路1：深度优先搜索
        # 第一步，构建深搜函数。index指定dfs中当前指针的位置；每次dfs()获取从s[index]开始的一个元素
        index = 0
        def dfs() -> NestedInteger:
            nonlocal index
            if s[index] == "[":
                obj = NestedInteger()
                index += 1
                while index < len(s) and s[index] != "]":
                    obj.add(dfs())
                    if s[index] == ",":
                        index += 1
                index += 1
                return obj
            else:
                neg = False
                if s[index] == "-":
                    neg = True
                    index += 1
                if s[index].isdigit():
                    num = 0
                    while index < len(s) and s[index].isdigit():
                        num = num * 10 + int(s[index])
                        index += 1
                    if neg:
                        num = -num
                    return NestedInteger(num)
        return dfs()

c++代码

class Solution {
public:
    NestedInteger deserialize(string s) {
        int n = s.size();
        stack<NestedInteger> st;
        int i = 0;
        while (i < n) {
            if (s[i] == '[') {
                st.push(NestedInteger());
                i++;
            } else if (s[i] == ',') {
                i++;
            } else if (s[i] == ']') {
                if (st.size() > 1) {
                    NestedInteger temp = st.top();
                    st.pop();
                    st.top().add(temp);
                }
                i++;
            } else if (s[i] == '-' || isdigit(s[i])) {
                int flag = 1;
                if (s[i] == '-') {
                    flag = -1;
                    i++;
                }
                int j = i, num = 0;
                while (j < n && isdigit(s[j])) {
                    num = num * 10 + (s[j] - '0');
                    j++;
                }
                num *= flag;
                i = j;
                if (st.size() > 0) {
                    st.top().add(NestedInteger(num));
                } else {
                    st.push(NestedInteger(num));
                }
            }
        }
        return st.top();
    }
};

4.执行结果