Expression expand

給定一個字串，將它展開

例如： 3[a]2[b] => aaabb

這題可以用遞迴或是stack來做，選用stack較好是因為如果有一個超長的字串，

那麼遞迴可能會發生 stack overflow

解題可以這樣想：

我們把數字＋ [ ] 當作一個「子單元」，做完一個子單元把結果推入 stack 中，

看看是不是還要重複做「子單元」。

我們走訪字串，每當遇到 [，將它前面的數字推入 stack，遇到 ] ，

則將在 ] 之前的英文字重複，往回遇到的第一個數字那麼多次，

例如 3[a] => 遇到 [ 把 3 推入，遇到 ] 將 a 重複 3 次，

這樣就完成一個「子單元」

還有一個地方要注意，數字可能是十位數、百位數，

那麼在讀取時則是要用一個變數去累計乘積

public String decodeString(String s) {
    if (s == null) {
        return "";
    }

    Stack<Object> stack = new Stack<>();
    int num = 0;
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            num = num * 10 + c - '0';    //累計乘積
        }
        else if (c == '[') {
            stack.push(Integer.valueOf(num));
            num = 0;
        }
        else if (c == ']') {
            // 遇到 ]
            // 把 stack 裡面的字串累加起來，然後重複 count次，
            // 再放回 stack 完成子單元運算
            // ex: 3[2[a]2[b]2[c]] => eventually there will be 3, aa, bb, cc in the stack
            String newStr = popStack(stack);
            Integer count = (Integer) stack.pop();
            for (int i=0; i<count; i++) {
                stack.push(newStr);
            }
        }
        else {
            stack.push(String.valueOf(c));
        }
    }
    return popStack(stack);
}

// 把遇到數字前的字串累加起來
private String popStack(Stack<Object> stack) {
    Stack<String> buffer = new Stack<>();
    while (!stack.isEmpty() && (stack.peek() instanceof String)) {
        buffer.push((String) stack.pop());
    }
    StringBuilder sb = new StringBuilder();
    while (!buffer.isEmpty()) {
        sb.append(buffer.pop());
    }
    return sb.toString();
}