726.原子的数量

解法一：栈

给定一个化学式formula（作为字符串），返回每种原子的数量。
原子总是以一个大写字母开始，接着跟随0个或任意个小写字母，表示原子的名字。
如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。例如，H2O 和 H2O2 是可行的，但 H1O2 这个表达是不可行的。
两个化学式连在一起是新的化学式。例如 H2O2He3Mg4 也是化学式。
一个括号中的化学式和数字（可选择性添加）也是化学式。例如 (H2O2) 和 (H2O2)3 是化学式。
给定一个化学式，输出所有原子的数量。格式为：第一个（按字典序）原子的名子，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。
示例 1:

输入: 
formula = "H2O"
输出: "H2O"
解释: 
原子的数量是 {'H': 2, 'O': 1}。

示例 2:

输入: 
formula = "Mg(OH)2"
输出: "H2MgO2"
解释: 
原子的数量是 {'H': 2, 'Mg': 1, 'O': 2}。

示例 3:

输入: 
formula = "K4(ON(SO3)2)2"
输出: "K4N2O14S4"
解释: 
原子的数量是 {'K': 4, 'N': 2, 'O': 14, 'S': 4}。

注意:

所有原子的第一个字母为大写，剩余字母都是小写。
formula的长度在[1, 1000]之间。
formula只包含字母、数字和圆括号，并且题目中给定的是合法的化学式。
解法一：栈

func isDigit(b byte) bool {
    return '0' <= b && b <= '9'
}

func isLower(b byte) bool {
    return 'a' <=b && b <= 'z'
}
func countOfAtoms(formula string) string {
    var res string
    stackArr := []map[string]int{{}}
    i, length := 0, len(formula)
    // 计算当前数字
    parseNum := func() int {
        var v int
        if i == length || !isDigit(formula[i]) {
            // 最后一个或者下一个不是数字
            return 1
        }
        for ; i< length && isDigit(formula[i]); i++ {
            // 必须这么 byte 转 int 才能得到其十进制
            v = v *10 + int(formula[i] - '0')
        }
        return v
    }
    for i < length {
        switch formula[i] {
            case '(':
            stackArr = append(stackArr, map[string]int{})
            i++
            case ')':
            var tempMap map[string]int
            tempMap, stackArr = stackArr[len(stackArr)-1], stackArr[:len(stackArr)-1]
            i++
            multiple := parseNum()
            for key, val := range tempMap {
                stackArr[len(stackArr)-1][key] += multiple * val
            }
            default:
            start := i
            i++
            for ; i < length && isLower(formula[i]);i++ {
            }
            name := formula[start:i]
            stackArr[len(stackArr)-1][name] += parseNum()
        }
    }
    // 排序
    mp := stackArr[0]
    sortString := make([]string, 0, len(mp))
    for key := range mp {
        sortString = append(sortString, key)
    }
    sort.Strings(sortString)

    for _, key := range sortString {
        res += key
        if v := mp[key]; v> 1 {
            res += strconv.Itoa(v)
        }
    }
    return res
}

解法一：栈