LeetCode 第385题：迷你语法分析器

📖 文章摘要

本文详细解析LeetCode第385题“迷你语法分析器”，这是一道字符串处理题。文章提供了基于递归下降解析的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升字符串处理能力的读者。

核心知识点： 字符串、递归、语法分析 难度等级： 中等 推荐人群： 具有基础算法知识，想要提升字符串处理能力的程序员

题目描述

给定一个用字符串表示的整数的嵌套列表，实现一个解析它的语法分析器。

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

示例

示例 1：

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

示例 2：

输入：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 表达式

解题思路

本题可以使用递归下降解析解决：

1. 定义NestedInteger类
2. 实现解析整数的方法
3. 实现解析列表的方法
4. 处理特殊情况

时间复杂度： O(n) 空间复杂度： O(n)

图解思路

解析流程

步骤	操作	说明
1	检查当前字符	判断类型
2	解析整数	处理数字
3	解析列表	处理嵌套
4	返回结果	构建对象

状态转换

状态	输入	输出	说明
整数	数字	NestedInteger	解析整数
列表	[	NestedInteger	解析列表
结束	]	返回	结束解析

代码实现

C# 实现

public class NestedInteger {
    private int? value;
    private List<NestedInteger> list;
    
    public NestedInteger() {
        list = new List<NestedInteger>();
    }
    
    public NestedInteger(int value) {
        this.value = value;
    }
    
    public bool IsInteger() {
        return value.HasValue;
    }
    
    public int GetInteger() {
        return value.Value;
    }
    
    public void SetInteger(int value) {
        this.value = value;
    }
    
    public void Add(NestedInteger ni) {
        list.Add(ni);
    }
    
    public IList<NestedInteger> GetList() {
        return list;
    }
}

public class Solution {
    private int index = 0;
    
    public NestedInteger Deserialize(string s) {
        if (s[index] == '[') {
            index++;
            NestedInteger ni = new NestedInteger();
            while (s[index] != ']') {
                ni.Add(Deserialize(s));
                if (s[index] == ',') {
                    index++;
                }
            }
            index++;
            return ni;
        } else {
            bool negative = false;
            if (s[index] == '-') {
                negative = true;
                index++;
            }
            int num = 0;
            while (index < s.Length && char.IsDigit(s[index])) {
                num = num * 10 + (s[index] - '0');
                index++;
            }
            if (negative) {
                num = -num;
            }
            return new NestedInteger(num);
        }
    }
}

Python 实现

class NestedInteger:
    def __init__(self, value=None):
        self.value = value
        self.list = []
        
    def isInteger(self) -> bool:
        return self.value is not None
        
    def getInteger(self) -> int:
        return self.value
        
    def setInteger(self, value: int) -> None:
        self.value = value
        
    def add(self, elem: 'NestedInteger') -> None:
        self.list.append(elem)
        
    def getList(self) -> List['NestedInteger']:
        return self.list

class Solution:
    def __init__(self):
        self.index = 0
        
    def deserialize(self, s: str) -> NestedInteger:
        if s[self.index] == '[':
            self.index += 1
            ni = NestedInteger()
            while s[self.index] != ']':
                ni.add(self.deserialize(s))
                if s[self.index] == ',':
                    self.index += 1
            self.index += 1
            return ni
        else:
            negative = False
            if s[self.index] == '-':
                negative = True
                self.index += 1
            num = 0
            while self.index < len(s) and s[self.index].isdigit():
                num = num * 10 + int(s[self.index])
                self.index += 1
            if negative:
                num = -num
            return NestedInteger(num)

C++ 实现

class NestedInteger {
private:
    int value;
    bool isInt;
    vector<NestedInteger> list;
    
public:
    NestedInteger() : isInt(false) {}
    NestedInteger(int value) : value(value), isInt(true) {}
    
    bool isInteger() const {
        return isInt;
    }
    
    int getInteger() const {
        return value;
    }
    
    void setInteger(int value) {
        this->value = value;
        isInt = true;
    }
    
    void add(const NestedInteger &ni) {
        list.push_back(ni);
    }
    
    const vector<NestedInteger> &getList() const {
        return list;
    }
};

class Solution {
private:
    int index = 0;
    
public:
    NestedInteger deserialize(string s) {
        if (s[index] == '[') {
            index++;
            NestedInteger ni;
            while (s[index] != ']') {
                ni.add(deserialize(s));
                if (s[index] == ',') {
                    index++;
                }
            }
            index++;
            return ni;
        } else {
            bool negative = false;
            if (s[index] == '-') {
                negative = true;
                index++;
            }
            int num = 0;
            while (index < s.length() && isdigit(s[index])) {
                num = num * 10 + (s[index] - '0');
                index++;
            }
            if (negative) {
                num = -num;
            }
            return NestedInteger(num);
        }
    }
};

执行结果

C# 实现

• 执行用时：92 ms
• 内存消耗：24.8 MB

Python 实现

• 执行用时：28 ms
• 内存消耗：13.2 MB

C++ 实现

• 执行用时：4 ms
• 内存消耗：8.4 MB

性能对比

语言	执行用时	内存消耗	特点
C++	4 ms	8.4 MB	执行效率最高，内存占用最小
Python	28 ms	13.2 MB	代码简洁，内存占用适中
C#	92 ms	24.8 MB	类型安全，内存占用较大

代码亮点

1. 🎯 使用递归下降解析处理嵌套结构
2. 💡 空间复杂度优化
3. 🔍 处理边界情况
4. 🎨 代码结构清晰，易于维护

常见错误分析

1. 🚫 未处理负数
2. 🚫 解析错误
3. 🚫 边界条件处理错误
4. 🚫 递归深度问题

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
递归下降	O(n)	O(n)	清晰，易维护	递归开销
迭代	O(n)	O(n)	无递归开销	代码复杂

相关题目

• LeetCode 394. 字符串解码 - 中等
• LeetCode 726. 原子的数量 - 困难
• LeetCode 736. Lisp 语法解析 - 困难

---

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第385题。

---

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

• 👍 点个赞，让更多人看到这篇文章
• 📁 收藏文章，方便后续查阅复习
• 🔔 关注作者，获取更多高质量算法题解
• 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！