棧的應(yīng)用 用棧求算術(shù)表達(dá)式的值

線性表3上海金融學(xué)院信息管理系1.3.5棧的應(yīng)用一.用棧求算術(shù)表達(dá)式的值二.用棧解決迷宮問題1.3.5棧的應(yīng)用——用棧求算術(shù)表達(dá)式的值一些概念

算術(shù)表達(dá)式：由操作數(shù)、算術(shù)運(yùn)算符和括號組成的有意義的式子。

二目運(yùn)算符：對于運(yùn)算符，參加運(yùn)算的操作數(shù)必須有兩個(gè)。

中綴表達(dá)式：在算術(shù)表達(dá)式中，二目運(yùn)算符位于參與運(yùn)算的兩個(gè)操作數(shù)中間。如：

a+b*c-d/e*f(a+b)*c-d/(e*f)

a+b*(c-d/(e*f))1.3.5棧的應(yīng)用——用棧求算術(shù)表達(dá)式的值中綴表達(dá)式規(guī)定：（1）括號內(nèi)的運(yùn)算先執(zhí)行。（2）運(yùn)算符優(yōu)先級由高（先執(zhí)行）到低（后執(zhí)行）為：

^//乘方*/+-（3）相同優(yōu)先級的運(yùn)算符，一般從左到右依次執(zhí)行1.3.5棧的應(yīng)用——用棧求算術(shù)表達(dá)式的值

后綴表達(dá)式：把運(yùn)算符放在參與運(yùn)算的操作數(shù)后面的算術(shù)表達(dá)式。如：

abc*+de/f*-請比較a+b*c-d/e*f

ab+c*def*/-請比較

(a+b)*c-d/(e*f)

abcdef*/-*+請比較

a+b*(c-d/(e*f))

一旦遇運(yùn)算符，即將緊靠它前面的兩個(gè)操作數(shù)拿出來進(jìn)行運(yùn)算，結(jié)果作為操作數(shù)置于原來位置。

優(yōu)點(diǎn)：后綴表達(dá)式中操作數(shù)的順序與中綴表達(dá)式中操作數(shù)的順序相同，但它更為簡單，不使用括號，不考慮運(yùn)算符的優(yōu)先級別，操作單純。1.3.5棧的應(yīng)用——用棧求算術(shù)表達(dá)式的值2.解決步驟（1）把中綴表達(dá)式轉(zhuǎn)換成等價(jià)的后綴表達(dá)式（2）根據(jù)后綴表達(dá)式來求值這兩步都需要應(yīng)用棧來解決問題（1）把中綴表達(dá)式轉(zhuǎn)換成等價(jià)的后綴表達(dá)式建一個(gè)存放操作符的棧，棧底元素存放字符“$”。掃描中綴表達(dá)式，若遇到操作數(shù)就將它直接輸出到后綴表達(dá)式中；若遇到操作符，則將其壓到棧中，等待時(shí)機(jī)輸出。若要兩個(gè)表達(dá)式等價(jià)，則后綴表達(dá)式要體現(xiàn)中綴表達(dá)式的運(yùn)算優(yōu)先次序。因此，要在操作符進(jìn)棧和出棧的時(shí)機(jī)，比較運(yùn)算符的優(yōu)先級，并加以處理。（1）把中綴表達(dá)式轉(zhuǎn)換成等價(jià)的后綴表達(dá)式定義運(yùn)算符（含識別符）的優(yōu)先級：字符棧中優(yōu)先級進(jìn)棧前的優(yōu)先級^34*/22+-11(0——$-1——（1）把中綴表達(dá)式轉(zhuǎn)換成等價(jià)的后綴表達(dá)式具體做法：逐個(gè)字符掃描中綴表達(dá)式，按下列情況分別處理：（1）若為變量(操作數(shù))，則立即輸出。（2）若為“（”，則將其壓入棧中。（3）若為運(yùn)算符，則將其優(yōu)先級（進(jìn)棧前）與棧頂字符的優(yōu)先級進(jìn)行比較。如果當(dāng)前的運(yùn)算符的優(yōu)先級小于或等于棧頂字符的優(yōu)先級，則棧頂字符出棧并輸出。此過程持續(xù)到當(dāng)前的運(yùn)算符的優(yōu)先級大于棧頂字符的優(yōu)先級為止。然后將當(dāng)前運(yùn)算符進(jìn)棧。（4）若為“）”，則從棧中依次退出運(yùn)算符并輸出，直到將“（”退出為止?！埃ā辈惠敵觥＃?）若為“\0”，則從棧中依次退出所有運(yùn)算符并輸出，直到將“$”退出為止?！?”不輸出。（1）把中綴表達(dá)式轉(zhuǎn)換成等價(jià)的后綴表達(dá)式算法程序(pp.22-23)int

icp(c)//返回進(jìn)棧前運(yùn)算符c的優(yōu)先級int

isp(c)//返回棧中字符c的優(yōu)先級int

mid_to_pos(mid_e,pos_e)//中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式課堂上講解（2）根據(jù)后綴表達(dá)式來求值建一個(gè)棧用來存放后綴表達(dá)式中的操作數(shù)。

掃描后綴表達(dá)式，若遇到操作數(shù)，則將其壓進(jìn)棧；若遇到運(yùn)算符，則從棧頂連續(xù)取出兩個(gè)操作數(shù)進(jìn)行運(yùn)算，然后將結(jié)果壓進(jìn)棧中。如此繼續(xù)，直到最后一個(gè)運(yùn)算符執(zhí)行完畢，這時(shí)送入棧中的值就是結(jié)果。（2）根據(jù)后綴表達(dá)式來求值為了程序簡單，后綴表達(dá)式的操作數(shù)用一個(gè)小寫英文字母表示。字母所表示的數(shù)值存放在數(shù)組v[26]中，即由數(shù)組元素v[0],v[1],v[2],…,v[25]分別存放變量a,b,c,…,z的值。（2）根據(jù)后綴表達(dá)式來求值pp.18-20int

evaluate(pos_e,p_y)課堂上講解1.3.5棧的應(yīng)用——用棧解決迷宮問題問題：設(shè)有一個(gè)表示為迷宮方案的（m+2)*(n+2)的矩陣maze，其中：元素為０表示該位置可通過，元素為１表示不能通過。矩陣maze的四周的元素都為１。

maze[1][1]為入口，maze[m][n]為出口。試在給定的方案中，找出一條從入口到出口的路徑。（p.24)1.3.5棧的應(yīng)用——用棧解決迷宮問題分析：（1）在迷宮的某個(gè)位置（i,j）上，共有八個(gè)試探方向。從正北方向起，按順時(shí)針的順序編號為0，1，2，…，7。則定義

typedef

struct{inta;

intb;}MOVE;MOVEmv[8];

數(shù)組mv[8]存儲向k（k=0,1,…,7)方向前進(jìn)一步在行和列上變動(dòng)的增量：mv[k].a和mv[k].b。1.3.5棧的應(yīng)用——用棧解決迷宮問題（2）為了避免走回頭路，凡是走過的位置，必須留下標(biāo)志，為此，應(yīng)建立一個(gè)與迷宮maze[][]大小相同的矩陣mark[][]，其元素的初始值為0，表示沒有到達(dá)。一旦到達(dá)某個(gè)maze[i][j]位置時(shí)，則置mark[i][j]為1。以后不允許再次到達(dá)。1.3.5棧的應(yīng)用——用棧解決迷宮問題（3）為了記錄已走過的路徑，使用棧。定義棧s:#defineMAXM30#defineMAXN20

typedef

struct{intx;//到達(dá)位置下標(biāo)1

inty;//到達(dá)位置下標(biāo)2

intd;//方向

}STACK;STACKs[MAXM*MAXN];//存放棧的數(shù)組

inttop;//棧頂下標(biāo)1.3.5棧的應(yīng)用——用棧解決迷宮問題voidsetmove()//