網站首頁 編程語言 正文
1.題目描述
所謂后綴表達式是指這樣的一個表達式:式中不再引用括號,運算符號放在兩個運算對象之后,所有計算按運算符號出現的順序,嚴格地由左而右進行(不用考慮運算符的優先級)。
如:中綴表達式 3*(5–2)+7 對應的后綴表達式為:352-*7+ 。
請將給出的中綴表達式轉化為后綴表達式并輸出。
2.輸入輸出
輸入樣例:?
2+4*8+(8*8+1)/3
輸出樣例:
248*+88*1+3/+
3.解題思路
對于中綴表達式轉換為后綴表達式,我們需要用以下步驟來解決這個問題:
1.初始化一個個棧:運算符棧S1
2.從左往右開始掃描中綴表達式
I.遇到數字,直接輸出
II.遇到運算符:
- 若為 '(' ?直接入棧
- 若為 ')' ?將符號棧中的元素依次出棧并輸出,直到 '(', '(' 只出棧,不輸出
- 若為其他符號,將符號棧中的元素依次出棧并將其輸出,直到遇到比當前符號優先級更低的符號或者 '('。將當前符號入棧。
- 掃描完后,將棧中剩余的符號依次輸出。
4.樣例解析?
下面以 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 * +
5.代碼實現
5.1.優先級確認
int priority(char op) { int priority; if(op == '*' || op == '/') priority = 2; if(op == '+' || op == '-') priority = 1; if(op == '(') priority = 0; return priority; }
5.2.轉換函數
//引用符號提高轉換效率 void Trans(string &str, string &str1) { stacks; 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#include #include 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 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; }
原文鏈接:https://blog.csdn.net/forever_bryant/article/details/123651211
相關推薦
- 2022-10-09 React?Redux使用配置詳解_React
- 2022-07-06 C語言深入探究自定義類型之結構體與枚舉及聯合_C 語言
- 2023-02-17 golang基礎之waitgroup用法以及使用要點_Golang
- 2022-05-07 Python使用matplotlib給柱狀圖添加數據標簽bar_label()_python
- 2022-04-25 ASP.NET?Core?MVC中Form?Tag?Helpers用法介紹_實用技巧
- 2022-06-16 原生實現C#與Lua相互調用方法(Unity3D可用)_C#教程
- 2022-10-22 C#?設置Chart的X軸為時間軸???????詳情_C#教程
- 2022-10-09 C#實現線性查找算法_C#教程
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版(
- Linux 中運行的top命令 怎么退出?
- MySQL 中decimal 的用法? 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符,流程控制 Flo
- 1. Int 和Integer 的區別,Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤:Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密?
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串(SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列,發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支