C / C++ / MFC

Consider the pattern n[string], which is equivalent to the succession (string) ... (string) ((string) repeated n times). Starting with this model, any string can be compressed.

For example:

• 1[a] is equivalent to a
• 2[ab] is equivalent to abab
• 2[a2[b]] is equivalent to abbabb
• 3[b2[ca]] is equivalent to bcacabcacabcaca

Requirement

Given a compressed string of characters, display its decompression.

Input data

The program reads from the keyboard a correctly compressed string S of characters.

Output data

The program will display a string of characters that will represent the decompression of the string S.

Restrictions and clarifications

• 3 ≤ the length of the string S ≤ 1000
• decompressed string length ≤ 100,000
• the string S will contain only lowercase letters of the English alphabet
• Time limit: 0.6 seconds
• Memory limit: 64 MB (global) / 8 MB(local)

Example

Input 1

3[a1[b2[c]]]

Output 1

abccabccabcc

Input 2

3[a2[c]]2[x3[y]]

Output 2

accaccaccxyyyxyyy

include <iostream>
include <string>
include <cctype>

string input;

int createNumber(int &pos) {
    int number = 0;
    while (isdigit(input[pos]))
        number = number * 10 + input[pos] - '0', input.erase(input.begin() + pos);
    return number;
}
string insideParanthesis(int &pos) {
    if (input.length()) {
        input.erase(input.begin() + pos);
        string toRepeat = "";
        while (input[pos] != ']') {
            while (isalpha(input[pos]) && pos < input.length())
                pos++, toRepeat += input[pos - 1];

            if (isdigit(input[pos])) {
                int timesExpr = createNumber(pos);
                int posStart = pos;
                timesExpr--;
                string expr = insideParanthesis(pos);
                if (timesExpr < 0) {
                    input.erase(input.begin() + posStart, input.begin() + pos);
                    continue;
                }
                while (timesExpr--)
                    input.insert(pos, expr), toRepeat += expr, pos += expr.length();
                toRepeat += expr;
            }
        }
        input.erase(input.begin() + pos);
        return toRepeat;
    }
    return "";
}

int main() {
    ios_base::sync_with_stdio(false);

    getline(cin, input);

    for (int i = 0; i < input.length(); i++) {
        if (isdigit(input[i])) {
            int timesExpr = createNumber(i);
            int iStart = i;
            timesExpr--;
            string expr = insideParanthesis(i);
            if (timesExpr < 0 && input.length()) {
                input.erase(input.begin() + iStart, input.begin() + i);
                continue;
            }
            else if (!(input.length()))
                return 0;
            while (timesExpr--)
                input.insert(i, expr);
        }
    }

    for (int i = 0; i < input.length(); i++) {
        if (input[i] == '[' || input[i] == ']')
            continue;
        else
            cout << input[i];
    }
}