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

根据扫描到的字符决定是否放入栈，或者计算重复次数。用栈做dfs

public class Solution {
    /*
     * @param s: an expression includes numbers, letters and brackets
     * @return: a string
     */
    public String expressionExpand(String s) {
        // write your code here
        if (s == null || s.length() == 0) {
            return s;
        }

        Stack<Object> stack = new Stack<Object>();
        char[] sArray = s.toCharArray();
        int number = 0;
        for (Character c : sArray) {
            if (c == '[') {
                stack.push(number);
                number = 0;
            } else if (Character.isDigit(c)) {
                number = number * 10 + c - '0';
            } else if (c == ']') {
                String temp = popStack(stack);
                int curNum = (int) stack.pop();
                String finalS = "";
                for (int i = 0; i < curNum; i++) {
                    finalS += temp;
                }
                stack.push(finalS);
            } else {
                stack.push(String.valueOf(c));
            }
        }
        return popStack(stack);
    }

    public String popStack(Stack<Object> stack) {
        String ans = "";
        while (!stack.isEmpty() && stack.peek() instanceof String) {
            ans = stack.pop() + ans;
        }
        return ans;
    }
}