您好,登錄后才能下訂單哦!
這篇文章將為大家詳細講解有關(guān)C++如何實現(xiàn)中綴表達式轉(zhuǎn)化為后綴表達式,小編覺得挺實用的,因此分享給大家做個參考,希望大家閱讀完這篇文章后可以有所收獲。
所謂后綴表達式是指這樣的一個表達式:式中不再引用括號,運算符號放在兩個運算對象之后,所有計算按運算符號出現(xiàn)的順序,嚴(yán)格地由左而右進行(不用考慮運算符的優(yōu)先級)。
如:中綴表達式 3*(5–2)+7 對應(yīng)的后綴表達式為:352-*7+ 。
請將給出的中綴表達式轉(zhuǎn)化為后綴表達式并輸出。
輸入樣例:
2+4*8+(8*8+1)/3
輸出樣例:
248*+88*1+3/+
對于中綴表達式轉(zhuǎn)換為后綴表達式,我們需要用以下步驟來解決這個問題:
1.初始化一個個棧:運算符棧S1
2.從左往右開始掃描中綴表達式
I.遇到數(shù)字,直接輸出
II.遇到運算符:
若為 '(' 直接入棧
若為 ')' 將符號棧中的元素依次出棧并輸出,直到 '(', '(' 只出棧,不輸出
若為其他符號,將符號棧中的元素依次出棧并將其輸出,直到遇到比當(dāng)前符號優(yōu)先級更低的符號或者 '('。將當(dāng)前符號入棧。
掃描完后,將棧中剩余的符號依次輸出。
下面以 a + b * c +(d * e + f) * g 為例子來講講計算機的轉(zhuǎn)換過程。
1.從左向右開始遍歷表達式,首先遇到a, 直接將其輸出
此時輸出 :a
棧的情況:空
2.繼續(xù)遍歷表達式,遇到+,此時棧空,則將其放入棧中
此時輸出 :a
棧的情況:+
3.繼續(xù)遍歷表達式,遇到b,直接將其輸出
此時輸出 :a b
棧的情況:+
4.繼續(xù)遍歷表達式,遇到*,因為*的優(yōu)先級大于棧頂?shù)?,所以將*入棧
此時輸出 :a b
棧的情況:+*
5.繼續(xù)遍歷表達式,遇到c,直接將其輸出
此時輸出 :a b c
棧的情況:+*
6.繼續(xù)遍歷表達式,遇到+, 因為+的優(yōu)先級低于棧頂?shù)?,所以將棧頂?shù)?彈出;然后新的棧頂元素的+與當(dāng)前的+優(yōu)先級相同,所以也要將+彈出;然后棧空了,將現(xiàn)在這個+放入棧中
此時輸出 :a b c * +
棧的情況:+
7.繼續(xù)遍歷表達式,遇到(,直接將其放入棧中,不遇到)不會將(彈出。
此時輸出為:a b c * +
棧的情況為:+(
8.繼續(xù)遍歷表達式,遇到d,直接將其輸出
此時輸出為:a b c * + d
棧的情況為:+(
9.繼續(xù)遍歷表達式,遇到*,因為棧頂為(,不遇到)不將(彈出,故直接將*放入棧中。
此時輸出為:a b c * + d
棧的情況為:+(*
10.繼續(xù)遍歷表達式,遇到e,直接將其輸出
此時輸出為:a b c * + d e
棧的情況為:+(*
11.繼續(xù)遍歷表達式,遇到+,因為+比棧頂*的優(yōu)先級低,故將*彈出;新的棧頂元素為(,不遇到)不彈出(,故將+放入棧中。
此時輸出為:a b c * + d e *
棧的情況為:+(+
12.繼續(xù)遍歷表達式,遇到f,直接將其輸出
此時輸出為:a b c * + d e * f
棧的情況為:+(+
13.繼續(xù)遍歷表達式,遇到),直接將棧中元素依次彈出并輸出直到遇到(為止,注意:(彈出但不輸出。
此時輸出為:a b c * + d e * f +
棧的情況為:+
14.繼續(xù)遍歷表達式,遇到*,因為*的優(yōu)先級大于棧頂元素+的優(yōu)先級,故直接將*入棧。
此時輸出為:a b c * + d e * f +
棧的情況為:+ *
15.繼續(xù)遍歷表達式,遇到g,直接將其輸出。
此時輸出為:a b c * + d e * f + g
棧的情況為:+ *
16.繼續(xù)遍歷表達式,為空,遍歷結(jié)束。將棧內(nèi)元素依次彈出。
此時輸出為:a b c * + d e * f + g * +
棧的情況為:空
至此,中綴表達式轉(zhuǎn)后綴已經(jīng)全部完成,結(jié)果為 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; }
//引用符號提高轉(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ù)字的情況分類討論進行判斷 { //棧為空時直接入棧 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 { //棧頂元素的優(yōu)先級大于等于當(dāng)前的運算符,就將其輸出 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; } //引用符號提高轉(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ù)字的情況分類討論進行判斷 { //棧為空時直接入棧 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 { //棧頂元素的優(yōu)先級大于等于當(dāng)前的運算符,就將其輸出 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; }
關(guān)于“C++如何實現(xiàn)中綴表達式轉(zhuǎn)化為后綴表達式”這篇文章就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,使各位可以學(xué)到更多知識,如果覺得文章不錯,請把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。