題目連結：
題目大意：
給定一正整數 n （1 ≦ n ≦ 18），代表現在有一個整數數列，內容為 1 、 2 、 3 、 …… 、 n。
現在給你一個堆疊（Stack，題目標題的「棧」是對岸 Stack 之譯名）之結構，其有兩種操作：
一：將上面給定的整數數列的前端之數字移到堆疊的頂端，稱為一次 push。
二：將堆疊頂端的數字移到輸出之序列的尾端，稱為一次 pop。
現在，整數數列要經過若干次的堆疊之操作（但不能有堆疊為空的時候 pop、原數列為空時 push 之非法操作），將數字全數從原數列移到輸出序列之中。
試問，給定的整數序列搭配若干個堆疊操作可以產生多少種輸出數列。
範例輸入：
3
範例輸出：
5
解題思維：
如果有稍微試著做一下（可能需要使用電腦幫助）前幾個可能的 n 值 （1 ～ 8 等等）。可以發現所求為 1 、 2 、 5 、 14 、 42 、 132 、 429 、 1430 、 …… 種可能的結果。
而上述的數列恰好為卡塔蘭數列的前 8 項（如果第 0 項不算的話）。因此我們猜測本命題等價於其他可以形成卡塔蘭數之命題。而事實上確實是等價的。
如果我們將 push 看作左括號「(」、pop 看作右括號「)」，則每個可能的、長度為 n 的輸出序列即代表一個長度為 2n 的合法括號之匹配。
例如輸出序列為 2 、 1 、 3 ，則產生該序列的操作依序為 push 、 push 、 pop 、 pop 、push 、 pop。轉成括號表示為 (())() ，恰為一組合法的括號。
為什麼呢？因為可以看到一組合法括號，其由左掃到右時，任意時刻皆滿足左括號之數量 ≧ 右括號之數量。並且整體之左括號數量 ＝ 右括號數量。而此項性質剛好對應到堆疊的操作合法性——堆疊為空時，不能 pop、原數列為空不能 push。
所以只要求出第 n 項的卡塔蘭數即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
