package leetcode

import (
	"sort"
	"strconv"
	"strings"
)

type atom struct {
	name string
	cnt  int
}

type atoms []atom

func (this atoms) Len() int           { return len(this) }
func (this atoms) Less(i, j int) bool { return strings.Compare(this[i].name, this[j].name) < 0 }
func (this atoms) Swap(i, j int)      { this[i], this[j] = this[j], this[i] }
func (this atoms) String() string {
	s := ""
	for _, a := range this {
		s += a.name
		if a.cnt > 1 {
			s += strconv.Itoa(a.cnt)
		}
	}
	return s
}

func countOfAtoms(s string) string {
	n := len(s)
	if n == 0 {
		return ""
	}

	stack := make([]string, 0)
	for i := 0; i < n; i++ {
		c := s[i]
		if c == '(' || c == ')' {
			stack = append(stack, string(c))
		} else if isUpperLetter(c) {
			j := i + 1
			for ; j < n; j++ {
				if !isLowerLetter(s[j]) {
					break
				}
			}
			stack = append(stack, s[i:j])
			i = j - 1
		} else if isDigital(c) {
			j := i + 1
			for ; j < n; j++ {
				if !isDigital(s[j]) {
					break
				}
			}
			stack = append(stack, s[i:j])
			i = j - 1
		}
	}

	cnt, deep := make([]map[string]int, 100), 0
	for i := 0; i < 100; i++ {
		cnt[i] = make(map[string]int)
	}
	for i := 0; i < len(stack); i++ {
		t := stack[i]
		if isUpperLetter(t[0]) {
			num := 1
			if i+1 < len(stack) && isDigital(stack[i+1][0]) {
				num, _ = strconv.Atoi(stack[i+1])
				i++
			}
			cnt[deep][t] += num
		} else if t == "(" {
			deep++
		} else if t == ")" {
			num := 1
			if i+1 < len(stack) && isDigital(stack[i+1][0]) {
				num, _ = strconv.Atoi(stack[i+1])
				i++
			}
			for k, v := range cnt[deep] {
				cnt[deep-1][k] += v * num
			}
			cnt[deep] = make(map[string]int)
			deep--
		}
	}
	as := atoms{}
	for k, v := range cnt[0] {
		as = append(as, atom{name: k, cnt: v})
	}
	sort.Sort(as)
	return as.String()
}

func isDigital(v byte) bool {
	if v >= '0' && v <= '9' {
		return true
	}
	return false
}

func isUpperLetter(v byte) bool {
	if v >= 'A' && v <= 'Z' {
		return true
	}
	return false
}

func isLowerLetter(v byte) bool {
	if v >= 'a' && v <= 'z' {
		return true
	}
	return false
}