摘要

在日常开发中，我们经常会遇到需要解析字符串的场景，比如配置文件、日志格式，甚至是网络传输中的 JSON 数据。这道题就类似于一个“小型 JSON 解析器”，给定一个描述嵌套列表的字符串，要求我们把它还原成嵌套的数据结构 NestedInteger。

本文会从题目描述入手，逐步分析如何用栈的方式来解析字符串，并给出 Swift 的完整解法与运行示例。最后，我们也会结合实际场景聊聊这个题目背后的工程意义。

描述

题目的输入是一个字符串 s，它可能是：

1. 单个整数，比如 "324"。
2. 一个嵌套的整数列表，比如 "[123,[456,[789]]]"。

目标是返回一个 NestedInteger 对象。这个类已经预定义好，支持以下操作：

• isInteger()：判断是否是单个整数。
• getInteger()：获取整数值。
• getList()：获取嵌套列表。
• add(_ elem: NestedInteger)：往列表里添加一个元素。

换句话说，我们要写一个语法分析器，把字符串转换成 NestedInteger。

题解答案

常见的解析方法有两种：

1. 递归法：遇到 [ 就递归解析子列表，遇到 ] 就返回。
2. 栈法：遍历字符串，遇到 [ 就新建一个列表对象压栈，遇到 ] 就出栈并加入上层。

这里我们采用 栈法，因为更直观，也更接近手动实现一个 JSON 解析器的过程。

题解代码分析

完整 Swift 实现如下：

import Foundation

// 模拟 LeetCode 提供的 NestedInteger 类
class NestedInteger {
    private var integer: Int?
    private var list: [NestedInteger] = []
    
    init() {}
    init(_ value: Int) {
        self.integer = value
    }
    
    func isInteger() -> Bool {
        return integer != nil
    }
    
    func getInteger() -> Int? {
        return integer
    }
    
    func setInteger(_ value: Int) {
        self.integer = value
    }
    
    func add(_ elem: NestedInteger) {
        list.append(elem)
    }
    
    func getList() -> [NestedInteger] {
        return list
    }
    
    // 方便打印调试
    func toString() -> String {
        if let value = integer {
            return "\(value)"
        } else {
            return "[" + list.map { $0.toString() }.joined(separator: ",") + "]"
        }
    }
}

class Solution {
    func deserialize(_ s: String) -> NestedInteger {
        // 如果输入是单个整数，直接返回
        if let value = Int(s) {
            return NestedInteger(value)
        }
        
        var stack: [NestedInteger] = []
        var numBuffer = ""
        var negative = false
        var current: NestedInteger? = nil
        
        for char in s {
            if char == "[" {
                let ni = NestedInteger()
                if let top = stack.last {
                    top.add(ni)
                }
                stack.append(ni)
            } else if char == "]" {
                if !numBuffer.isEmpty {
                    let num = (negative ? -1 : 1) * Int(numBuffer)!
                    stack.last?.add(NestedInteger(num))
                    numBuffer = ""
                    negative = false
                }
                current = stack.popLast()
            } else if char == "," {
                if !numBuffer.isEmpty {
                    let num = (negative ? -1 : 1) * Int(numBuffer)!
                    stack.last?.add(NestedInteger(num))
                    numBuffer = ""
                    negative = false
                }
            } else if char == "-" {
                negative = true
            } else if char.isNumber {
                numBuffer.append(char)
            }
        }
        
        return current!
    }
}

代码解析

1. NestedInteger 类：我们自己实现一个简化版，方便测试。

2. deserialize() 方法：

   • 如果整个字符串是单个整数，直接返回。

   • 用栈来保存当前的嵌套结构。

   • 遍历字符串：

     • 遇到 [：新建一个列表对象，压入栈。
     • 遇到数字或 -：存入缓冲区，等到完整数字解析完成再入栈。
     • 遇到 , 或 ]：把缓冲区里的数字变成 NestedInteger 对象，加入当前列表。

   • 最后返回栈顶的对象。

这种方法跟手动解析 JSON 或 XML 很像，工程里也常见。

示例测试及结果

我们写一个小 demo 来测试：

let solution = Solution()

let ex1 = "324"
let result1 = solution.deserialize(ex1)
print("输入: \(ex1)")
print("输出: \(result1.toString())\n")

let ex2 = "[123,[456,[789]]]"
let result2 = solution.deserialize(ex2)
print("输入: \(ex2)")
print("输出: \(result2.toString())\n")

运行结果：

输入: 324
输出: 324

输入: [123,[456,[789]]]
输出: [123,[456,[789]]]

这跟题目要求完全一致。

时间复杂度

• 我们只遍历了一次字符串，每个字符都处理一次，所以 O(n)。
• 数字解析和栈操作都是常量时间。

空间复杂度

• 栈的深度最多等于嵌套层数。
• 所以空间复杂度是 O(n)，主要用于存储结果对象和栈。

总结

这道题看起来是算法题，其实就是一个小型的 语法解析器。
它考察了两个核心点：

1. 如何设计数据结构来表达嵌套关系。
2. 如何用栈来解析字符串，避免递归层数过深。

在实际场景中，这个思路非常有用，比如：

• 写一个轻量级的配置解析器（像 JSON、YAML）。
• 解析游戏关卡脚本，描述嵌套的任务和事件。
• 从日志中提取嵌套的数据结构，方便分析。

所以，这不仅仅是一道刷题，更是把我们带入了“编译原理”的世界。