(3.2.1)-3.2棧的應(yīng)用數(shù)據(jù)結(jié)構(gòu)與算法

棧的應(yīng)用12中綴表達(dá)式轉(zhuǎn)換后綴表達(dá)式思想中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式實(shí)例小結(jié)教學(xué)內(nèi)容

中綴表達(dá)式中綴表達(dá)式就是平常書寫采用的表達(dá)式形式，對于雙目運(yùn)算符來說，加號、乘號位于兩個(gè)操作數(shù)之間，故稱為中綴表達(dá)式。先計(jì)算優(yōu)先級高的部分，再計(jì)算優(yōu)先級低的部分。如：2+3*5

后綴表達(dá)式后綴表達(dá)式，又稱逆波蘭式，指的是不包含括號，運(yùn)算符放在兩個(gè)運(yùn)算對象的后面，所有的計(jì)算按運(yùn)算符出現(xiàn)的順序，嚴(yán)格從左向右進(jìn)行（不再考慮運(yùn)算符的優(yōu)先規(guī)則）。如：235*+

中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式算法思想將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法思想：開始掃描：當(dāng)前為數(shù)字時(shí)，加入后綴表達(dá)式；當(dāng)前為運(yùn)算符：a.若為'('，入棧；b.

若為‘)’，則依次把棧中的運(yùn)算符出棧并加入后綴表達(dá)式中，直到出現(xiàn)'('，從棧中刪除'('；中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式思想

c.若為除括號外的其他運(yùn)算符，當(dāng)其優(yōu)先級高于除‘(’以外的棧頂運(yùn)算符時(shí)，直接入棧。否則從棧頂開始，依次彈出比當(dāng)前處理的運(yùn)算符優(yōu)先級高和優(yōu)先級相等的運(yùn)算符到后綴表達(dá)式中，直到一個(gè)比它優(yōu)先級低的或者遇到了一個(gè)左括號為止，然后將其自身壓入棧中（先出后入）。當(dāng)掃描的中綴表達(dá)式結(jié)束時(shí)，棧中的所有運(yùn)算符出棧；中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式實(shí)例

將中綴表達(dá)式5*（2+6*3）轉(zhuǎn)為后綴表達(dá)式（1）首先，如果遇到操作數(shù)5，我們就直接將其輸出5。接著是符號”*”,入棧：例1此時(shí)輸出的后綴表達(dá)式：5中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式實(shí)例（2）第三個(gè)字符是”（“，入棧，接著是數(shù)字2，輸出，然后是符號”+“，入棧：此時(shí)輸出的后綴表達(dá)式：52

將中綴表達(dá)式5*（2+6*3）轉(zhuǎn)為后綴表達(dá)式中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式實(shí)例

（3）接著是數(shù)字6，輸出，之后是符號”*”，因?yàn)闂ｍ斣?+"優(yōu)先級比"*"低，所以將"*"直接入棧：此時(shí)輸出的后綴表達(dá)式：526

將中綴表達(dá)式5*（2+6*3）轉(zhuǎn)為后綴表達(dá)式中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式實(shí)例

（4）接下來是數(shù)字3，輸出，緊跟著是“）”，此時(shí)，我們需要去匹配棧里的“（”，在匹配前將棧頂運(yùn)算符依次出棧（這里就相當(dāng)于括號里的優(yōu)先執(zhí)行的道理），最后棧中只剩操作符“*”（此時(shí)掃描已結(jié)束），直接彈出并輸出：此時(shí)輸出的后最表達(dá)式：5263*+*

將中綴表達(dá)式5*（2+6*3）轉(zhuǎn)為后綴表達(dá)式中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式實(shí)例

最后得到的后綴表達(dá)式：5263*+*

將中綴表達(dá)式5*（2+6*3）轉(zhuǎn)為后綴表達(dá)式中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式實(shí)例

例2

將中綴表達(dá)式5*（2+6-3）轉(zhuǎn)為后綴表達(dá)式（1）首先，如果遇到操作數(shù)5，我們就直接將其輸出5。接著是符號”*”,入棧：此時(shí)輸出的后綴表達(dá)式：5中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式實(shí)例（2）第三個(gè)字符是”（“，入棧，接著是數(shù)字2，輸出，然后是符號”+“，入棧：此時(shí)輸出的后綴表達(dá)式：52

將中綴表達(dá)式5*（2+6-3）轉(zhuǎn)為后綴表達(dá)式中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式實(shí)例

（3）接著是數(shù)字6，輸出，之后是符號”-”，因?yàn)闂ｍ斣亍?”優(yōu)先級與“-”相等，所以將“+”出棧并輸出，之后棧頂為“（”，將“—”入棧：此時(shí)輸出的后綴表達(dá)式：526+

將中綴表達(dá)式5*（2+6-3）轉(zhuǎn)為后綴表達(dá)式中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式實(shí)例

（4）接下來是數(shù)字3，輸出，緊跟著是“）”，此時(shí)，我們需要去匹配棧里的“（”，然后再匹配前將棧頂符號依次出棧（這里就相當(dāng)于括號里的優(yōu)先執(zhí)行的道理），也就是將“—”輸出。此時(shí)掃描結(jié)束，棧中只剩下“*”，將其輸出即可。此時(shí)輸出的后綴表達(dá)式：526+3—*

將中綴表達(dá)式5*（2+6-3）轉(zhuǎn)為后綴表達(dá)式中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式實(shí)例

最后得到的后綴表達(dá)式：526+3—*

將中綴表達(dá)式5*（2+6-3）轉(zhuǎn)為后綴表達(dá)式運(yùn)算符優(yōu)先級的表示

相鄰運(yùn)算符a、b優(yōu)先關(guān)系，a在左、b在右＋－×／()#＋>><<<>>－>><<<>>×>>>><>>／>>>><>>(<<<<<=)>>>>>>#<<<<<=charpre[7][7]={{'>','>','<','<','<','>','>'},

{'>','>','<','<','<','>','>'},

{'>','>','>','>','<','>','>'},

{'>','>','>','>','<','>','>'},

{'<','<','<','<','<','=',''},

{'>','>','>','>','','>','>'},

{'<','<','<','<','<','','='}

};小結(jié)

轉(zhuǎn)換過程需要用到棧，具體過程如下：1）如果遇到操作數(shù)，我們就直接將其輸出。2）如果遇到左括號“（”時(shí)，將其放入棧中。3）如果遇到一個(gè)右括號“）”，則將棧元素彈出，將彈出的操作符輸出直到遇到左括號“（”為止。注意，左括號只彈出并不輸出，實(shí)際就是消括號。小結(jié)

4）如果遇到任何其他的操作符，如【“+”，“*”，“（”】等，當(dāng)其優(yōu)先級高于棧頂運(yùn)算符時(shí)，直接入棧；否則從棧頂開始，依次從棧中彈出元素直到遇到更低優(yōu)先級的元素(或者棧為空)為止；彈出完這些元素后