Given an expressionsincludes numbers, letters and brackets. Number represents the number of repetitions inside the brackets(can be a string or another expression)．Please expand expression to be a string.

Have you met this question in a real interview?

Yes

Example

s =abc3[a]returnabcaaa
s =3[abc]returnabcabcabc
s =4[ac]dy, returnacacacacdy
s =3[2[ad]3[pf]]xyz, returnadadpfpfpfadadpfpfpfadadpfpfpfxyz

Challenge

Can you do it without recursion?

class Solution {

public:

/\*\*

 \* @param s  an expression includes numbers, letters and brackets

 \* @return a string

 \*/

string expressionExpand\(string& s\) {

    // Write your code here

    string numStr;

    stack<string> stk;



    for \(char c : s\) {

        if \(isdigit\(c\)\) {

            numStr += c;

        } else if \(c == '\['\) {

            stk.push\(numStr\);

            numStr = "";

        } else if \(c == '\]'\) {

            string cur = popStack\(stk\);

            string cnt = stk.top\(\) ; stk.pop\(\);

            int k = atoi\(cnt.c\_str\(\)\);

            for \(int i = 0; i < k; ++i\) {

                stk.push\(cur\);

            }

        } else {

            stk.push\(string\(1, c\)\);

        }

    }



    return popStack\(stk\);

}



string popStack\(stack<string>& stk\) {

    stack<string> buffer;

    while \(!stk.empty\(\) && !isNum\(stk.top\(\)\)\) {

        buffer.push\(stk.top\(\)\);

        stk.pop\(\);

    }

    string res;

    while \(!buffer.empty\(\)\) {

        res += buffer.top\(\);

        buffer.pop\(\);

    }

    return res;

}



bool isNum\(const string& s\) {

    for \(char c : s\) {

        if \(!isdigit\(c\)\) {

            return false;

        }

    }

    return true;

}

};