為四則運(yùn)算式轉(zhuǎn)后綴表達(dá)式設(shè)計(jì)算法：
如：6+（8-2）*2/3轉(zhuǎn)換后結(jié)果為：6 8 2-2*3/+
①用棧來(lái)存儲(chǔ)運(yùn)算符號(hào)，從左往右掃描四則運(yùn)算式，遇到數(shù)字直接輸出
②若棧為空或當(dāng)前運(yùn)算符號(hào)為“（“時(shí)，入棧
③若棧非空：當(dāng)棧頂為“（“則當(dāng)前運(yùn)算符入棧；否則比較優(yōu)先級(jí)，當(dāng)前運(yùn)算符大于棧頂元素則入棧，否則棧頂元素出棧輸出，直至棧頂元素小于或等于當(dāng)前運(yùn)算符，當(dāng)前運(yùn)算符入棧
④遇到右括號(hào)時(shí)，則棧頂元素依次出棧輸出，直至遇到左括號(hào)，左括號(hào)出棧但不輸出；
（1）四則運(yùn)算式2*6+（3+2）/3轉(zhuǎn)后綴表達(dá)式結(jié)果為：26*32+3/+26*32+3/+。
（2）實(shí)現(xiàn)上述功能的程序如下，請(qǐng)?jiān)跈M線處填入合適的代碼。
【考點(diǎn)】棧的應(yīng)用．
【答案】26*32+3/+
【解答】
【點(diǎn)評(píng)】
聲明：本試題解析著作權(quán)屬菁優(yōu)網(wǎng)所有，未經(jīng)書面同意，不得復(fù)制發(fā)布。
發(fā)布：2024/6/27 10:35:59組卷：14引用：1難度：0.4
相似題
-
1．數(shù)字1，2，3依次進(jìn)棧，則不可能的出棧順序是（ ）
發(fā)布：2024/11/28 22:30:1組卷：8引用：2難度：0.5 -
2．為四則運(yùn)算式“6+（8-2）*2÷3”轉(zhuǎn)逆波蘭表達(dá)“682-2*3÷+”設(shè)計(jì)算法，編程實(shí)現(xiàn)。
分析：在數(shù)學(xué)運(yùn)算表達(dá)式中，運(yùn)算符總是置于與之相關(guān)的兩個(gè)運(yùn)算對(duì)象之間，在計(jì)算結(jié)果時(shí)，要考慮括號(hào)、運(yùn)算符號(hào)的優(yōu)先性。為了程序?qū)崿F(xiàn)的方便，波蘭邏輯學(xué)家J.Lukasiewicz提出了另一種表示法，將運(yùn)算符置于其運(yùn)算對(duì)象之后，沒(méi)有括號(hào)，不用考慮運(yùn)算符號(hào)的優(yōu)先性。這種表達(dá)式稱為后綴表達(dá)式，又叫逆波蘭表達(dá)式。
如表達(dá)式“682-2*3÷+”是四則運(yùn)算式“6+（8-2）*2÷3”的逆波蘭表達(dá)式。為了處理方便，規(guī)定表達(dá)式中的數(shù)均為小于10的正整數(shù)，運(yùn)算符為+、-、*、÷。
（1）抽象建模
設(shè)計(jì)兩個(gè)棧bds、fh,棧bds用來(lái)存放表達(dá)式，棧fh用來(lái)暫時(shí)存放運(yùn)算符。從左往右掃描四則運(yùn)算式，遇到數(shù)字時(shí)，入棧bds；遇到運(yùn)算符號(hào)時(shí)，根據(jù)運(yùn)算符號(hào)的優(yōu)先級(jí)設(shè)計(jì)進(jìn)棧與出棧。
四則運(yùn)算式“6+（8-2）*2÷3”轉(zhuǎn)換規(guī)則的模擬過(guò)程如表所示：
結(jié)合表格的操作過(guò)程，用棧bds和棧fh記錄每個(gè)操作后的棧內(nèi)情況（見(jiàn)圖），那么在操作2中棧fh里有內(nèi)容為（請(qǐng)從棧底到棧頂順序書寫）。
（2）設(shè)計(jì)算法
基于問(wèn)題的抽象與建模，解決該問(wèn)題的主要算法描述如下：
從左往右遍歷四則運(yùn)算式s（設(shè)中間變量為ch）：
1）當(dāng)ch是數(shù)字，直接入棧bds；
2）當(dāng)ch是運(yùn)算符：
a.若ch為左括號(hào)時(shí)，直接入棧fh；
b.若ch為右括號(hào)時(shí)，則將棧fh元素彈出，壓入棧bds,直到遇到左括號(hào)（左括號(hào)只
彈出，不壓入棧bds）；
c.若ch為其它運(yùn)算符時(shí)，如果運(yùn)算符ch優(yōu)先級(jí)大于棧fh中棧頂元素的優(yōu)先級(jí)（或棧fh為空），直接入棧fh；否則，將棧fh元素依次彈出，并壓入棧bds,直到運(yùn)算符ch優(yōu)先級(jí)大于棧fh中棧頂元素的優(yōu)先級(jí)（或棧fh為空）；
3）將棧bds中元素依次出棧，即為該四則運(yùn)算s的后綴表達(dá)式。
（3）編寫程序
實(shí)現(xiàn)上述功能的Python代碼如下，請(qǐng)?jiān)跈M線處填入合適代碼。
發(fā)布：2024/11/29 21:0:1組卷：17引用：2難度：0.3 -
3．一個(gè)棧的入棧序列為1，2，3，4，5，其出棧序列為sl,s2，s3，s4，s5。若s2是3，則s1不可能是（ ?。?/h2>
發(fā)布：2024/12/10 20:0:2組卷：15引用：4難度：0.5
把好題分享給你的好友吧~~