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

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

解题思路 #

将一个嵌套的数据结构中的数字转换成 NestedInteger 数据结构。
这一题用栈一层一层的处理就行。有一些比较坑的特殊的边界数据见测试文件。这一题正确率比很多 Hard 题还要低的原因应该是没有理解好题目和边界测试数据没有考虑到。NestedInteger 这个数据结构笔者实现了一遍，见代码。

代码 #


package leetcode

import (
	"fmt"
	"strconv"
)

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * type NestedInteger struct {
 * }
 *
 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
 * func (n NestedInteger) 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
 * // So before calling this method, you should have a check
 * func (n NestedInteger) GetInteger() int {}
 *
 * // Set this NestedInteger to hold a single integer.
 * func (n *NestedInteger) SetInteger(value int) {}
 *
 * // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 * func (n *NestedInteger) Add(elem NestedInteger) {}
 *
 * // Return the nested list that this NestedInteger holds, if it holds a nested list
 * // The list length is zero if this NestedInteger holds a single integer
 * // You can access NestedInteger's List element directly if you want to modify it
 * func (n NestedInteger) GetList() []*NestedInteger {}
 */

// NestedInteger define
type NestedInteger struct {
	Num  int
	List []*NestedInteger
}

// IsInteger define
func (n NestedInteger) IsInteger() bool {
	if n.List == nil {
		return true
	}
	return false
}

// GetInteger define
func (n NestedInteger) GetInteger() int {
	return n.Num
}

// SetInteger define
func (n *NestedInteger) SetInteger(value int) {
	n.Num = value
}

// Add define
func (n *NestedInteger) Add(elem NestedInteger) {
	n.List = append(n.List, &elem)
}

// GetList define
func (n NestedInteger) GetList() []*NestedInteger {
	return n.List
}

// Print define
func (n NestedInteger) Print() {
	if len(n.List) != 0 {
		for _, v := range n.List {
			if len(v.List) != 0 {
				v.Print()
				return
			}
			fmt.Printf("%v ", v.Num)
		}
	} else {
		fmt.Printf("%v ", n.Num)
	}
	fmt.Printf("\n")
}

func deserialize(s string) *NestedInteger {
	stack, cur := []*NestedInteger{}, &NestedInteger{}
	for i := 0; i < len(s); {
		switch {
		case isDigital(s[i]) || s[i] == '-':
			j := 0
			for j = i + 1; j < len(s) && isDigital(s[j]); j++ {
			}
			num, _ := strconv.Atoi(s[i:j])
			next := &NestedInteger{}
			next.SetInteger(num)
			if len(stack) > 0 {
				stack[len(stack)-1].List = append(stack[len(stack)-1].GetList(), next)
			} else {
				cur = next
			}
			i = j
		case s[i] == '[':
			next := &NestedInteger{}
			if len(stack) > 0 {
				stack[len(stack)-1].List = append(stack[len(stack)-1].GetList(), next)
			}
			stack = append(stack, next)
			i++
		case s[i] == ']':
			cur = stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			i++
		case s[i] == ',':
			i++
		}
	}
	return cur
}

⬅️上一页

下一页➡️