385.迷你语法分析器
385.迷你语法分析器
题解
题目：给一个字符串，返回一个NestedInteger嵌套列表，第一个123是一个NestedInteger，里面包含了123元素
输入：s = "[123,[456,[789]]]", 输出：[123,[456,[789]]] 解释：返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表： 1. 一个 integer 包含值 123 2. 一个包含两个元素的嵌套列表： i. 一个 integer 包含值 456 ii. 一个包含一个元素的嵌套列表 a. 一个 integer 包含值 789
并且给定两个函数SetInteger和Add，第一个是往NestedInteger中加入元素，第二个是往NestedInteger嵌套NestedInteger
思路：
- 遍历字符串
- 遇到[，说明后面是一个新的NestedInteger对象，创建NestedInteger并加入栈中
- 遇到-，说明元素的负数，把negative赋值为true
- 遇到0~9，num = num*10 + int(ch-‘0’)
- 遇到是,或者],并且前一个数是数字，即[123]或者[123,23],新建一个NestedInteger对象，temp.SetInteger(num)把元素加入这个对象中，stack[len(stack)-1].Add(*temp)并将这个对象加入到栈顶对象中
- 如果],并且栈的数量大于1，即[1[2]]，这个时候把栈顶对象加入到栈第二个对象中，并弹出栈顶
代码
/* type NestedInteger struct {} func (n *NestedInteger) SetInteger(value int) {} func (n *NestedInteger) Add(elem NestedInteger) {} */ func deserialize(s string) *NestedInteger { if s[0] != '[' { num, _ := strconv.Atoi(s) temp := &NestedInteger{} temp.SetInteger(num) return temp } stack, num, negative := []*NestedInteger{}, 0, false for i, ch := range s { if ch == '[' { temp := &NestedInteger{} stack = append(stack, temp) } else if ch == '-' { negative = true } else if ch >= '0' && ch <= '9' { num = num*10 + int(ch-'0') } else if (ch == ',' || ch == ']') && s[i-1] >= '0' && s[i-1] <= '9' { if negative { num = -num } temp := &NestedInteger{} temp.SetInteger(num) stack[len(stack)-1].Add(*temp) num = 0 negative = false } if ch == ']' && len(stack) > 1 { temp1, temp2 := stack[len(stack)-1], stack[len(stack)-2] temp2.Add(*temp1) stack = stack[:len(stack)-1] } } return stack[len(stack)-1] }
