主題
題目連結：
題目大意：
現有一程式語言名為 A++ ，現給定其迴圈的架構。給定一正整數 t （ t ≦ 10 ），代表接下來有 t 筆測試資料。
每筆測試資料的第一列給定一正整數 L 以及一字串，前者代表接下來有 L 列的程式碼（ L ≦ 100 ）、後者代表預測的時間複雜度，字串形式為「O(1)」或「O(n^w)」（ w ≦ 100 ，且為正整數；而 n 是一個變數，代表複雜度的數量級之底數，保證遠大於 100 ）。
接下來的 L 列輸入，每列代表一列的程式碼。
若程式碼以「F」開頭，接著會給定 i 、 x 、 y ， i 是一個小寫的英文字母（保證不為「n」）、x 跟 y 各自可為正整數或是「n」。其代表一個迴圈的開頭， i 代表宣告的新變數作為此迴圈的索引值、x 為 i 的初始值、y 是迴圈的上界，當 i ＞ y 時便跳出迴圈。而每到迴圈的結尾並回來之後， i 之值會加一。
若程式碼為「E」開頭，則代表先前輸入之中最近的迴圈之結尾。
迴圈可為巢狀架構。例：
F a 1 n
F b 2 n
E
E
試問：給定的程式碼之時間複雜度與預測的時間複雜度是否相同？
若相同，輸出「Yes」；反之，輸出「No」。但倘若程式碼之中迴圈匹配不正確（「F」、「E」的數量搭不起來），或是變數被重複地宣告（當迴圈結束，該迴圈宣告的變數會被釋放，此時可以再次宣告），則應該輸出「ERR」代表程式碼之架構有誤。
範例輸入：
8
2 O(1)
F i 1 1
E
2 O(n^1)
F x 1 n
E
1 O(1)
F x 1 n
4 O(n^2)
F x 5 n
F y 10 n
E
E
4 O(n^2)
F x 9 n
E
F y 2 n
E
4 O(n^1)
F x 9 n
F y n 4
E
E
4 O(1)
F y n 4
F x 9 n
E
E
4 O(n^2)
F x 1 n
F x 1 10
E
E
範例輸出：
Yes
Yes
ERR
Yes
No
Yes
Yes
ERR
解題思維：
主要的想法就是每遇到一個「F」就把 i 、 x 、 y 的資訊丟進一個堆疊（stack，特性是先進後出）裡；反之，遇到「E」就丟掉堆疊頂端的元素。
每有一層新迴圈時，先判斷會不會進去該迴圈裡，也就是 x 有無小於等於 y。因為 x 、 y 各自可以為正整數或是變數「n」。因此會有以下五種情況：
兩者皆為正整數且 x ＜ y ：會進入此迴圈，但不影響時間複雜度。
兩者皆為正整數且 x ＞ y ：不會進入此迴圈，而且裡面包含的東西也跟著不會進去。
x 為正整數且 y 為「n」：進入此迴圈，且當前的時間複雜度層級上升一個等級。
x 為「n」且 y 為正整數：不會進入此迴圈，而且裡面包含的迴圈們也跟著不會執行。
兩者皆為「n」：進入此迴圈，但不影響時間複雜度。
以上的情況當中可以忽略的就是兩者皆為正整數且 x ＜ y 跟兩者皆為「n」，因為不影響時間複雜度（但是還是要放進堆疊裡，不然無法對應到相應的「E」）
而兩者皆為正整數且 x ＞ y 與 x 為「n」且 y 為正整數，則是不會進去該迴圈裡，連同接著的任何巢狀架構也不會進去，因此本體以及內容物皆無法影響時間複雜度。所以需要一個變數表示現在是否在不會執行的迴圈架構裡。
最後是 x 為正整數且 y 為「n」，需要一變數儲存當前在的位置之時間複雜度層級為何，此迴圈會使層級上升一個檔次。當遇到相應的「E」表為此迴圈的結尾時，層級會降回去。當中出現過的時間複雜度層級之最大值，即是這整個程式碼的總體時間複雜度。
其中，遇到有變數重複時、最後的堆疊不為空（即「F」的數量 ＞ 「E」）或是丟掉已經「空」的堆疊之頂端（即發生「F」的數量 ＜ 「E」的數量）時，當應該輸出「ERR」（因為以上都是題目所定義之錯誤）。
如果沒有以上情形，就把我們分析程式碼而得的總體時間複雜度（過程中出現過最大的時間複雜度之層級）判斷是否與給定的預測時間複雜度相同。不同，則輸出「No」；反之，輸出「Yes」。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
