385. Mini Parser

发表于 | 分类于 | |

385. Mini Parser

题目描述

Given a nested list of integers represented as a string, implement a parser to deserialize it.

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

Note: You may assume that the string is well-formed:

String is non-empty.
String does not contain white spaces.
String contains only digits 0-9, [, - ,, ].

1
2
3
4
5
Example 1:
Given s = "324",
You should return a NestedInteger object which contains a single integer 324.
1
2
3
4
5
6
7
8
9
10
11
Example 2:
Given s = "[123,[456,[789]]]",
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.

题目大意

给定一个字符串表示嵌套列表，实现一个反序列化的解析器。
每个元素代表一个整数或者一个列表。
注意：

  • 非空字符。
  • 字符串不包含空格。
  • 字符串只包含0-9的数字，[ - ] ，。

示例1：
给定 s = "324"

你应该返回一个包含单个数字324的NestedInteger对象

示例2：

给定s = "[123,[456,[789]]]"

你应该返回一个包含两个元素的嵌套列表的NestedInteger对象:

  • 一个数字324
  • 一个包含两个元素的嵌套列表:
    • 一个数字456
    • 一个包含一个元素的嵌套列表：
      • 一个数字789

解题思路

遍历字符串s，记当前字符为char。
如果char为0-9，则使用value数值。
如果char为-，则将符号变量symbol为-1。
如果char为[,则新建一个NestedInteger对象，并压栈。
如果char为]或者,：

  • 如果value非空，则将value * symbol压栈。
  • 将栈顶元素弹出，记为last，如果栈为空，则返回last；如果栈非空，则将last加入栈顶元素的嵌套列表

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public func 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
 *     public func getInteger() -> Int
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public func setInteger(value: Int)
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public func add(elem: NestedInteger)
 *
 *     // 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
 *     public func getList() -> [NestedInteger]
 * }
 */
func deserialize(_ s: String) -> NestedInteger {
    var stack = [NestedInteger]()
    var value: Int? = nil
    var symbol = 1
    for char in s {
        let num = Int(String(char)) ?? -1
        if num >= 0 && num <= 9 {
            value = 10 * (value ?? 0) + num
        }else if char == "-" {
            symbol = -1
        }else if char == "[" {
            stack.append(NestedInteger())
        }else {
            if value != nil {
                let nestedInteger = NestedInteger()
                nestedInteger.setInteger(value! * symbol)
                stack.last?.add(nestedInteger)
                symbol = 1
                value = nil
            }
            if char == "]" {
                let last = stack.removeLast()
                if stack.isEmpty {
                    return last
                }else {
                    stack.last?.add(last)
                }
            }
        }
    }
    let nestedInteger = NestedInteger()
    nestedInteger.setInteger((value ?? 0) * symbol)
    return nestedInteger
}
0%