TopCoder

Thumb output jddoia
$\huge 南ことり$
今天也要輸贏!?

User's AC Ratio

91.7% (11/12)

Submission's AC Ratio

54.4% (43/79)

Description

  在農場裡,奶牛們習慣將中序的數學式用後序表達,舉例來說,(x+y)×(z+w)可以被表達成xy+zw+×。
為了確保式子的計算結果是正確的,農場有台奶牛計算機。這台計算機相當大,裡頭有好幾頭計算奶牛,
這些奶牛扮演著變數的身分,照著一個規則進到計算機裡的牛棚。

  這個牛棚相當長,只有單個出口,且其寬度只能讓一頭牛剛好容納在其中。於是先進去的
奶牛得最後才能出來,簡單來說,它是個以奶牛為元素的超大堆疊。

  當然,裡頭的奶牛是採輪班制,農場內的每頭牛都會輪到,因此不會有任何奶牛抱怨。而
這個計算機計算式子結果的規則如下。這個規則有兩個操作:

  1. push:請一隻奶牛走進牛棚。
  2. pop :請最靠近出入口的奶牛出來。

  然後順著算式從左到右,遇到變數就請代表該變數的奶牛 push。
如果遇到運算符號 X,則做像這樣的操作。

            b ← pop();
            a ← pop();
            push( a × b );

  最後牛棚裡只會剩下一隻奶牛,請留在牛棚裡的奶牛宣讀自己所代表的數字即是答案。

  然而,農夫約翰不小心在牛棚的另一端弄破了一個洞,於是在牛棚內的奶牛想從這裡出來,
因為他們不想在狹小的空間內轉身。也就是先進去的奶牛會先出來,這個牛棚變成了一個佇列。
這下子操作變成了下面這樣:

            1. push:請一隻奶牛從入口走進牛棚。
            2. pop :請最靠近出口的奶牛出來。

  農夫約翰為此相當頭痛,因為這台計算機算出來的答案都是錯的,使得農場裡的秩序整個
變了調,為此,農夫約翰請了資優生貝西來暫時擔任計算機來解決這個問題。

  只是,農場內的奶牛們並不相信貝西的心算結果,即使她拿出了在 USACO大學多次免修
的證明也一樣。無奈的貝西只好偷偷修改運算式的順序,使得新的運算式透過新的計算機規則
可以算出正確的結果。

  但一天到晚動腦筋也是挺累的,於是她想請你幫忙寫個程式算出她要運算式改成什麼模樣,
如此一來她就可以不用動腦筋了。

  需要注意的是,奶牛們在做的運算不僅沒有交換律,更沒有結合律。因此改動後的運算式
仍是唯一的,不可以任意改變運算答案的順序。

Input Format

運算式的長度不會超過 500,000 個字元。

輸入只有一行,代表奶牛的運算式。運算式中只會出現大、小寫英文字母及阿拉伯數字,小寫
字母、阿拉伯數字代表變數,大寫字母代表運算符號。運算式一定合法。

Output Format

輸出一行,代表改動後的運算式。

Sample Input

dcYbaXZ

Sample Output

abcdXYZ

Hints

輸入的算式用中序來寫就是(d Y c) Z (b X a)。

Problem Source

原TIOJ1707 / 建國中學99年校內培訓contest #7 prob 1
problem setter:suhorng

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144