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.

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

考点：stack

思路

1. 用1个stack同时记录字符串和数字（stack<Object>）
2. 循环整个string
   • 用两个变量记录当前的数字和字符串
   • Iterate 每个char; 分情况讨论；
     1). 数字（不止一位）: num = 10 * num + (c - ‘0’)
     2). ‘[‘ ：push 数字进stack；重置num = 0；
     3). ‘]’：
     • 弹出stack中从头到遇到数字之前的所有String，此例中弹出abc。
     • 根据得到的num, 循环将弹出的abc再次入栈，得到abcabcabcabc。
       4). 其他（字母）：push字母入stack
3. 最后将整个stack中的string弹出，得到最终结果
4. 需一个getSubString(Stack stack)函数，用于在碰到”]”时，弹出subString
5. 为保证弹出的string顺序正确，此函数中需要再次使用stack。应为STACK为FILO，从stack1弹出 push stack2 stack2弹出，就保证了顺序。

public class Solution {
    /**
     * @param s  an expression includes numbers, letters and brackets
     * @return a string
     */
    public String expressionExpand(String s) {
        // Write your code here
        String result = null;
        if (s == null || s.length() == 0) {
            return "";
        }
        
        char[] temp = s.toCharArray();
        Stack<Object> stack = new Stack<Object>();
        int number = 0; //calculate the number in the given string
        
        for (char c : temp) {
            if (Character.isDigit(c)) {
                // conver char into integer : - '0'
                //数字不止一位
                number = number * 10 + c - '0'; 
            } else if (c == '[') {
                stack.push(number);
                number = 0; //after push number, numbr must set into 0
            } else if (c == ']') {
                //get(pop) content inside [ ]
                String subStr = this.getSubString(stack);
                //get(pop) the number before [ ]
                int count = (Integer)stack.pop();
                for (int i = 0; i < count; i++) {
                    stack.push(subStr);
                }
            } else {
                stack.push(String.valueOf(c));
            }
        }
        
        return this.getSubString(stack);
    }
    
    public String getSubString(Stack stack) {
        StringBuilder subStr = new StringBuilder();
        Stack<String> subStack = new Stack<String>(); //用于保证substring的顺序。因为STACK是FILO，只弹出一个的话，那么substring就是反的，用2个stack，就是正确的顺序了
        while(!stack.isEmpty() && stack.peek() instanceof String) {
            subStack.push((String)stack.pop());
        }
        
        while (!subStack.isEmpty()) {
            subStr.append(subStack.pop());
        }
        return subStr.toString();
    }
    
}