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
        stack<string> stk;
        string numStr;
        for (char c : s) {
            if (isdigit(c)) {
                numStr += c;
            } else if (c == '[') {
                stk.push(numStr);
                numStr = "";
            } else if (c == ']') {
                string str = popStack(stk);
                string cnt = stk.top(); stk.pop();
                int k = stoi(cnt);
                for (int i = 0; i < k; ++i) {
                    stk.push(str);
                }
            } else {
                stk.push(string(1, c));
            }
        }
        return popStack(stk);
    }

    string popStack(stack<string>& stk) {
        stack<string> buf;
        string res;
        while (!stk.empty() && !isNum(stk.top())) {
            buf.push(stk.top());
            stk.pop();
        }
        while (!buf.empty()) {
            res += buf.top();
            buf.pop();
        }
        return res;
    }

    bool isNum(string s) {
        for (char c : s) {
            if (!isdigit(c)) {
                return false;
            }
        }
        return true;
    }

};