十、從中綴向后綴轉換表達式

文章目錄

• 十、從中綴向后綴轉換表達式
• • 題目描述
  • 解題思路
  • 上機代碼

題目描述

中綴表達式就是我們通常所書寫的數學表達式，后綴表達式也稱為逆波蘭表達式，在編譯程序對我們書寫的程序中的表達式進行語法檢查時，往往就可以通過逆波蘭表達式進行。我們所要設計并實現的程序就是將中綴表示的算術表達式轉換成后綴表示，例如，將中綴表達式

(A 一 (B*C 十 D) *E) ／ (F 十 G )

轉換為后綴表示為：

ABC*D 十 E * 一 FG十／

**注意：**為了簡化編程實現，假定變量名均為單個字母，運算符只有＋，－，＊，／ 和＾（指數運算），可以處理圓括號（），并假定輸入的算術表達式正確。

**要求：**使用棧數據結構實現 ，輸入的中綴表達式以＃號結束

輸入：

整數N。表示下面有N個中綴表達式
N個由單個字母、整數和運算符構成的表達式

輸出：

N個后綴表達式。

測試輸入期待的輸出時間限制內存限制額外進程

測試用例 1	1 (A-(B*C+D)*E)/(F+G)#	ABC*D+E*-FG+/	1秒	64M	0
測試用例 2	2 a+b*c-d# a-b*(c+d)#	abc*+d- abcd+*-	1秒	64M	0

解題思路

后綴表達式中不含有括號，且后綴表達式中的操作數順序和中綴表達式的操作數順序完全相同，只是運算符的位置改變了。考慮用棧來實現，我們可以設置兩個棧，一個 opt 棧用來存放運算符，一個 exp 棧用來存放最后的后綴表達式

在將中綴表達式轉換為后綴的時候，遵循的原則是：

• 從左到右依次掃描中綴表達式，如果讀到的是操作數，直接存入 exp 棧
• 如果讀到的是運算符，則進行判斷
  • 該運算符是 ’ ( '，則直接存入 opt 棧
  • 該運算符是 ’ ) '，則將 opt 棧中對應 ‘(’ 前的所有運算符出棧，存入 exp 棧（這一對括號就可以直接舍棄了）
• 如果該運算符不是括號，則將該運算符和 opt 棧頂運算符做比較
  • 優先級大于或等于 opt 棧頂運算符，則直接存入 opt 棧
  • 優先級小于 opt 棧頂運算符，則讓 opt 棧頂運算符出棧并存入 exp 棧中。如果此時新的棧頂運算符優先級大于等于該運算符，繼續讓棧頂運算符出棧存入exp棧。最后再將該運算符存入 opt 棧
• 當掃描完成后，opt 棧中還有運算符，則將 opt 所有運算符出棧，存入 exp 棧中

符號的優先級定義如下：

• ( 優先級為 1
• +、-優先級為 3
• *、/優先級為 3
• ^ 優先級為 7
• ) 優先級為 9

對于 測試用例1 的轉換過程如下：

掃描字符串opt棧exp棧

(	(	空
(A	(	A
(A-	(-	A
(A-(	(-(	A
(A-(B	(-(	AB
(A-(B*	(-(*	AB
(A-(B*C	(-(*	ABC
(A-(B*C+	(-(+	ABC*
(A-(B*C+D	(-(+	ABC*D
(A-(B*C+D)	(-	ABC*D+
(A-(B*C+D)*	(-*	ABC*D+
(A-(B*C+D)*E	(-*	ABC*D+E
(A-(B*C+D)*E)	空	ABC*D+E*-
(A-(B*C+D)*E)/	/	ABC*D+E*-
(A-(B*C+D)*E)/(	/(	ABC*D+E*-
(A-(B*C+D)*E)/(F	/(	ABC*D+E*-F
(A-(B*C+D)*E)/(F+	/(+	ABC*D+E*-F
(A-(B*C+D)*E)/(F+G	/(+	ABC*D+E*-FG
(A-(B*C+D)*E)/(F+G)	/	ABC*D+E*-FG+
(A-(B*C+D)*E)/(F+G)#	空	ABC*D+E*-FG+/

上機代碼

懶得手寫 C 的棧了，我就直接使用了 C ++ 封裝好的棧

#include<cstdio> #include<cstdlib> #include<cstring> #include<stack> using namespace std;bool JudgeOpt(char a, char b) {//判斷兩個運算符優先級int value1 = 0, value2 = 0;switch(a){case '(': value1 = 1;break;case '+': value1 = 3;break;case '-': value1 = 3;break;case '*': value1 = 5;break;case '/': value1 = 5;break;case '^': value1 = 7;break;case ')': value1 = 9;break;}switch(b){case '(': value2 = 1;break;case '+': value2 = 3;break;case '-': value2 = 3;break;case '*': value2 = 5;break;case '/': value2 = 5;break;case '^': value2 = 7;break;case ')': value2 = 9;break;}//優先級a<b則falseif(value1 - value2 < 0)return false;elsereturn true; } int main() {int n = 0;scanf("%d",&n);stack<char> opt,exp;while(n--){//初始化兩個棧while(!opt.empty())opt.pop();while(!exp.empty())exp.pop();char str[110];scanf("%s",str);char ch; //用一個ch來表示str[i]//求字符串長度int len = 0;while(str[len]!='\0')len++;//掃描字符串for(int i = 0; i < len; i++){ch = str[i];if(ch == '#') //掃描完畢則退出break;//操作數直接壓棧if((ch >= 'a'&& ch <= 'z') || (ch >= 'A'&& ch <= 'Z') || (ch >= '0'&& ch <= '9'))exp.push(ch);else //判斷括號{if(ch == '(')//左括號直接壓棧opt.push(ch);else if(ch == ')')//右括號則取opt中對應的操作符存入exp中{while(opt.top()!='('){exp.push(opt.top());opt.pop();}opt.pop();//舍棄棧頂的左括號}else //判斷運算符{if(opt.empty() || JudgeOpt(ch, opt.top()))//優先級大直接存入{opt.push(ch);}else //優先級小，棧頂元素出棧{exp.push(opt.top());opt.pop();while(!opt.empty())//繼續出棧{if(JudgeOpt(opt.top(), ch)){exp.push(opt.top());opt.pop();}elsebreak;}opt.push(ch);//最后ch存入opt}}}}//將opt剩余運算符存入exp中while(!opt.empty()){exp.push(opt.top());opt.pop();}//取出exp的后綴表達式，逆序輸出int num = 1;while(!exp.empty()){str[num++]=exp.top();exp.pop();}for(int i = num - 1; i > 0; i--){printf("%c", str[i]);}printf("\n");}return 0; }

總結

以上是生活随笔為你收集整理的十、从中缀向后缀转换表达式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。