Reverse Polish Notation
|
Time Limit: Nolimit
|
|
Memory Limit: 65536K
|
Description
標(biāo)準(zhǔn)的表達式如"A+B"，在數(shù)學(xué)上學(xué)名叫中綴表達式（Infix Notation），原因是運算符號在兩個運算對象的中間。相對應(yīng)的還有前綴表達式（Prefix Notation）,如："+ - A * B C D"，轉(zhuǎn)換成中綴表達式為："A - B * C + D"；后綴表達式（Postfix Notation），比如前所述的中綴表達式轉(zhuǎn)換為后綴表達式為："A B C * - D +"。為了紀(jì)念波蘭數(shù)學(xué)家魯卡謝維奇（Jan Lukasiewicz），前綴表達式被稱作波蘭表達式，后綴表達式稱為逆波蘭表達式（Reverse Polish Notation）。后綴表達式的優(yōu)點是顯而易見的，編譯器在處理時候按照從左至右的順序讀取逆波蘭表達式，遇到運算對象直接壓入堆棧，遇到運算符就從堆棧提取后進的兩個對象進行計算，這個過程正好符合了計算機計算的原理。后綴表達式比前綴表達式更加易于轉(zhuǎn)換，并且它的最左面一定為數(shù)字，這一點在實際編程的時候就會體會到它的好處了。逆波蘭表達式有一個更大的優(yōu)點，就是拆括號，根據(jù)運算符的級別將中綴表達式轉(zhuǎn)換成逆波蘭表達式后，運算順序就已經(jīng)替代了運算符的級別，這樣也避免了括號提高運算級別的特殊處理。事實上，人的思維方式很容易固定~~！正如習(xí)慣拉10進制。就對2，3，4，8，16等進制不知所措一樣~~！人們習(xí)慣的運算方式是中綴表達式。而碰到前綴，后綴方式。。迷茫其實僅僅是一種表達式子的方式而已（不被你習(xí)慣的方式）我這里教你一種也許你老師都沒跟你講的簡單轉(zhuǎn)換方式一個中綴式到其他式子的轉(zhuǎn)換方法~~這里我給出一個中綴表達式~a+b*c-(d+e)
第一步：按照運算符的優(yōu)先級對所有的運算單位加括號~
式子變成拉：((a+(b*c))-(d+e))
第二步：轉(zhuǎn)換中綴與后綴表達式 后綴：把運算符號移動到對應(yīng)的括號后面 則變成拉：((a(bc)*)+(de)+)-
把括號去掉：abc*+de+- 后綴式子出現(xiàn)發(fā)現(xiàn)沒有，前綴式，后綴式是不需要用括號來進行優(yōu)先級的確定的。現(xiàn)在，你需要用計算機來實現(xiàn)這一過程，怎么樣，是否有興趣一試呢？如果答案是肯定的話，Let‘s go！
Input
按照人們?nèi)粘５妮斎肓?xí)慣，請輸入一個帶浮點型帶括號的中綴表達式（不需要添加等號）。
輸入的算式可以包含整數(shù)，小數(shù)，+,-,*,/,(,)這幾種類型，
當(dāng)然，為了體現(xiàn)和諧社會的客觀要求及人文關(guān)懷，你可以假設(shè)這個算式的總字符長度小于100字節(jié)。
Output
輸出與此中綴表達式對應(yīng)的逆波蘭表達式，為了區(qū)分數(shù)字，請將數(shù)字與數(shù)字或字符與字符以空格隔開。
最后一個字符后不需要添加空格，各組測試數(shù)據(jù)之間請用空行隔開。(輸出到文件尾)
Sample Input
1.5+2.5*3-（4+5）
1*（2+3）/4
Sample Output
1.5 2.5 3 * + 4 5 + -
1 2 3 + * 4 /
Source
Weitao(偉濤) 's first submitting problem for njust ACM team;