




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第C++棧實(shí)現(xiàn)逆波蘭式的應(yīng)用目錄一.定義二.逆波蘭式的意義三.逆波蘭式的實(shí)現(xiàn)1.方法2.代碼實(shí)現(xiàn)
一.定義
逆波蘭式,又稱后綴表達(dá)式,指的是操作符在其所控制的操作數(shù)后面的表達(dá)式。
舉個(gè)例子,1+2*3-4這個(gè)表達(dá)式是我們熟悉的中綴表達(dá)式,那么其所對(duì)應(yīng)的后綴表達(dá)式為:123*+4-。
再來(lái)個(gè)復(fù)雜的例子:1*(2+3)/5-4/2其對(duì)應(yīng)的后綴表達(dá)式為:123+*5/42/-(其中括號(hào)由于只是提升表達(dá)式優(yōu)先級(jí)的作用,因此不放入后綴表達(dá)式中)。
二.逆波蘭式的意義
為什么要將看似簡(jiǎn)單的中綴表達(dá)式轉(zhuǎn)換為復(fù)雜的逆波蘭式,原因就在于這個(gè)簡(jiǎn)單是相對(duì)我們?nèi)祟惖乃季S結(jié)構(gòu)來(lái)說(shuō)的,對(duì)計(jì)算機(jī)而言中序表達(dá)式是非常復(fù)雜的結(jié)構(gòu)。相對(duì)的,逆波蘭式在計(jì)算機(jī)看來(lái)卻是比較簡(jiǎn)單易懂的結(jié)構(gòu)。因?yàn)橛?jì)算機(jī)普遍采用的內(nèi)存結(jié)構(gòu)是棧式結(jié)構(gòu),它執(zhí)行先進(jìn)后出的順序。
三.逆波蘭式的實(shí)現(xiàn)
1.方法
(1)中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式
對(duì)于給出的中綴表達(dá)式,如何將其轉(zhuǎn)化為后綴表達(dá)式呢?
第一,若遇到操作數(shù)則直接輸出/存儲(chǔ)。
第二,遇到操作符,若此時(shí)棧為空或者操作符優(yōu)先級(jí)高于棧頂,則入棧。
第三,若操作符的優(yōu)先級(jí)低于或者等于棧頂,則出棧直至??栈蛘邇?yōu)先級(jí)低于該操作符。
第四,遇到'(',其后的所有操作符(直至遇到')')按上述操作入?;虺鰲?;當(dāng)遇到')‘時(shí),將'('頂上的所有操作符出棧。
(2)由后綴表達(dá)式計(jì)算結(jié)果
第一,遇到操作數(shù)則入棧。
第二,遇到操作符則將棧頂?shù)膬蓚€(gè)操作數(shù)出棧,其中第一個(gè)數(shù)為右操作數(shù),第二個(gè)數(shù)為左操作數(shù)。
第三,計(jì)算結(jié)果并將計(jì)算的結(jié)果入棧。
第四,最后棧頂?shù)慕Y(jié)果即為所計(jì)算的結(jié)果。
2.代碼實(shí)現(xiàn)
#includeiostream
#includestring
#includestack
#includevector
usingnamespacestd;
stringtrans(strings)
stringoperand;
stackcharOperator;
intflag=0;//記錄括號(hào)優(yōu)先級(jí)
for(constautoe:s)
if(e=='(')
Operator.push(e);
flag=1;
continue;
if(e==')')
flag=0;
while(Operator.top()!='(')
operand.push_back(Operator.top());
Operator.pop();
Operator.pop();
continue;
//操作符
if(e=='+'||e=='-'||e=='*'||e=='/')
if(flag==1)
if(Operator.top()=='(')
Operator.push(e);
elseif((e=='*'||e=='/')(Operator.top()=='+'||Operator.top()=='-'))
Operator.push(e);
else//操作符的優(yōu)先級(jí)低于或等于棧頂操作符則出棧,直至遇到'('
while(Operator.top()!='(')
operand.push_back(Operator.top());
Operator.pop();
Operator.push(e);
elseif(Operator.empty())//棧空就入棧
Operator.push(e);
//操作符的優(yōu)先級(jí)高于棧頂操作符,入棧
elseif((e=='*'||e=='/')(Operator.top()=='+'||Operator.top()=='-'))
Operator.push(e);
else//操作符的優(yōu)先級(jí)低于或等于棧頂操作符則出棧,直至??栈蛘邇?yōu)先級(jí)高于棧頂操作符
while(!Operator.empty())
operand.push_back(Operator.top());
Operator.pop();
Operator.push(e);
//操作數(shù)
else
operand.push_back(e);
while(!Operator.empty())
operand.push_back(Operator.top());
Operator.pop();
returnoperand;
intevalRPN(conststrings)
stackcharoperand;
intleft=0,right=0;
for(constautoe:s)
if(e=='+'||e=='-'||e=='*'||e=='/')
switch(e)
case'+':
right=operand.top();
operand.pop();
left=operand.top();
operand.pop();
operand.push(left+right);
break;
case'-':
right=operand.top();
operand.pop();
left=operand.top();
operand.pop();
operand.push(left-right);
break;
case'*':
right=operand.top();
operand.pop();
left=operand.top();
operand.pop();
operand.push(left*right);
break;
case'/':
right=operand.top();
operand.pop();
left=operand.top();
operand.pop();
operand.push(left/right);
break;
else//操作數(shù)
operand.push(e-'0');
returnoperand.top();
intRPN(conststringstr)
//1.中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式
strings(str);
s=trans(s);
//2.后綴表達(dá)式計(jì)算答案
returnevalRPN(s);
intmain()
strings("1*(2*3+5)
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025建筑工程合同登記備案流程
- 情感分析與拍賣平臺(tái)用戶體驗(yàn)優(yōu)化-洞察闡釋
- 2024年上海青浦教育系統(tǒng)招聘事業(yè)編制教師真題
- 神經(jīng)內(nèi)科帕金森病基礎(chǔ)知識(shí)點(diǎn)歸納
- 2024年安康紫陽(yáng)縣特崗教師招聘真題
- 2025年四川輕化工大學(xué)數(shù)學(xué)競(jìng)賽試題
- 幼兒園保育工作相關(guān)表格與工作制度:實(shí)驗(yàn)幼兒園戶外活動(dòng)檢查記錄表
- 基于類間關(guān)系建模的異常區(qū)域分割算法研究
- 信息化背景下高中語(yǔ)文合格考的應(yīng)對(duì)策略
- 當(dāng)前建筑垃圾管理體系存在的主要問(wèn)題
- 污水處理過(guò)程
- APP開發(fā)及運(yùn)營(yíng)投資協(xié)議
- 青海省西寧市2025屆中考一模生物試題含解析
- 2025版 初中 語(yǔ)文 學(xué)考復(fù)習(xí) 第三部分 模擬練《江西省2025年初中語(yǔ)文學(xué)業(yè)水平考試模擬練(三)》課件
- 2024年危險(xiǎn)化學(xué)品生產(chǎn)經(jīng)營(yíng)單位其他從業(yè)人員考試題庫(kù)附答案
- DB45T 2364-2021 公路路基監(jiān)測(cè)技術(shù)規(guī)范
- 造價(jià)咨詢進(jìn)度控制措施全
- 電力儲(chǔ)能用飛輪儲(chǔ)能系統(tǒng)技術(shù)規(guī)范
- 必修二公式結(jié)論默寫-高中數(shù)學(xué)人教A版(2019)必修第二冊(cè)
- 2024年成人高考成考(專升本)醫(yī)學(xué)綜合試卷與參考答案
- 園林綠化風(fēng)險(xiǎn)因素辨識(shí)及防控措施考核試卷
評(píng)論
0/150
提交評(píng)論