C++實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式詳解

第C++實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式詳解目錄1.題目描述2.輸入輸出3.解題思路4.樣例解析5.代碼實(shí)現(xiàn)5.1.優(yōu)先級(jí)確認(rèn)5.2.轉(zhuǎn)換函數(shù)

1.題目描述

所謂后綴表達(dá)式是指這樣的一個(gè)表達(dá)式：式中不再引用括號(hào)，運(yùn)算符號(hào)放在兩個(gè)運(yùn)算對(duì)象之后，所有計(jì)算按運(yùn)算符號(hào)出現(xiàn)的順序，嚴(yán)格地由左而右進(jìn)行（不用考慮運(yùn)算符的優(yōu)先級(jí)）。

如：中綴表達(dá)式3*(52)+7對(duì)應(yīng)的后綴表達(dá)式為：352-*7+。

請(qǐng)將給出的中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式并輸出。

2.輸入輸出

輸入樣例:

2+4*8+(8*8+1)/3

輸出樣例:

248*+88*1+3/+

3.解題思路

對(duì)于中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，我們需要用以下步驟來解決這個(gè)問題：

1.初始化一個(gè)個(gè)棧：運(yùn)算符棧S1

2.從左往右開始掃描中綴表達(dá)式

I.遇到數(shù)字，直接輸出

II.遇到運(yùn)算符：

若為(直接入棧若為)將符號(hào)棧中的元素依次出棧并輸出,直到(,(只出棧，不輸出若為其他符號(hào)，將符號(hào)棧中的元素依次出棧并將其輸出，直到遇到比當(dāng)前符號(hào)優(yōu)先級(jí)更低的符號(hào)或者(。將當(dāng)前符號(hào)入棧。掃描完后，將棧中剩余的符號(hào)依次輸出。

4.樣例解析

下面以a+b*c+(d*e+f)*g為例子來講講計(jì)算機(jī)的轉(zhuǎn)換過程。

1.從左向右開始遍歷表達(dá)式，首先遇到a,直接將其輸出

此時(shí)輸出：a

棧的情況：空

2.繼續(xù)遍歷表達(dá)式，遇到+，此時(shí)棧空，則將其放入棧中

此時(shí)輸出：a

棧的情況：+

3.繼續(xù)遍歷表達(dá)式，遇到b，直接將其輸出

此時(shí)輸出：ab

棧的情況：+

4.繼續(xù)遍歷表達(dá)式，遇到*，因?yàn)?的優(yōu)先級(jí)大于棧頂?shù)?，所以將*入棧

此時(shí)輸出：ab

棧的情況：+*

5.繼續(xù)遍歷表達(dá)式，遇到c，直接將其輸出

此時(shí)輸出：abc

棧的情況：+*

6.繼續(xù)遍歷表達(dá)式，遇到+,因?yàn)?的優(yōu)先級(jí)低于棧頂?shù)?，所以將棧頂?shù)?彈出；然后新的棧頂元素的+與當(dāng)前的+優(yōu)先級(jí)相同，所以也要將+彈出；然后?？樟?，將現(xiàn)在這個(gè)+放入棧中

此時(shí)輸出：abc*+

棧的情況：+

7.繼續(xù)遍歷表達(dá)式，遇到(，直接將其放入棧中，不遇到)不會(huì)將(彈出。

此時(shí)輸出為：abc*+

棧的情況為：+(

8.繼續(xù)遍歷表達(dá)式，遇到d，直接將其輸出

此時(shí)輸出為：abc*+d

棧的情況為：+(

9.繼續(xù)遍歷表達(dá)式，遇到*，因?yàn)闂ｍ敒?,不遇到)不將(彈出,故直接將*放入棧中。

此時(shí)輸出為：abc*+d

棧的情況為：+(*

10.繼續(xù)遍歷表達(dá)式，遇到e，直接將其輸出

此時(shí)輸出為：abc*+de

棧的情況為：+(*

11.繼續(xù)遍歷表達(dá)式，遇到+，因?yàn)?比棧頂*的優(yōu)先級(jí)低，故將*彈出；新的棧頂元素為(,不遇到)不彈出(,故將+放入棧中。

此時(shí)輸出為：abc*+de*

棧的情況為：+(+

12.繼續(xù)遍歷表達(dá)式，遇到f，直接將其輸出

此時(shí)輸出為：abc*+de*f

棧的情況為：+(+

13.繼續(xù)遍歷表達(dá)式，遇到),直接將棧中元素依次彈出并輸出直到遇到(為止，注意：(彈出但不輸出。

此時(shí)輸出為：abc*+de*f+

棧的情況為：+

14.繼續(xù)遍歷表達(dá)式，遇到*，因?yàn)?的優(yōu)先級(jí)大于棧頂元素+的優(yōu)先級(jí)，故直接將*入棧。

此時(shí)輸出為：abc*+de*f+

棧的情況為：+*

15.繼續(xù)遍歷表達(dá)式，遇到g，直接將其輸出。

此時(shí)輸出為：abc*+de*f+g

棧的情況為：+*

16.繼續(xù)遍歷表達(dá)式，為空，遍歷結(jié)束。將棧內(nèi)元素依次彈出。

此時(shí)輸出為：abc*+de*f+g*+

棧的情況為：空

至此，中綴表達(dá)式轉(zhuǎn)后綴已經(jīng)全部完成，結(jié)果為abc*+de*f+g*+

5.代碼實(shí)現(xiàn)

5.1.優(yōu)先級(jí)確認(rèn)

intpriority(charop)

intpriority;

if(op=='*'||op=='/')priority=2;

if(op=='+'||op=='-')priority=1;

if(op=='(')priority=0;

returnpriority;

}

5.2.轉(zhuǎn)換函數(shù)

//引用符號(hào)提高轉(zhuǎn)換效率

voidTrans(stringstr,stringstr1)

stackchar

inti;

for(i=0;istr.size();i++)

//是數(shù)字的情況下直接輸出

if(str[i]='0'str[i]='9'||str[i]='a'str[i]='z')

str1+=str[i];

else//不是數(shù)字的情況分類討論進(jìn)行判斷

//棧為空時(shí)直接入棧

if(s.empty())s.push(str[i]);

//左括號(hào)入棧

elseif(str[i]=='(')s.push(str[i]);

//如果是右括號(hào)，只要棧頂不是左括號(hào)，就彈出并輸出

elseif(str[i]==')')

while(s.top()!='(')

str1+=s.top();

s.pop();

//彈出左括號(hào)，但不輸出

s.pop();

else

//棧頂元素的優(yōu)先級(jí)大于等于當(dāng)前的運(yùn)算符，就將其輸出

while(priority(str[i])=priorty(s.top()))

str1+=s.top();

s.pop();

//棧為空，停止

if(s.empty())break;

s.push(str[i]);

//最后，如果不為空，就把所以的元素全部彈出

while(!s.empty())

str1+=s.top();

s.pop();

}

#includeiostream

#includecstring

#includestack

usingnamespacestd;

intpriority(charop)

intpriority;

if(op=='*'||op=='/')priority=2;

if(op=='+'||op=='-')priority=1;

if(op=='(')priority=0;

returnpriority;

//引用符號(hào)提高轉(zhuǎn)換效率

voidTrans(stringstr,stringstr1)

stackchar

inti;

for(i=0;istr.size();i++)

//是數(shù)字的情況下直接輸出

if(str[i]='0'str[i]='9'||str[i]='a'str[i]='z')

str1+=str[i];

else//不是數(shù)字的情況分類討論進(jìn)行判斷

//棧為空時(shí)直接入棧

if(s.empty())s.push(str[i]);

//左括號(hào)入棧

elseif(str[i]=='(')s.push(str[i]);

//如果是右括號(hào)，只要棧頂不是左括號(hào)，就彈出并輸出

elseif(str[i]==')')

while(s.top()!='(')

str1+=s.top();

s.pop();

//彈出左括號(hào)，但不輸出

s.pop();

else

//棧頂元素的優(yōu)先級(jí)大于等于當(dāng)前的運(yùn)算符，就將其輸出

while(priority(str[i])=priorty(s.top()))

str1+=s.top();

s.pop();

//棧為空，停止

if(s.empty())break;

s.push(str[i]);

//最后，如果不為空，就把所以的元素全部彈出

while(!s.empty())

str1+=s.top();

s.pop();