C++實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式詳解
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*(5–2)+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á)式,我們需要用以下步驟來(lái)解決這個(gè)問(wèn)題:
1.初始化一個(gè)個(gè)棧:運(yùn)算符棧S1
2.從左往右開(kāi)始掃描中綴表達(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 為例子來(lái)講講計(jì)算機(jī)的轉(zhuǎn)換過(guò)程。
1.從左向右開(kāi)始遍歷表達(dá)式,首先遇到a, 直接將其輸出
此時(shí)輸出 :a
棧的情況:空
2.繼續(xù)遍歷表達(dá)式,遇到+,此時(shí)??眨瑒t將其放入棧中
此時(shí)輸出 :a
棧的情況:+
3.繼續(xù)遍歷表達(dá)式,遇到b,直接將其輸出
此時(shí)輸出 :a b
棧的情況:+
4.繼續(xù)遍歷表達(dá)式,遇到*,因?yàn)?的優(yōu)先級(jí)大于棧頂?shù)?,所以將*入棧
此時(shí)輸出 :a b
棧的情況:+*
5.繼續(xù)遍歷表達(dá)式,遇到c,直接將其輸出
此時(shí)輸出 :a b c
棧的情況:+*
6.繼續(xù)遍歷表達(dá)式,遇到+, 因?yàn)?的優(yōu)先級(jí)低于棧頂?shù)?,所以將棧頂?shù)?彈出;然后新的棧頂元素的+與當(dāng)前的+優(yōu)先級(jí)相同,所以也要將+彈出;然后棧空了,將現(xiàn)在這個(gè)+放入棧中
此時(shí)輸出 :a b c * +
棧的情況:+
7.繼續(xù)遍歷表達(dá)式,遇到(,直接將其放入棧中,不遇到)不會(huì)將(彈出。
此時(shí)輸出為:a b c * +
棧的情況為:+(
8.繼續(xù)遍歷表達(dá)式,遇到d,直接將其輸出
此時(shí)輸出為:a b c * + d
棧的情況為:+(
9.繼續(xù)遍歷表達(dá)式,遇到*,因?yàn)闂m敒?,不遇到)不將(彈出,故直接將*放入棧中。
此時(shí)輸出為:a b c * + d
棧的情況為:+(*
10.繼續(xù)遍歷表達(dá)式,遇到e,直接將其輸出
此時(shí)輸出為:a b c * + d e
棧的情況為:+(*
11.繼續(xù)遍歷表達(dá)式,遇到+,因?yàn)?比棧頂*的優(yōu)先級(jí)低,故將*彈出;新的棧頂元素為(,不遇到)不彈出(,故將+放入棧中。
此時(shí)輸出為:a b c * + d e *
棧的情況為:+(+
12.繼續(xù)遍歷表達(dá)式,遇到f,直接將其輸出
此時(shí)輸出為:a b c * + d e * f
棧的情況為:+(+
13.繼續(xù)遍歷表達(dá)式,遇到),直接將棧中元素依次彈出并輸出直到遇到(為止,注意:(彈出但不輸出。
此時(shí)輸出為:a b c * + d e * f +
棧的情況為:+
14.繼續(xù)遍歷表達(dá)式,遇到*,因?yàn)?的優(yōu)先級(jí)大于棧頂元素+的優(yōu)先級(jí),故直接將*入棧。
此時(shí)輸出為:a b c * + d e * f +
棧的情況為:+ *
15.繼續(xù)遍歷表達(dá)式,遇到g,直接將其輸出。
此時(shí)輸出為:a b c * + d e * f + g
棧的情況為:+ *
16.繼續(xù)遍歷表達(dá)式,為空,遍歷結(jié)束。將棧內(nèi)元素依次彈出。
此時(shí)輸出為:a b c * + d e * f + g * +
棧的情況為:空
至此,中綴表達(dá)式轉(zhuǎn)后綴已經(jīng)全部完成,結(jié)果為 a b c * + d e * f + g * +
5.代碼實(shí)現(xiàn)
5.1.優(yōu)先級(jí)確認(rèn)

int priority(char op)
{
int priority;
if(op == '*' || op == '/') priority = 2;
if(op == '+' || op == '-') priority = 1;
if(op == '(') priority = 0;
return priority;
}5.2.轉(zhuǎn)換函數(shù)
//引用符號(hào)提高轉(zhuǎn)換效率
void Trans(string &str, string &str1)
{
stack<char> s;
int i;
for(i = 0; i < str.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)入棧
else if(str[i] == '(') s.push(str[i]);
//如果是右括號(hào),只要棧頂不是左括號(hào),就彈出并輸出
else if(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();
}
}#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
int priority(char op)
{
int priority;
if(op == '*' || op == '/') priority = 2;
if(op == '+' || op == '-') priority = 1;
if(op == '(') priority = 0;
return priority;
}
//引用符號(hào)提高轉(zhuǎn)換效率
void Trans(string &str, string &str1)
{
stack<char> s;
int i;
for(i = 0; i < str.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)入棧
else if(str[i] == '(') s.push(str[i]);
//如果是右括號(hào),只要棧頂不是左括號(hào),就彈出并輸出
else if(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();
}
}
int main()
{
//輸入前綴表達(dá)式
string infix;
string postfix;
cin >> infix;
Trans(infix, postfix);
cout << postfix << endl;
return 0;
}以上就是C++實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式詳解的詳細(xì)內(nèi)容,更多關(guān)于C++中綴轉(zhuǎn)后綴表達(dá)式的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
VSCode Linux的C++代碼格式化配置的實(shí)現(xiàn)
動(dòng)格式化代碼容易出現(xiàn)錯(cuò)誤,特別是當(dāng)代碼量較大時(shí),使用自動(dòng)格式化可以減少這種錯(cuò)誤的風(fēng)險(xiǎn),本文主要介紹了VSCode Linux的C++代碼格式化配置的實(shí)現(xiàn),感興趣的可以了解一下2023-10-10
C++實(shí)現(xiàn)數(shù)據(jù)保留小數(shù)點(diǎn)后兩位的常見(jiàn)方法
在計(jì)算機(jī)程序中,保留小數(shù)點(diǎn)后兩位通常需要使用特定的函數(shù)或方法來(lái)實(shí)現(xiàn),本文給大家介紹了C++實(shí)現(xiàn)數(shù)據(jù)保留小數(shù)點(diǎn)后兩位的常見(jiàn)方法,并通過(guò)代碼講解的非常詳細(xì),需要的朋友可以參考下2025-03-03
C++雙線程調(diào)用網(wǎng)絡(luò)攝像頭與多線程調(diào)用多攝像頭同步執(zhí)行方法詳細(xì)講解
這篇文章主要介紹了C++雙線程調(diào)用網(wǎng)絡(luò)攝像頭與多線程調(diào)用多攝像頭同步執(zhí)行方法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧2022-11-11
VisualStudio?制作Dynamic?Link?Library動(dòng)態(tài)鏈接庫(kù)文件的詳細(xì)過(guò)程
這篇文章主要介紹了VisualStudio?制作Dynamic?Link?Library動(dòng)態(tài)鏈接庫(kù)文件的詳細(xì)過(guò)程,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-08-08
Java3D實(shí)例之創(chuàng)建空間幾何模型的實(shí)現(xiàn)方法
本篇文章是對(duì)Java3D 創(chuàng)建空間幾何模型的實(shí)現(xiàn)方法進(jìn)行了詳細(xì)的介紹。需要的朋友參考下2013-05-05

