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