C++實現(xiàn)中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式詳解
1.題目描述
所謂后綴表達(dá)式是指這樣的一個表達(dá)式:式中不再引用括號,運(yùn)算符號放在兩個運(yùn)算對象之后,所有計算按運(yùn)算符號出現(xiàn)的順序,嚴(yán)格地由左而右進(jìn)行(不用考慮運(yùn)算符的優(yōu)先級)。
如:中綴表達(dá)式 3*(5–2)+7 對應(yīng)的后綴表達(dá)式為:352-*7+ 。
請將給出的中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式并輸出。
2.輸入輸出
輸入樣例:
2+4*8+(8*8+1)/3
輸出樣例:
248*+88*1+3/+
3.解題思路
對于中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式,我們需要用以下步驟來解決這個問題:
1.初始化一個個棧:運(yùn)算符棧S1
2.從左往右開始掃描中綴表達(dá)式
I.遇到數(shù)字,直接輸出
II.遇到運(yùn)算符:
- 若為 '(' 直接入棧
- 若為 ')' 將符號棧中的元素依次出棧并輸出,直到 '(', '(' 只出棧,不輸出
- 若為其他符號,將符號棧中的元素依次出棧并將其輸出,直到遇到比當(dāng)前符號優(yōu)先級更低的符號或者 '('。將當(dāng)前符號入棧。
- 掃描完后,將棧中剩余的符號依次輸出。
4.樣例解析
下面以 a + b * c +(d * e + f) * g 為例子來講講計算機(jī)的轉(zhuǎn)換過程。
1.從左向右開始遍歷表達(dá)式,首先遇到a, 直接將其輸出
此時輸出 :a
棧的情況:空
2.繼續(xù)遍歷表達(dá)式,遇到+,此時??眨瑒t將其放入棧中
此時輸出 :a
棧的情況:+
3.繼續(xù)遍歷表達(dá)式,遇到b,直接將其輸出
此時輸出 :a b
棧的情況:+
4.繼續(xù)遍歷表達(dá)式,遇到*,因為*的優(yōu)先級大于棧頂?shù)?,所以將*入棧
此時輸出 :a b
棧的情況:+*
5.繼續(xù)遍歷表達(dá)式,遇到c,直接將其輸出
此時輸出 :a b c
棧的情況:+*
6.繼續(xù)遍歷表達(dá)式,遇到+, 因為+的優(yōu)先級低于棧頂?shù)?,所以將棧頂?shù)?彈出;然后新的棧頂元素的+與當(dāng)前的+優(yōu)先級相同,所以也要將+彈出;然后??樟?,將現(xiàn)在這個+放入棧中
此時輸出 :a b c * +
棧的情況:+
7.繼續(xù)遍歷表達(dá)式,遇到(,直接將其放入棧中,不遇到)不會將(彈出。
此時輸出為:a b c * +
棧的情況為:+(
8.繼續(xù)遍歷表達(dá)式,遇到d,直接將其輸出
此時輸出為:a b c * + d
棧的情況為:+(
9.繼續(xù)遍歷表達(dá)式,遇到*,因為棧頂為(,不遇到)不將(彈出,故直接將*放入棧中。
此時輸出為:a b c * + d
棧的情況為:+(*
10.繼續(xù)遍歷表達(dá)式,遇到e,直接將其輸出
此時輸出為:a b c * + d e
棧的情況為:+(*
11.繼續(xù)遍歷表達(dá)式,遇到+,因為+比棧頂*的優(yōu)先級低,故將*彈出;新的棧頂元素為(,不遇到)不彈出(,故將+放入棧中。
此時輸出為:a b c * + d e *
棧的情況為:+(+
12.繼續(xù)遍歷表達(dá)式,遇到f,直接將其輸出
此時輸出為:a b c * + d e * f
棧的情況為:+(+
13.繼續(xù)遍歷表達(dá)式,遇到),直接將棧中元素依次彈出并輸出直到遇到(為止,注意:(彈出但不輸出。
此時輸出為:a b c * + d e * f +
棧的情況為:+
14.繼續(xù)遍歷表達(dá)式,遇到*,因為*的優(yōu)先級大于棧頂元素+的優(yōu)先級,故直接將*入棧。
此時輸出為:a b c * + d e * f +
棧的情況為:+ *
15.繼續(xù)遍歷表達(dá)式,遇到g,直接將其輸出。
此時輸出為:a b c * + d e * f + g
棧的情況為:+ *
16.繼續(xù)遍歷表達(dá)式,為空,遍歷結(jié)束。將棧內(nèi)元素依次彈出。
此時輸出為:a b c * + d e * f + g * +
棧的情況為:空
至此,中綴表達(dá)式轉(zhuǎn)后綴已經(jīng)全部完成,結(jié)果為 a b c * + d e * f + g * +
5.代碼實現(xiàn)
5.1.優(yōu)先級確認(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ù)
//引用符號提高轉(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)行判斷 { //棧為空時直接入棧 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)前的運(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; } //引用符號提高轉(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)行判斷 { //棧為空時直接入棧 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)前的運(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++實現(xiàn)中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式詳解的詳細(xì)內(nèi)容,更多關(guān)于C++中綴轉(zhuǎn)后綴表達(dá)式的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
C++實現(xiàn)二分法的一些細(xì)節(jié)(常用場景)
二分法算法思想首先確定有根區(qū)間,將區(qū)間二等分,通過判斷f(x)的符號,逐步將有根區(qū)間縮小,直至有根區(qū)間足夠小,便可求出滿足精度要求的近似值2021-07-07Qt?TCP網(wǎng)絡(luò)通信學(xué)習(xí)
用于數(shù)據(jù)傳輸?shù)牡蛯泳W(wǎng)絡(luò)協(xié)議,多個物聯(lián)網(wǎng)協(xié)議都是基于TCP協(xié)議的,這篇文章為大家介紹了Qt?TCP網(wǎng)絡(luò)通信,文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-08-08