溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關C++如何實現中綴表達式轉化為后綴表達式，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
所謂后綴表達式是指這樣的一個表達式：式中不再引用括號，運算符號放在兩個運算對象之后，所有計算按運算符號出現的順序，嚴格地由左而右進行（不用考慮運算符的優先級）。
如：中綴表達式 3*(5–2)+7 對應的后綴表達式為：352-*7+ 。
請將給出的中綴表達式轉化為后綴表達式并輸出。
輸入樣例:
2+4*8+(8*8+1)/3
輸出樣例:
248*+88*1+3/+
對于中綴表達式轉換為后綴表達式，我們需要用以下步驟來解決這個問題：
1.初始化一個個棧：運算符棧S1
2.從左往右開始掃描中綴表達式
I.遇到數字，直接輸出
II.遇到運算符：
若為 '(' 直接入棧
若為 ')' 將符號棧中的元素依次出棧并輸出,直到 '(', '(' 只出棧，不輸出
若為其他符號，將符號棧中的元素依次出棧并將其輸出，直到遇到比當前符號優先級更低的符號或者 '('。將當前符號入棧。
掃描完后，將棧中剩余的符號依次輸出。
下面以 a + b * c +(d * e + f) * g 為例子來講講計算機的轉換過程。
1.從左向右開始遍歷表達式，首先遇到a, 直接將其輸出
此時輸出 ：a
棧的情況：空
2.繼續遍歷表達式，遇到+，此時棧空，則將其放入棧中
此時輸出 ：a
棧的情況：+
3.繼續遍歷表達式，遇到b，直接將其輸出
此時輸出 ：a b
棧的情況：+
4.繼續遍歷表達式，遇到*，因為*的優先級大于棧頂的+，所以將*入棧
此時輸出 ：a b
棧的情況：+*
5.繼續遍歷表達式，遇到c，直接將其輸出
此時輸出 ：a b c
棧的情況：+*
6.繼續遍歷表達式，遇到+, 因為+的優先級低于棧頂的*，所以將棧頂的*彈出；然后新的棧頂元素的+與當前的+優先級相同，所以也要將+彈出；然后棧空了，將現在這個+放入棧中
此時輸出 ：a b c * +
棧的情況：+
7.繼續遍歷表達式，遇到(，直接將其放入棧中，不遇到)不會將(彈出。
此時輸出為：a b c * +
棧的情況為：+(
8.繼續遍歷表達式，遇到d，直接將其輸出
此時輸出為：a b c * + d
棧的情況為：+(
9.繼續遍歷表達式，遇到*，因為棧頂為(,不遇到)不將(彈出,故直接將*放入棧中。
此時輸出為：a b c * + d
棧的情況為：+(*
10.繼續遍歷表達式，遇到e，直接將其輸出
此時輸出為：a b c * + d e
棧的情況為：+(*
11.繼續遍歷表達式，遇到+，因為+比棧頂*的優先級低，故將*彈出；新的棧頂元素為(,不遇到)不彈出(,故將+放入棧中。
此時輸出為：a b c * + d e *
棧的情況為：+(+
12.繼續遍歷表達式，遇到f，直接將其輸出
此時輸出為：a b c * + d e * f
棧的情況為：+(+
13.繼續遍歷表達式，遇到),直接將棧中元素依次彈出并輸出直到遇到(為止，注意：(彈出但不輸出。
此時輸出為：a b c * + d e * f +
棧的情況為：+
14.繼續遍歷表達式，遇到*，因為*的優先級大于棧頂元素+的優先級，故直接將*入棧。
此時輸出為：a b c * + d e * f +
棧的情況為：+ *
15.繼續遍歷表達式，遇到g，直接將其輸出。
此時輸出為：a b c * + d e * f + g
棧的情況為：+ *
16.繼續遍歷表達式，為空，遍歷結束。將棧內元素依次彈出。
此時輸出為：a b c * + d e * f + g * +
棧的情況為：空
至此，中綴表達式轉后綴已經全部完成，結果為 a b c * + d e * f + g * +
int priority(char op)
{
int priority;
if(op == '*' || op == '/') priority = 2;
if(op == '+' || op == '-') priority = 1;
if(op == '(') priority = 0;
return priority;
}//引用符號提高轉換效率
void Trans(string &str, string &str1)
{
stack<char> s;
int i;
for(i = 0; i < str.size(); i ++ )
{
//是數字的情況下直接輸出
if(str[i] >= '0' && str[i] <= '9' || str[i] >= 'a' && str[i] <= 'z')
{
str1 += str[i];
}
else //不是數字的情況分類討論進行判斷
{
//棧為空時直接入棧
if(s.empty()) s.push(str[i]);
//左括號入棧
else if(str[i] == '(') s.push(str[i]);
//如果是右括號，只要棧頂不是左括號，就彈出并輸出
else if(str[i] == ')')
{
while(s.top() != '(')
{
str1 += s.top();
s.pop();
}
//彈出左括號，但不輸出
s.pop();
}
else
{
//棧頂元素的優先級大于等于當前的運算符，就將其輸出
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;
}
//引用符號提高轉換效率
void Trans(string &str, string &str1)
{
stack<char> s;
int i;
for(i = 0; i < str.size(); i ++ )
{
//是數字的情況下直接輸出
if(str[i] >= '0' && str[i] <= '9' || str[i] >= 'a' && str[i] <= 'z')
{
str1 += str[i];
}
else //不是數字的情況分類討論進行判斷
{
//棧為空時直接入棧
if(s.empty()) s.push(str[i]);
//左括號入棧
else if(str[i] == '(') s.push(str[i]);
//如果是右括號，只要棧頂不是左括號，就彈出并輸出
else if(str[i] == ')')
{
while(s.top() != '(')
{
str1 += s.top();
s.pop();
}
//彈出左括號，但不輸出
s.pop();
}
else
{
//棧頂元素的優先級大于等于當前的運算符，就將其輸出
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()
{
//輸入前綴表達式
string infix;
string postfix;
cin >> infix;
Trans(infix, postfix);
cout << postfix << endl;
return 0;
}關于“C++如何實現中綴表達式轉化為后綴表達式”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
