Problem

Given an expression s includes 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] return abcaaa
s = 3[abc] return abcabcabc
s = 4[ac]dy, return acacacacdy
s = 3[2[ad]3[pf]]xyz, return adadpfpfpfadadpfpfpfadadpfpfpfxyz

思路

1. because it has embedded expression , we need to expand from inner to outer.
2. when we go through the array, we need to save the outer information, expand the inner expression then form the expression with outer one.
3. so we need to implement it with Recursion or stack.

here is the stack solution. the recursion solution is on Depth first search chapter

steps:

1. go through the string,

   1. push number when there is a '['
   2. push digit
   3. pop when ']' to form a string using the char and number

2. 

3.  public String expressionExpand(String s) {
        Stack<Object> stack = new Stack<>();
        int number = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isLetter(c)) {
                stack.push(String.valueOf(c));
            } else if (Character.isDigit(c)) {
                number = number * 10 + c - '0';
            } else if (c == '[') {
                stack.push(number);
                number = 0;
            } else if (c == ']') {
                StringBuilder sb = new StringBuilder();
                while (!stack.isEmpty()) {
                    Object obj = stack.pop();
                    if (obj instanceof String) {
                        sb.insert(0, (String)obj);
                    } else {
                        String temp = sb.toString();
                        sb.setLength(0);
                        for (int j = 0; j < (Integer)obj; j++) {
                            sb.append(temp);
                        }
                        break;
                    }
                }
                stack.push(sb.toString());
            }
        }
   
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.insert(0, (String)stack.pop());
        }
        return sb.toString();
    }