TopCoder

$\huge 南ことり$
$ε=ε=ε=(~ ̄▽ ̄)~烙跑囉$

User's AC Ratio

84.6% (11/13)

Submission's AC Ratio

55.0% (44/80)

Tags

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 1

dcYbaXZ

Sample Output 1

abcdXYZ

Hints

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

Problem Source

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

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 131072 262144 1
1 1000 131072 262144 2
2 1000 131072 262144 3
3 1000 131072 262144 4
4 1000 131072 262144 5
5 1000 131072 262144 6
6 1000 131072 262144 7
7 1000 131072 262144 8
8 1000 131072 262144 9
9 1000 131072 262144 10