LintCode 575 - Expression Expand

LeetCode 394 - Decode String
https://segmentfault.com/a/1190000008883991
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.
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并不难，这种嵌套式一般是DFS的思想，先走到最里面最小的那个括号，然后逐渐回到上一层→上一层。又∵非递归，“BFS queue， DFS stack”。想到用stack并不难
Stack non-recursion DFS template
要点是，处理完之后重新返回stack，才能够回到上一层操作

这个题具体操作起来真是很多可圈可点的地方，主要是在于String的处理上

1. reverse
   因为stack的顺序，在这个题中需要每次将每层里的内容reverse。直接StringBuilder的reverse方法不可取：因为是reverse每一层。e.g. 3[ab]2[c]层直接从stack取出实际上是cc, ababab将这个reverse后应该得到abababcc。这个时候考虑逆向stack，建立一个stack buffer，将stack pop出来的东西再reverse一个顺序，逆逆得顺
2. instanceof
   nstanceof是一个很好用的操作符，a instanceof A,判断“一个对象是否是一个类的实例”。作为操作符instanceof不可以直接在最前面！取非（比如>=这种也是），而是用 a instanceof A == false之类的判断
3. 复制StringBuilderadd到底append几次，怎么append：直接append add 是不可以的，因为add是在变的，必须要先将第一个add保存起来，类似于dummy node，预先保存queue size这种“锚定”。
4. 坑小心一点0[peer], -3[aaa]这种情况啊！

public String expressionExpand(String s) {
    Stack<Object> stack = new Stack<>();
    char[] arr = s.toCharArray();
    
    int num = 0;
    for(char c : arr){
       if(Character.isDigit(c)){
           num = num * 10 + c - '0';
       }
       else if(c == '['){
           stack.push(Integer.valueOf(num));
           num = 0;
       }
       else if(c == ']'){
           popStack(stack);
       }
       else{
           stack.push(c);
       }
    }
    popStack(stack);
    return stack.pop().toString();
}
private void popStack(Stack<Object> stack){
    StringBuilder add = new StringBuilder();
    int count;
    Stack<Object> buffer = new Stack<Object>();
    while(!stack.isEmpty() && stack.peek() instanceof Integer == false){
        buffer.push(stack.pop());
    }
    while(!buffer.isEmpty()){
        add.append(buffer.pop());
    }
    
    count = stack.isEmpty()? 1 : (Integer) stack.pop();
    StringBuilder part = new StringBuilder(add);
    if(count > 0){
        for(int i = 0; i < count - 1; i++)
            add.append(part);
        stack.push(add);// reput
    }
}