數(shù)據(jù)結(jié)構(gòu)課件(c語言)(4)-資料下載頁
2024-10-19 19:48本頁面
【正文】 有單目運算符和雙目運算符；從運算類型上分，有算術(shù)運算、關(guān)系運算、邏輯運算。在此僅限于討論只含二目運算符的算術(shù)表達式。 Exp=a b+(cd/e) f Exp=S1 OP S2 稱為 中綴表達式 但是 Exp=S1 S2 OP 后綴表達式 a b c d e / f + 更方便計算機實現(xiàn) [例 3]表達式求值 第 3章 棧和隊列 ． 運算符的優(yōu)先級 為：（） —— ^ —— ＊、 /、 %—— +、 ； ．有括號出現(xiàn)時先算括號內(nèi)的，后算括號外的，多層括號，由內(nèi)向外進行 ； ．乘方連續(xù)出現(xiàn)時先算最右面的； 2^3^2 處理過程是 ：需要兩個棧：對象棧 s1和算符棧 s2。 ①當(dāng)自左至右掃描表達式的每一個字符； ② 若是表達式結(jié)束符，運算結(jié)束； ③當(dāng)前字符是運算對象，入對象棧，返①； ④當(dāng)前字符是運算符時，要與棧頂運算符比較，若高則入棧，返 ① ；否則，從對象棧出棧兩個運算量，然后與從算符棧出棧一個運算符進行運算，并將其運算結(jié)果入對象棧，返①。 (1)中綴表達式求值：對象棧和運算符棧 第 3章 棧和隊列 對象棧 算符棧 2 + 對象棧 算符棧 2 + 1 6 * 對象棧 算符棧 2 + 6 對象棧 算符棧 8 對象棧 算符棧 2 + ( 對象棧 算符棧 2 + ( 4 3 對象棧 算符棧 2 + 1 ( 對象棧 算符棧 2 + 1 左括號在棧外優(yōu)先級最高 右括號遇到左括號，左括號直接出棧在棧外優(yōu)先級最高 左括號在棧內(nèi)優(yōu)先級比 低 例 計算 2+(43)*6 第 3章 棧和隊列 算法描述： 讀入表達式一個字符 。 while(未遇到結(jié)束符 ) {if(當(dāng)前字符是運算對象 ) {將該字符入對象棧 。掃描下一個字符 。} else//當(dāng)前字符是運算符 switch(當(dāng)前運算符 ) {case 左括號 :{進棧 。掃描下一個字符 。 break。} case 右括號 ,將算符棧頂至左括號之間的運算符依次出棧， 每個運算符并與對象棧出棧的兩個運算對象進行運算， 結(jié) 果入對象棧； } default: if(當(dāng)前字符優(yōu)先級 =運算棧頂?shù)膬?yōu)先級 ) { 從運算棧彈出一個運算符 。 從對象棧彈出兩個對象 。 計算 ,將結(jié)果入對象棧 。 } else {將當(dāng)前運算符入運算符棧 。掃描下一個字符 。} }//switch結(jié)束 } //while結(jié)束 輸出對象棧中棧頂?shù)闹?。 第 3章 棧和隊列 算法描述： 讀入表達式一個字符 。 while(未遇到結(jié)束符 ) {if(是運算對象 ) 壓入棧 。 else//若是運算符 {從棧中彈出 2個數(shù)，將運算結(jié)果再壓入棧 。 讀入下一個字符 。 } 輸出棧頂值 。 2 2 4 2 4 3 例 計算 2+(43)*6 后綴表達式： 2 4 3 – 6 * + 2 1 (2)后綴表達式求值步驟： 只需對象棧 (3)中綴表達式轉(zhuǎn)換成后綴表達式：只需運算符棧 2 1 6 2 6 8 第 3章 棧和隊列 [例 4]棧與遞歸 r 主程序 s r r r s 子程序1 r s t 子程序2 r s t 子程序3 (1) 過程的嵌套 第 3章 棧和隊列 作業(yè) ? ， 利用棧判斷一個字符串是否為回文。 ? ， 利用棧將一個單鏈表逆置。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1