第三章棧與隊(duì)列-全文預(yù)覽
【正文】 sFull() 4 top a b top c top 空棧 top 棧 ? 棧的單鏈表表示 ? 棧的數(shù)組表示可能棧滿 ? 棧的單鏈表表示無棧滿問題 ? 入棧在表頭進(jìn)行插入操作 ? 出棧在表頭進(jìn)行刪除操作 5 top c b a null 棧 ? 進(jìn)棧順序?yàn)?(1,2,3)，出棧順序能否為 (3,1,2)? ? 不能， 3出棧時(shí)，說明 2和 1都在棧里，而且 2必須先于 1出棧 6 3 2 1 top 作業(yè)： 1， 2， 3， 4， 5， 6依次進(jìn)棧，若出棧順序?yàn)?2， 3， 4， 6， 5， 1 則棧大小至少為多少？ 棧的應(yīng)用：表達(dá)式求值 ? 一個(gè)表達(dá)式由操作數(shù) (亦稱運(yùn)算對(duì)象 )、操作符 (亦稱運(yùn)算符 ) 和分界符組成。 8 棧的應(yīng)用：表達(dá)式求值 ? 從左向右掃描表達(dá)式，用一個(gè)棧暫存掃描到的操作數(shù)或計(jì)算結(jié)果。amp。 ?結(jié)束符 “ ” 優(yōu)先級(jí)最低 ?左括號(hào) “ (” 棧外優(yōu)先級(jí)最高 ， 進(jìn)棧后極低 ?右括號(hào) “ )” 棧外優(yōu)先級(jí)極低 ?其他進(jìn)棧后優(yōu)先級(jí)加 1， 這可滿足自左向右計(jì)算要求 19 各個(gè)算術(shù)操作符的優(yōu)先級(jí) 操作符 ( * / % + ) isp(棧內(nèi)優(yōu)先級(jí) ) 0 1 5 3 6 icp(棧外優(yōu)先級(jí) ) 0 6 4 2 1 棧的應(yīng)用：表達(dá)式求值 ? 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式算法 ? 操作符棧初始化，結(jié)束符 進(jìn)棧，讀入中綴表達(dá)式的首字符 ch ? 重復(fù)執(zhí)行以下步驟，直到 ch=，同時(shí)棧頂操作符也是 ，停止循環(huán) ?若 ch是操作數(shù)直接輸出，讀入下一字符 ch ?若 ch是操作符，比較 ch和棧頂操作符 op優(yōu)先級(jí)： ?若 icp(ch) isp(op)，令 ch進(jìn)棧，讀入下一字符 ch ?若 icp(ch) isp(op)，退棧，并輸出 ?若 icp(ch)==isp(op)，退棧不輸出；若退出的是 (，則讀入下一個(gè)字符 ch ? 算法結(jié)束，輸出序列即為所得后綴表達(dá)式 20 棧的應(yīng)用：表達(dá)式求值 21 步 輸入 類型 動(dòng)作 棧內(nèi)容 后綴輸出 0 進(jìn)棧 1 A 操作數(shù) A 2 + 操作符 isp() icp(+), 進(jìn)棧 + A 3 B 操作數(shù) + AB 4 * 操作符 isp(+) icp(*), 進(jìn)棧 + * AB 5 ( 操作符 isp(*) icp( ( ), 進(jìn)棧 + * ( AB 6 C 操作數(shù) + * ( ABC 7 操作符 isp( ( ) icp(), 進(jìn)棧 + * ( ABC 8 D 操作數(shù) + * ( ABCD 9 ) 操作符 isp() icp( ) ), 退棧 + * ( ABCD– isp(( ) == icp( )), 退棧 + * ABCD 中綴表示轉(zhuǎn)換為后綴表示過程： A B C D * + E F / ) ( A C 后綴輸出： + top top 空棧 top * （ top top top B 棧的應(yīng)用：表達(dá)式求值 22 步 輸入 類型 動(dòng)作 棧內(nèi)容 后綴輸出 0 進(jìn)棧 1 A 操作數(shù) A 2 + 操作符 isp() icp(+), 進(jìn)棧 + A 3 B 操作數(shù) + AB 4 * 操作符 isp(+) icp(*), 進(jìn)棧 + * AB 5 ( 操作符 isp(*) icp( ( ), 進(jìn)棧 + * ( AB 6 C 操作數(shù) + * ( ABC 7 操作符 isp( ( ) icp(), 進(jìn)棧 + * ( ABC 8 D 操作數(shù) + * ( ABCD 9 ) 操作符 isp() icp( ) ), 退棧 + * ( ABCD– isp( ( ) == icp( ) ), 退棧 + * ABCD 中綴表示轉(zhuǎn)換為后綴表示過程： A B C D * + E F / ) ( A B C D 后綴輸出： + * （ top top top 棧的應(yīng)用：表達(dá)式求值 23 步 輸入 類型 動(dòng)作 棧內(nèi)容 后綴輸出 10 操作符 isp(*) icp(), 退棧 + ABCD* isp(+) icp(), 退棧 ABCD*+ isp() icp(), 進(jìn)棧 ABCD*+ 11 E 操作數(shù) ABCD*+E 12 / 操作符 isp() icp(/), 進(jìn)棧 / ABCD*+E 13 F 操作數(shù) / ABCD*+EF 14 操作符 isp(/) icp(), 退棧 ABCD*+EF/ isp() icp(), 退棧 ABCD*+EF 結(jié)束 中綴表示轉(zhuǎn)換為后綴表示過程： A B C D * + E F / ) ( + top top * top A B C D * + 后綴輸出： 棧的應(yīng)用：表達(dá)式求值 24 步 輸入 類型 動(dòng)作 棧內(nèi)容 后綴輸出 10 操作符 isp(*) icp(), 退棧 + ABCD* isp(+) icp(), 退棧 ABCD*+ isp() icp(), 進(jìn)棧 ABCD*+ 11 E 操作數(shù) ABCD*+E 12 / 操作符 isp() icp(/), 進(jìn)棧 / ABCD*+E 13 F 操作數(shù) / ABCD*+EF 14 操作符 isp(/) icp(), 退棧 ABCD*+EF/ isp() icp(), 退棧 ABCD*+EF 結(jié)束 中綴表示轉(zhuǎn)換為后綴表示過程： A B C D * + E F / ) ( top top / top A B C D * + E F / 后綴輸出： 作業(yè) ? 程序?qū)崿F(xiàn)簡(jiǎn)單的中綴表達(dá)式求值 ? 數(shù)字均為一位數(shù)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1