棧的應(yīng)用舉例-資料下載頁(yè)
2025-08-05 08:28本頁(yè)面
【正文】 7 || 各個(gè)算術(shù)操作符的優(yōu)先級(jí) ? isp叫做棧內(nèi) (in stack priority)優(yōu)先數(shù) ? icp叫做棧外 (in ing priority)優(yōu)先數(shù) 。 ? 操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在 括號(hào)配對(duì) 或棧底的 “ ?！碧?hào)與輸入流最后的 “ ?！碧?hào)配對(duì) 時(shí) 。 操作符 ch 。 ( *, /, % +, ) isp ( 棧內(nèi) ) 0 1 5 3 6 icp ( 棧外 ) 0 6 4 2 1 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法 ? 操作符棧初始化 ， 將結(jié)束符 ‘ ’進(jìn)棧 。 然后讀入中綴表達(dá)式字符流的首字符 ch。 ? 重復(fù)執(zhí)行以下步驟 ， 直到 ch = ‘’， 同時(shí)棧頂?shù)牟僮鞣彩?‘ ’， 停止循環(huán) 。 ? 若 ch是操作數(shù)直接輸出 ， 讀入下一個(gè)字符 ch。 ? 若 ch是操作符 ， 判斷 ch的優(yōu)先級(jí) icp和 位于棧頂 的 操作符 op的優(yōu)先級(jí) isp： ? 若 icp(ch) isp(op)， 令 ch進(jìn)棧 ， 讀入下一個(gè)字符 ch。 ? 若 icp(ch) isp(op)， 退棧并輸出 。 ? 若 icp(ch) == isp(op)， 退棧但不輸出 ， 若退出的是 “ (”號(hào)讀入下一個(gè)字符 ch。 ? 算法結(jié)束，輸出序列即為所需的后綴表達(dá)式。 a ? ( b ? ( c + d / e ) f ) a ? ( b ? ( c + d / e / / + ? f ? 步 輸入 棧內(nèi)容 語(yǔ)義 輸出 動(dòng)作 1 棧初始化 2 A A 操作數(shù) A 輸出 , 讀字符 3 + + 。 操作符 + 進(jìn)棧 , 讀字符 4 B + B 操作數(shù) B 輸出 , 讀字符 5 * + * + 操作符 * 進(jìn)棧 , 讀字符 6 ( +* ( * 操作符 ( 進(jìn)棧 , 讀字符 7 C + * ( C 操作數(shù) C 輸出 , 讀字符 8 + * ( ( 操作符 進(jìn)棧 , 讀字符 9 D + * ( D 操作數(shù) D 輸出 , 讀字符 10 ) + * ( ) 操作符 退棧輸出 11 + * ( ) = ( ( 退棧 , 消括號(hào) , 讀字符 另一個(gè)例子： A+B*(CD)E/F 步 輸入 棧內(nèi)容 語(yǔ)義 輸出 動(dòng)作 12 + * * * 操作符 * 退棧輸出 13 + + + 操作符 + 退棧輸出 1 4 。 操作 符 進(jìn)棧 , 讀字符 1 5 E E 操作數(shù) E 輸出 , 讀字符 1 6 / / 操作符 / 進(jìn)棧 , 讀字符 1 7 F / F 操作數(shù) F 輸出 , 讀字符 1 8 / / / 操作符 / 退棧輸出 1 9 操作符 退棧輸出 20 = 。 。 配對(duì) , 轉(zhuǎn)換結(jié)束 另一個(gè)例子： A+B*(CD)E/F 表達(dá)式計(jì)算的算法 ? 中綴轉(zhuǎn)后綴算法見(jiàn)課本 120 ? 后綴表達(dá)式計(jì)算的算法見(jiàn)課本 118
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1