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è)問題:
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 為例子來(lái)講講計(jì)算機(jī)的轉(zhuǎn)換過程。
1.從左向右開始遍歷表達(dá)式,首先遇到a, 直接將其輸出
此時(shí)輸出 :a
棧的情況:空
2.繼續(xù)遍歷表達(dá)式,遇到+,此時(shí)???,則將其放入棧中
此時(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)文章
C語(yǔ)言return知識(shí)點(diǎn)總結(jié)
在本篇文章里小編給大家整理的是關(guān)于C語(yǔ)言return知識(shí)點(diǎn)總結(jié)內(nèi)容,需要的朋友們可以學(xué)習(xí)參考下。2020-02-02基于C++的攝像頭圖像采集及拼接程序的簡(jiǎn)單實(shí)現(xiàn)
本程序是在?ubuntu14.04?平臺(tái)下實(shí)現(xiàn)的,在本項(xiàng)目目錄下,已經(jīng)有編譯生成的可執(zhí)行程序,其中Camera_to_Frmae.cpp是我們從雙攝像頭實(shí)時(shí)抓取單幀圖像的源碼,對(duì)基于C++的攝像頭圖像采集及拼接程序的實(shí)現(xiàn)感興趣的朋友一起看看吧2022-01-01C++實(shí)現(xiàn)二分法的一些細(xì)節(jié)(常用場(chǎng)景)
二分法算法思想首先確定有根區(qū)間,將區(qū)間二等分,通過判斷f(x)的符號(hào),逐步將有根區(qū)間縮小,直至有根區(qū)間足夠小,便可求出滿足精度要求的近似值2021-07-07Qt?TCP網(wǎng)絡(luò)通信學(xué)習(xí)
用于數(shù)據(jù)傳輸?shù)牡蛯泳W(wǎng)絡(luò)協(xié)議,多個(gè)物聯(lián)網(wǎng)協(xié)議都是基于TCP協(xié)議的,這篇文章為大家介紹了Qt?TCP網(wǎng)絡(luò)通信,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-08-08Visual?Studio?2022?激活碼(親測(cè)可用)
在?Visual?Studio?2019?的基礎(chǔ)上,新版集成開發(fā)壞境提供了非常多的改進(jìn),包括對(duì)?64?位、.NET?6?的支持,為核心調(diào)試器提供更好的性能。本文給大家分享Visual?Studio?2022?激活碼,需要的朋友參考下吧2021-12-12