[Swift]LeetCode385.迷你语法分析器|MiniParser

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10283451.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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, [, - ,, ].

Example 1:

Given s = "324",

You should return a NestedInteger object which contains a single integer 324.

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",

你应该返回一个 NestedInteger 对象，其中只包含整数值 324。

示例 2：

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

返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表：

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

88ms

 1 /**
 2  * // This is the interface that allows for creating nested lists.
 3  * // You should not implement it, or speculate about its implementation
 4  * class NestedInteger {
 5  *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 6  *     public func isInteger() -> Bool
 7  *
 8  *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 9  *     // The result is undefined if this NestedInteger holds a nested list
10  *     public func getInteger() -> Int
11  *
12  *     // Set this NestedInteger to hold a single integer.
13  *     public func setInteger(value: Int)
14  *
15  *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
16  *     public func add(elem: NestedInteger)
17  *
18  *     // Return the nested list that this NestedInteger holds, if it holds a nested list
19  *     // The result is undefined if this NestedInteger holds a single integer
20  *     public func getList() -> [NestedInteger]
21  * }
22  */
23 class Solution {
24     func deserialize(_ s: String) -> NestedInteger {
25     if s[s.startIndex] != "[" {
26         let n = Int(s)!
27         let nest = NestedInteger()
28         nest.setInteger(n)
29         return nest
30     }
31     var stack = [NestedInteger]()
32     var num = ""
33     for c in s.characters {
34         if c == "[" {
35             stack.append(NestedInteger())
36         } else if c == "]"{
37             let last = stack.removeLast()
38             if !num.isEmpty {
39                 let n = Int(num)!
40                 let nest = NestedInteger()
41                 nest.setInteger(n)
42                 last.add(nest)
43                 num = ""
44             }
45             if stack.isEmpty {
46                 return last
47             }
48             if last.isInteger() {
49                 stack[stack.count-1].setInteger(last.getInteger())
50             } else {
51                 stack[stack.count-1].add(last)
52             }
53         } else if c == "," {
54             if let n = Int(num) {
55                 let nest = NestedInteger()
56                 nest.setInteger(n)
57                 stack[stack.count-1].add(nest)
58                 num = ""
59             }
60         } else {
61             num.append(c)
62         }
63     }
64     return NestedInteger()
65   }    
66 }

100ms

 1 extension String {
 2     func digitInt(offset: String.Index) -> Int {
 3         return Int(self[offset].unicodeScalars.first!.value - "0".unicodeScalars.first!.value)
 4     }
 5 }
 6 
 7 fileprivate let one2nine = CharacterSet(charactersIn: "123456789")
 8 fileprivate let zero2nine = CharacterSet(charactersIn: "0123456789")
 9 
10 class Solution {
11     
12     //listOrInt:    list | integer
13     //list:         [ listOrInt (, listOrInt)* ]
14     //integer:      -? (1-9)?(0-9)*
15     
16     private func consumeListOrInt(offset: String.Index, s: String) -> (parsed: NestedInteger, offset: String.Index)? {
17         if let consumedList = consumeList(offset: offset, s: s) {
18             return consumedList
19         }
20         if let consumedInt = consumeInt(offset: offset, s: s) {
21             return consumedInt
22         }
23         return nil
24     }
25     
26     private func consumeList(offset: String.Index, s: String) -> (parsed: NestedInteger, offset: String.Index)? {
27         guard s[offset] == "[" else {
28             return nil
29         }
30         
31         let result = NestedInteger()
32         var newOffset = s.index(after: offset)
33         if let firstElem = consumeListOrInt(offset: newOffset, s: s) {
34             result.add(firstElem.parsed)
35             newOffset = firstElem.offset
36             while true {
37                 guard s[newOffset] == "," else {
38                     break
39                 }
40                 newOffset = s.index(after: newOffset)
41                 guard let elem = consumeListOrInt(offset: newOffset, s: s) else {
42                     break
43                 }
44                 newOffset = elem.offset
45                 result.add(elem.parsed)
46             }
47         }
48         
49         guard s[newOffset] == "]" else {
50             return nil;
51         }
52         return (result, s.index(after: newOffset))
53     }
54     
55     private func consumeInt(offset: String.Index, s: String) -> (parsed: NestedInteger, offset: String.Index)? {
56         let result = NestedInteger()
57         var integer: Int = 0
58         var positive = true
59         var newOffset = offset
60         if s[offset] == "-" {
61             positive = false
62             newOffset = s.index(after: offset)
63         }
64         guard newOffset < s.endIndex else {
65             return nil
66         }
67         if s[newOffset] == "0" {
68             result.setInteger(0)
69             return (result, s.index(after: newOffset))
70         }
71         guard one2nine.contains(s[newOffset].unicodeScalars.first!) else {
72             return nil
73         }
74         integer = s.digitInt(offset: newOffset) * (positive ? 1 : -1)
75         newOffset = s.index(after: newOffset)
76         while true {
77             guard newOffset < s.endIndex else {
78                 break
79             }
80             guard zero2nine.contains(s[newOffset].unicodeScalars.first!) else {
81                 break
82             }
83             integer = integer * 10 + s.digitInt(offset: newOffset) * (positive ? 1 : -1)
84             newOffset = s.index(after: newOffset)
85         }
86         result.setInteger(integer)
87         return (result, newOffset)
88     }
89     
90     func deserialize(_ s: String) -> NestedInteger {
91         guard let (parsed, offset) = consumeListOrInt(offset: s.startIndex, s: s) else {
92             fatalError()
93         }
94         if offset != s.endIndex {
95             fatalError()
96         }
97         return parsed
98     }
99 }

10120ms

 1 class Solution {
 2     func deserialize(_ s: String) -> NestedInteger {
 3         if s.count == 0 {return NestedInteger()}
 4         if s[0] != "[" {return NestedInteger(Int(atoi(s)))}
 5         if s.count <= 2 {return NestedInteger()}
 6         var res:NestedInteger = NestedInteger()
 7         var start:Int = 1
 8         var cnt:Int = 0
 9         for i in 1..<s.count
10         {
11             if cnt == 0 && (s[i] == "," || i == s.count - 1)
12             {
13                 res.add(deserialize(s.subString(start, i - start)))
14                 start = i + 1
15             }
16             else if s[i] == "[" {cnt += 1}
17             else if s[i] == "]" {cnt -= 1}
18         }
19         return res
20     }
21 }
22 
23 extension String {        
24     //subscript函数可以检索数组中的值
25     //直接按照索引方式截取指定索引的字符
26     subscript (_ i: Int) -> Character {
27         //读取字符
28         get {return self[index(startIndex, offsetBy: i)]}
29     }
30     
31     // 截取字符串：指定索引和字符数
32     // - begin: 开始截取处索引
33     // - count: 截取的字符数量
34     func subString(_ begin:Int,_ count:Int) -> String {
35         let start = self.index(self.startIndex, offsetBy: max(0, begin))
36         let end = self.index(self.startIndex, offsetBy:  min(self.count, begin + count))
37         return String(self[start..<end]) 
38     }
39 }