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