385. 迷你语法分析器.md

385. 迷你语法分析器

题目传送门

点击这里

解题思路

这道设计题有点意思，预先定义好了方法然后要构建出s要表达的结构内部，很像括号匹配那种字符串题，因为存在嵌套结构，可以使用dfs来深层遍历统计。又因为类似于括号匹配的思路，这道题用栈也可以做。

代码

/**
 * // 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 {}
 */
func deserialize(s string) *NestedInteger {
    // 首先要清楚Nest这个数据结构的方法，可以查询是否为单个整数且可以获得这个单个整数，可以对该数据结构设定单个整数值且可以对其添加Next嵌套结构，可以获取里面的Next嵌套结构
    // 使用dfs的方法来做
    // dfs的目的就是将s中的各个整数添加到我们的结果实例中
    // 如果碰到[]说明是嵌套结构
    i := 0
    var dfs func() *NestedInteger 
    dfs = func() *NestedInteger {
        n := new(NestedInteger)
        if s[i] == '[' {
            i ++ 
            for s[i] != ']' {
                // 如果是是[xx,[xx,[xx]]]这种嵌套多层的，就用dfs来添加，add方法是预先定义好的实例添加嵌套结构方法。
                n.Add(*dfs())
                if s[i] == ',' {
                    // 如果不只一个，则继续添加。
                    i ++
                }
            }
            i ++ // 此时索引i处s[i] == ']'，索引加1继续向后
            return n
        }

        var f bool 
        if s[i] == '-' {
            f = true
            i ++
        }
        sum := 0
        // 向后遍历把数字添加进来，unicode.IsDigit方法是内置的判断是否为数字的方法
        for ;i < len(s) &&  unicode.IsDigit(rune(s[i]));i ++ {
            sum = sum * 10 + int(s[i]-'0')
        }
        if f {
            sum = -sum
        }
        // 调用实例预先定义好的set方法将单个数字添加
        n.SetInteger(sum)
        return n
    }
    return dfs()
}

/**
 * // 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 {}
 */
func deserialize(s string) *NestedInteger {
    // 用完dfs的方法，可以感觉到这道题和括号匹配那种题想法很像，所以也可以使用栈来做。
    if s[0] != '[' {
        num, _ := strconv.Atoi(s)
		n := &NestedInteger{}
		n.SetInteger(num)
		return n
    }
    stack := []*NestedInteger{}
    var f bool
    sum := 0
    for i, v := range s {
        // 如果是-或者是数字，将数字统计
        if v == '-' {
            f = true
        } else if unicode.IsDigit(v) {
			sum = sum*10 + int(v-'0')
        } else if v == '[' {
            // 如果是[符号，则建立新的实例压入栈内，
            stack = append(stack, &NestedInteger{})
        } else if v == ',' || v == ']' {
            // 如果是,或者]，将存好的sum放入栈内最后一个实例中
            if unicode.IsDigit(rune(s[i-1])) { // 这个地方主要是用来判断]]]这种情况
                if f {
                    sum = -sum
                }
                n := new(NestedInteger)
                n.SetInteger(sum)
                stack[len(stack)-1].Add(*n)
                sum = 0
                f = false
            }
            if v == ']' && len(stack) > 1 {
                stack[len(stack)-2].Add(*stack[len(stack)-1])
                stack = stack[:len(stack)-1]
            }
        }
    }
    return stack[len(stack)-1]
}