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