免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

這里所謂的前綴，中綴，后綴是根據(jù)操作符的位置來定的，如果操作符在操作數(shù)前面，則稱為前綴表達(dá)式，例如“- + 1 × + 2 3 4 5”;如果操作符在操作數(shù)之間，則稱為中綴表達(dá)式，例如

“1+((2+3)×4)-5”;如果操作符在操作數(shù)后面，則稱為后綴表達(dá)式，例如“1 2 3 + 4 × + 5 -”。

雖然中綴表達(dá)式符合人類的日常思維習(xí)慣，但是計(jì)算機(jī)在存儲(chǔ)中綴表達(dá)式時(shí)，需要使用樹這種數(shù)據(jù)結(jié)構(gòu)，如果表達(dá)式過于復(fù)雜，那么樹的高度會(huì)變得很高，大大增加了時(shí)間復(fù)雜度和空間復(fù)雜度。如果轉(zhuǎn)換成線性結(jié)構(gòu)，那么效率將變得高很多，所以需要將中綴表達(dá)式先轉(zhuǎn)換成前綴或者后綴表達(dá)式，然后依靠棧這種線性數(shù)據(jù)結(jié)構(gòu)來進(jìn)行計(jì)算。

前綴表達(dá)式又叫波蘭表達(dá)式，后綴表達(dá)式又叫逆波蘭表達(dá)式。前綴表達(dá)式基本沒有在商業(yè)計(jì)算機(jī)中使用過，所以現(xiàn)實(shí)中用的更多的是后綴表達(dá)式。

如何將中綴表達(dá)式轉(zhuǎn)化成后綴表達(dá)式呢？

利用兩個(gè)棧S1，S2：其中S1存放操作符，S2存放操作數(shù)

從左往右遍歷中綴表達(dá)式，如果遇到數(shù)字，則放入S2中，如果遇到操作符，則放入S1中。在放操作符的時(shí)候有一定的規(guī)則，如果棧為空或棧頂元素為（，則直接壓棧。如果是(，也直接壓棧;如果棧頂元素為普通操作符，則比較優(yōu)先級(jí)，如果待壓棧的操作符比棧頂操作符優(yōu)先級(jí)高，則直接壓棧，否則將S1中的棧頂元素出棧，并壓入S2中，再接著比較S1棧頂元素的優(yōu)先級(jí)。如果遇到)，則依次彈出S1棧頂?shù)倪\(yùn)算符，并壓入S2，直到遇到左括號(hào)為止，此時(shí)將這一對(duì)括號(hào)丟棄。最后將S1中剩余的運(yùn)算符依次彈出并壓入S2，逆序輸出S2（從棧底到棧頂）便得到了后綴表達(dá)式。（注意：等號(hào)的優(yōu)先級(jí)最低，因?yàn)橐阶詈蟛胚M(jìn)行賦值操作）

得到后綴表達(dá)式之后，計(jì)算就變得方便多了，遇到數(shù)字就壓棧，遇到操作符的時(shí)候，pop出棧頂?shù)膬蓚€(gè)元素，進(jìn)行計(jì)算后將結(jié)果又壓入棧中，這樣一直下去，直到得到最終結(jié)果。

將中綴表達(dá)式“1+((2+3)×4)-5”轉(zhuǎn)換為后綴表達(dá)式的過程如下：

因此結(jié)果為“1 2 3 + 4 × + 5 -”（需要逆序輸出）