棧與隊(duì)列-文庫(kù)吧
2025-09-07 16:13 本頁(yè)面
【正文】 （ 1） 進(jìn)棧操作 若棧不滿 ， 則在棧頂插入元素 x作為新的棧頂 。 void LinkStack::Push(ElemType x) { SNode *p=new SNode。 if(p!=NULL) { pdata=x。 pnext=top。 top=p。 } } 10/36 （ 2） 出棧操作 若棧不空 ， 則刪除棧頂元素 ， 用 result返回其值 。 void LinkStack::Pop(ElemType amp。result)。 { SNode *p。 if(top!=NULL){ result = topdata。 p=top。 top=topnext。 delete p。 } } 11/36 舉例 : 后綴表達(dá)式求值 假定表達(dá)式是由加減乘除和數(shù)字構(gòu)成。最簡(jiǎn)單的表達(dá)式為下列形式： (操作數(shù) S1)(運(yùn)算符 OP)(操作數(shù) S2) 三種不同的表示方法： 前綴表示法 OPS1S2 例如 6+3寫(xiě)成 +63 中綴表示法 S1OPS2 例如 6+3寫(xiě)成 6+3 后綴表示法 S1S2OP 例如 6+3寫(xiě)成 63+ 12/36 同時(shí)，任何表達(dá)式都可分解為下列形式： (子表達(dá)式 E1)(運(yùn)算符 OP)(子表達(dá)式 E2) 它的后綴表示法應(yīng)寫(xiě)成： (E1的后綴表示 )(E2的后綴表示 )OP 只要不斷對(duì)子表達(dá)式進(jìn)一步分解，總能將子表達(dá)式分解為最簡(jiǎn)單形式，因此任何四則運(yùn)算表達(dá)式都可寫(xiě)成前綴式或后綴式。 例如： 2*(6+3) ? 2(6+3)* ? 263+*。 (注意：轉(zhuǎn)化為后綴式后括號(hào)去掉 ) 13/36 中綴式雖然容易理解，但在求值的時(shí)候利用前綴式或后綴式更為簡(jiǎn)單。 用后綴式求值的算法為： 首先設(shè)立一個(gè)堆棧，依此讀取后綴式中的字符，若字符是數(shù)字，則進(jìn)棧并繼續(xù)讀取，若字符是運(yùn)算符（記為 OP），則連續(xù)出棧兩次得到數(shù)字 S1和 S2，計(jì)算表達(dá)式S1OPS2并將結(jié)果入棧，繼續(xù)讀取后綴式。當(dāng)讀到結(jié)束符時(shí)停止讀操作，這時(shí)堆棧中只應(yīng)該有一個(gè)數(shù)據(jù)，即結(jié)果數(shù)據(jù)。 14/36 例如后綴式 263+*的計(jì)算過(guò)程為 3依次入棧，讀 +號(hào)則令 3和 6依次出棧，計(jì)算6+3后將結(jié)果 9入棧，讀 *號(hào)則令 9和 2依次出棧，計(jì)算 2*9后將結(jié)果 18入棧。這時(shí) 18就是最終結(jié)果。 【 例 23】 假定表達(dá)式是由不超過(guò) 四個(gè)實(shí)數(shù)進(jìn)行四則 運(yùn)算構(gòu)成的算式， 要編寫(xiě)一個(gè)程序來(lái)求解該算式的結(jié)果 。 15/36 中綴表達(dá)式變成等價(jià)的后綴表達(dá)式 將中綴表達(dá)式變成等價(jià)的后綴表達(dá)式 ， 表達(dá)式中操作數(shù)次序不變 ， 運(yùn)算符次序發(fā)生變化 ， 同時(shí)去掉了圓括號(hào) 。 轉(zhuǎn)換規(guī)則是： 設(shè)立一個(gè)棧 ， 存放運(yùn)算符 ， 首先棧為空 ， 編譯程序從左到右掃描中綴表達(dá)式 ， 若遇到操作數(shù) ， 直接輸出 ， 并輸出一個(gè)空格作為兩個(gè)操作數(shù)的分隔符；若遇到運(yùn)算符 ，則必須與棧頂比較 ， 運(yùn)算符級(jí)別比棧頂級(jí)別高則進(jìn)棧 ， 否則退出棧頂元素并輸出 ， 然后輸出一個(gè)空格作分隔符；若遇到左括號(hào) ， 進(jìn)棧；若遇到右括號(hào) ， 則一直退棧輸出 ， 直到退到左括號(hào)止 。 當(dāng)棧變成空時(shí) ， 輸出的結(jié)果即為后綴表達(dá)式 。 16/36 步驟 棧中元素 輸出結(jié)果 說(shuō)明 1 ( （進(jìn)棧 2 ( 1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1