后綴表達(dá)式/逆波蘭表達(dá)式
運(yùn)算表達(dá)式的種類
-
a + b：中綴表達(dá)式 (Infix Notation)，原因是運(yùn)算符號(hào)在兩個(gè)運(yùn)算對(duì)象的中間。 -
+ - a * b c d：前綴表達(dá)式 (Prefix Notation)，運(yùn)算符在運(yùn)算對(duì)象前面，又稱為波蘭表達(dá)式。 -
a b c * - d +：后綴表達(dá)式 (Prefix Notation)，運(yùn)算符在運(yùn)算對(duì)象后面，又稱為逆波蘭表達(dá)式。
后綴表達(dá)式的優(yōu)點(diǎn)
- 相較于前綴表達(dá)式更易于轉(zhuǎn)換，
最左邊一定為數(shù)字。 - 不用括號(hào)，
依靠運(yùn)算順序確定運(yùn)算符的優(yōu)先級(jí)。 - 更符合計(jì)算機(jī)的計(jì)算方式。計(jì)算機(jī)通過從左至右讀取后綴表達(dá)式，就可以將遇到的運(yùn)算對(duì)象壓入棧，在遇到運(yùn)算符時(shí)就彈出兩個(gè)運(yùn)算對(duì)象，完成計(jì)算，再將結(jié)果壓入棧。最后留在棧中的就是計(jì)算結(jié)果。
中綴表達(dá)式轉(zhuǎn)換為后綴表達(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 (b c) * ) + (d e) + ) - -
把括號(hào)去掉，記得到了后綴表達(dá)式
a b c * + d e + -
可以發(fā)現(xiàn)，后綴表達(dá)式是不需要括號(hào)來調(diào)整運(yùn)算優(yōu)先級(jí)的。
