GoJava算法之迷你语法分析器示例详解

GoJava算法之迷你语法分析器示例详解

目录

迷你语法分析器

方法一:深度优先遍历(Java)

方法二:栈(Go)

迷你语法分析器

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

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

示例 1:

输入:s = "324",

输出:324

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

示例 2:

输入:s = "[123,[456,[789]]]",

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

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

一个 integer 包含值 123

一个包含两个元素的嵌套列表:

i. 一个 integer 包含值 456

ii. 一个包含一个元素的嵌套列表

a. 一个 integer 包含值 789  

提示:

1 <= s.length <= 5 * 104

s 由数字、方括号 "[]"、负号 '-' 、逗号 ','组成

用例保证 s 是可解析的 NestedInteger

输入中的所有值的范围是 [-106, 106]

方法一:深度优先遍历(Java)

根据题意,一个 NestedInteger 实例只能包含下列两部分之一:1)一个整数;2)一个列表。

列表中的每个元素都是一个 NestedInteger 实例。据此,NestedInteger 是通过递归定义的,因此也可以用递归的方式来解析。

注意序列化的String,有2个特殊含义,导致不能用String.split()。否则实现起来会比较困难。

逗号: 表示分割“同层级”的元素

中括号[] : 表示1个List,可以有兄弟节点Integer。

如果用逗号分割,可能会割裂了[]的List含义。

class Solution { int index = 0; public NestedInteger deserialize(String s) { if (s.charAt(index) == '[') { index++; NestedInteger ni = new NestedInteger(); while (s.charAt(index) != ']') { ni.add(deserialize(s)); if (s.charAt(index) == ',') { index++; } } index++; return ni; } else { boolean negative = false; if (s.charAt(index) == '-') { negative = true; index++; } int num = 0; while (index < s.length() && Character.isDigit(s.charAt(index))) { num = num * 10 + s.charAt(index) - '0'; index++; } if (negative) { num *= -1; } return new NestedInteger(num); } } }

时间复杂度:O(n)

空间复杂度:O(n)

方法二:栈(Go)

我们只需关注字符串s中的[],字符,其他字符均可转为数字,初始化栈时,将一个空的NestedInteger加入其中,防止越界。

顺序遍历,3 种情况:

[ :新建列表,入栈

数字和-:累加字符串

],:字符串加完,加入列表

]出栈,结果加入上级列表

func deserialize(s string) *NestedInteger { if s[0] != '[' { integer, _ := strconv.Atoi(s) nestedInteger := &NestedInteger{} nestedInteger.SetInteger(integer) return nestedInteger } stack, integer := []*NestedInteger{}, "" for _, ch := range s { switch ch { case '[': stack = append(stack, &NestedInteger{}) // 入栈 case ']': fallthrough case ',': if integer != "" { int, _ := strconv.Atoi(integer) nestedInteger := NestedInteger{} nestedInteger.SetInteger(int) stack[len(stack) - 1].Add(nestedInteger) integer = "" } if ch == ']' && len(stack) > 1 { // 出栈 stack[len(stack) - 2].Add(*stack[len(stack) - 1]) stack = stack[:len(stack) - 1] } default: integer += string(ch) } } return stack[len(stack) - 1] }

时间复杂度:O(n)

空间复杂度:O(n)

以上就是Go Java 算法之迷你语法分析器示例详解的详细内容,更多关于Go Java 算法语法分析器的资料请关注易知道(ezd.cc)其它相关文章!

推荐阅读