Decode string

Expand a run-length pattern like "3[a2[c]]" into "accaccacc", using a stack to remember what to return to when each bracket closes.

The idea

Every "[" starts a group whose repeat count and whose outer text (built so far) need to wait until the matching "]". Pushing both onto their own stacks is exactly a save, and popping them on "]" is exactly a restore: the inner text gets repeated and glued back onto what came before it.

Code

public static string DecodeString(string s) {
    var counts = new Stack<int>();
    var parts = new Stack<string>();
    string cur = "";
    int num = 0;
    foreach (char c in s) {
        if (char.IsDigit(c)) num = num * 10 + (c - '0');
        else if (c == '[') {
            counts.Push(num); parts.Push(cur);
            num = 0; cur = "";
        }
        else if (c == ']') {
            int k = counts.Pop();
            cur = parts.Pop() + string.Concat(Enumerable.Repeat(cur, k));
        }
        else cur += c;
    }
    return cur;
}

Tips

• Build the digits of a count one character at a time: "12" is num = 1, then num = 1*10+2 = 12.
• Nested groups just mean deeper stacks. The innermost "]" is always resolved first, which is what makes the recursion work without recursion.

In the .NET library

string.Concat(Enumerable.Repeat(cur, k)) repeats a string k times; cur.Repeat(k) isn't a real .NET method, but string has no built-in repeat either, so Concat+Repeat (or a StringBuilder loop) is the usual idiom.