中序式轉(zhuǎn)后序式

說(shuō)明平常所使用的運(yùn)算式，主要是將運(yùn)算元放在運(yùn)算子的兩旁，例如a+b/d這樣的式子，這稱(chēng) 之為中序（Infix）表示式，對(duì)于人類(lèi)來(lái)說(shuō)，這樣的式子很容易理 解，但由于電腦執(zhí)行指令時(shí)是 有順序的，遇到中序表示式時(shí)，無(wú)法直接進(jìn)行運(yùn)算，而必須進(jìn)一步判斷運(yùn)算的先后順序，所以 必須將中序表示式轉(zhuǎn)換為另一種表示方 法。

可以將中序表示式轉(zhuǎn)換為后序（Postfix）表示式，后序表示式又稱(chēng)之為逆向波蘭表示式（Reverse polishnotation），它是由波蘭的數(shù)學(xué)家盧卡謝維奇提出，例如(a+b)*(c+d)這個(gè)式子，表示為后序 表示式時(shí)是ab+cd+*。

解析

用手算的方式來(lái)計(jì)算后序式相當(dāng)?shù)暮?jiǎn)單，將運(yùn)算子兩旁的運(yùn)算元依先后順序全括號(hào)起來(lái)，然后將所有的右括號(hào)取代為左邊最接近的運(yùn)算子（從最內(nèi)層括號(hào)開(kāi)始），最后去掉所有的左括號(hào) 就可以完成后序表示式，例如： a+b*d+c/d => ((a+(b*d))+(c/d)) -> abd*+cd/+，如果要用程式來(lái)進(jìn)行中序轉(zhuǎn)后序，則必須使用堆疊，演算法很簡(jiǎn)單，直接敘述的話就是使用回 圈，取出中序式的字元，遇運(yùn)算元直接輸出，堆疊運(yùn)算子與左括號(hào)， ISP>ICP的話直接輸出堆 疊中的運(yùn)算子，遇右括號(hào)輸出堆疊中的運(yùn)算子至左括號(hào)。

如果要將中序式轉(zhuǎn)為前序式，則在讀取中序式時(shí)是由后往前讀取，而左右括號(hào)的處理方式相反， 其余不變，但輸出之前必須先置入堆疊，待轉(zhuǎn)換完成后再將堆疊中的 值由上往下讀出，如此就 是前序表示式。

代碼實(shí)現(xiàn)

測(cè)試代碼