在農場裡,奶牛們習慣將中序的數學式用後序表達,舉例來說,(x+y)×(z+w)可以被表達成xy+zw+×。
為了確保式子的計算結果是正確的,農場有台奶牛計算機。這台計算機相當大,裡頭有好幾頭計算奶牛,
這些奶牛扮演著變數的身分,照著一個規則進到計算機裡的牛棚。
這個牛棚相當長,只有單個出口,且其寬度只能讓一頭牛剛好容納在其中。於是先進去的
奶牛得最後才能出來,簡單來說,它是個以奶牛為元素的超大堆疊。
當然,裡頭的奶牛是採輪班制,農場內的每頭牛都會輪到,因此不會有任何奶牛抱怨。而
這個計算機計算式子結果的規則如下。這個規則有兩個操作:
然後順著算式從左到右,遇到變數就請代表該變數的奶牛 push。
如果遇到運算符號 X,則做像這樣的操作。
b ← pop();
a ← pop();
push( a × b );
最後牛棚裡只會剩下一隻奶牛,請留在牛棚裡的奶牛宣讀自己所代表的數字即是答案。
然而,農夫約翰不小心在牛棚的另一端弄破了一個洞,於是在牛棚內的奶牛想從這裡出來,
因為他們不想在狹小的空間內轉身。也就是先進去的奶牛會先出來,這個牛棚變成了一個佇列。
這下子操作變成了下面這樣:
1. push:請一隻奶牛從入口走進牛棚。
2. pop :請最靠近出口的奶牛出來。
農夫約翰為此相當頭痛,因為這台計算機算出來的答案都是錯的,使得農場裡的秩序整個
變了調,為此,農夫約翰請了資優生貝西來暫時擔任計算機來解決這個問題。
只是,農場內的奶牛們並不相信貝西的心算結果,即使她拿出了在 USACO大學多次免修
的證明也一樣。無奈的貝西只好偷偷修改運算式的順序,使得新的運算式透過新的計算機規則
可以算出正確的結果。
但一天到晚動腦筋也是挺累的,於是她想請你幫忙寫個程式算出她要運算式改成什麼模樣,
如此一來她就可以不用動腦筋了。
需要注意的是,奶牛們在做的運算不僅沒有交換律,更沒有結合律。因此改動後的運算式
仍是唯一的,不可以任意改變運算答案的順序。
運算式的長度不會超過 500,000 個字元。
輸入只有一行,代表奶牛的運算式。運算式中只會出現大、小寫英文字母及阿拉伯數字,小寫
字母、阿拉伯數字代表變數,大寫字母代表運算符號。運算式一定合法。
輸出一行,代表改動後的運算式。
輸入的算式用中序來寫就是(d Y c) Z (b X a)。
原TIOJ1707 / 建國中學99年校內培訓contest #7 prob 1
problem setter:suhorng
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 |