How to Decode Nested Strings Using a Stack in Go

According to the problem specification, a string is encoded as k[encoded_string]. To decode it, we must capture the repeat count k outside the brackets and the encoded_string inside, then expand the string.

For nested patterns such as 2[a3[b]], the inner segment 3[b] is decoded first to bbb, producing 2[abbb]. The outer repeat count (2) can then be applied. This requires temporarily storing the outer count until the inner decoding finishes.

The solution uses a stack: when encountering a left bracket [, push the current repeat count and the current accumulated string onto their respective stacks, then reset them for the inner segment. When a right bracket ] appears, pop the previous string and count, repeat the current string that many times, and concatenate it with the popped string. This naturally respects the nested decoding order.

Example walkthrough with 3[a]2[bc] demonstrates the push/pop sequence. Encountering [ pushes the count (3) and the previous string (empty). After processing a, the closing bracket triggers a pop, repeating a three times to form aaa. The same steps repeat for 2[bc], yielding bcbc, and the final result is aaabc bc.

The complete Go implementation follows.

func decodeString(s string) string {
    // a6[c]
    // Traverse left to right, curStr and curNum record current values
    // 1. When encountering '[', push current num and str onto stacks, then reset them for reuse inside brackets
    // 2. Example: when traversing to 'c', curStr = "c", curNum = 0
    // 3. When encountering ']', pop, combine previous string + repeated current string = new string, e.g., expand a6[c] to acccccc
    curStr, strStack := "", []string{}
    curNum, numStack := 0, []int{}
    for _, v := range s {
        if v >= '0' && v <= '9' {
            curNum = curNum*10 + int(v-'0')
        } else if v == '[' {
            strStack = append(strStack, curStr)
            numStack = append(numStack, curNum)
            curStr = ""
            curNum = 0
        } else if v == ']' {
            preStr := strStack[len(strStack)-1]
            preNum := numStack[len(numStack)-1]
            curStr = preStr + strings.Repeat(curStr, preNum)
            strStack = strStack[:len(strStack)-1]
            numStack = numStack[:len(numStack)-1]
        } else {
            curStr += string(v)
        }
    }
    return curStr
}