舉一個中綴表達式的例子：a+b-a*((c+d)/e-f)+g

一、中綴表達式轉后綴表達式

方法一：括號法

比較簡單方便。

①按照運算符的優(yōu)先級，對所有的運算單位加括號。

于是變成：(((a+b)-(a*(((c+d)/e)-f)))+g)

②從最里面的括號開始，依次把運算符號移動到對應的括號的后面。

于是變成：(((ab)+(a(((cd)+e)/f)-)*)-g)+

③最后，把括號都去掉

于是變成：ab+acd+e/f-*-g+

?

方法二：利用語法樹

略。

?

方法三：基于堆棧的算法

具體轉換方式:

從左到右進行遍歷。

1.遇到的是運算數，直接輸出。

2.遇到的是左括號'('，直接壓入堆棧(括號是最高優(yōu)先級，無需比較；入棧后優(yōu)先級降到最低，確保其他符號正常入棧)。

3.遇到的是右括號')'，意味著括號已結束。不斷彈出棧頂運算符并輸出，直到遇到左括號，這個左括號彈出但是不輸出。

4.遇到的是運算符('+'、'-'、'*'、'/')，有三種情況

①如果棧為空，直接入棧。

②如果棧頂元素是左括號'('，直接入棧。

③如果棧頂元素是運算符，則需要進行比較，

1-如果優(yōu)先級大于棧頂運算符，則壓入堆棧；

2-如果優(yōu)先級小于等于棧頂運算符，則將棧頂運算符彈出并輸出，然后比較新的棧頂運算符，直到優(yōu)先級大于棧頂運算符或者棧空，再將該運算符入棧

5.如果對象處理完畢，則按順序彈出并輸出棧中所有運算符

算法如下：

/* 中綴轉后綴 思路： 中綴存于一個字符數組infix[]里，有一個輔助棧s1，棧頂元素為top1，有一個結果棧s2，棧頂元素為top2。 從左向右掃描。i=0，當infix[i]!='\0'時， 1、碰到'0'-'9'，存入s2中。 2、碰到'('，存入s1中。 3、碰到'+'、'-'、'*'、'/'，如果棧為空，或者top1='('，或者運算符的優(yōu)先級大于top1棧頂元素的優(yōu)先級，存入s1中；否則s2[++top2]=s1[top1--]。 4、碰到')'，將s1里截止到'('以前的元素全部放到s2中，并把'('丟掉 *///判斷運算符的優(yōu)先級 int getPriority(char op){if(op=='+'||op=='-')return 0; //+或-的優(yōu)先級比較低elsereturn 1; }void infixToPostFix(char infix[], char s2[], int &top2) //infix[]是中綴表達式存在數組里，s2是結果棧 {char s1[maxSize]; int top1=-1; //s1是輔助棧int i=0;while(infix[i]!='\0'){if('0'<=infix[i]&&infix[i]<='9'){ //如果掃描到'0'-'9'字符，將它放入s2s2[++top2]==infix[i];++i;}else if(infix[i]=='('){ //如果掃描到'('，將它放入s1s1[++top1]='(';++i;}else if(infix[i]=='+'|| //如果掃描到'+','-','*','/'字符，需要和s1里的元素進行判斷infix[i]=='-'||infix[i]=='*'||infix[i]=='/'){if(top1==-1|| //判斷s1是否為空s1[top1]=='('|| //判斷輔助棧的棧頂元素是否為'('getPriority(infix[i])>getPriority(top1[top1])){ //判斷表達式里元素的優(yōu)先級是否大于s1元素的優(yōu)先級s1[++top1]=infix[i];++i;}else //如果不是，將輔助站的運算符放入結果棧里s2[++top2]==s1[top1--];}else if(infix[i]==')'){while(s1[top1]!='(')s2[++top2]=s1[top1--];--top1; //刪除s1里的'('++i;}}while(top1!=-1)s2[++top2]=s1[top1--]; //將s1中的元素都放入s2 }

?

二、中綴表達式轉前綴表達式

和中綴表達式轉后綴表達式類似，稍微有點區(qū)別。

方法一：括號法

比較簡單方便。

①按照運算符的優(yōu)先級，對所有的運算單位加括號。

于是變成：(((a+b)-(a*(((c+d)/e)-f)))+g)

②從最里面的括號開始，依次把運算符號移動到對應的括號的前面。

于是變成：+(-(+(ab)*(a-(/(+(cd)e)f)))g)

③最后，把括號都去掉

于是變成：+-+ab*a-/+cdefg

?

方法二：利用語法樹

略。

?

方法三：基于堆棧的算法

具體轉換方式:

從右到左進行遍歷。

1.遇到的是運算數，直接輸出。

2.遇到的是右括號')'，直接壓入堆棧(括號是最高優(yōu)先級，無需比較；入棧后優(yōu)先級降到最低，確保其他符號正常入棧)。

3.遇到的是左括號'('，意味著括號已結束。不斷彈出棧頂運算符并輸出，直到遇到右括號，這個右括號彈出但是不輸出。

4.遇到的是運算符('+'、'-'、'*'、'/')，有三種情況

①如果棧為空，直接入棧。

②如果棧頂元素是右括號')'，直接入棧。

③如果棧頂元素是運算符，則需要進行比較，

1-如果優(yōu)先級大于等于棧頂運算符，則壓入堆棧；

2-如果優(yōu)先級小于棧頂運算符，則將棧頂運算符彈出并輸出，然后比較新的棧頂運算符，直到優(yōu)先級大于等于棧頂運算符或者棧空，再將該運算符入棧

5.如果對象處理完畢，則按順序彈出并輸出棧中所有運算符

算法如下：

/* 中綴轉前綴 思路： 中綴存于一個字符數組infix[]里，有一個輔助棧s1，棧頂元素為top1，有一個結果棧s2，棧頂元素為top2。 從右向左掃描。i=len-1，當i>=0時， 1、碰到'0'-'9'，存入s2中。 2、碰到')'，存入s1中。 3、碰到'+'、'-'、'*'、'/'，如果棧為空，或者top1=')'，運算符的優(yōu)先級大于等于top1棧頂元素的優(yōu)先級，存入s1中；否則s2[++top2]=s1[top1--]。 4、碰到'('，將s1里截止到')'以前的元素全部放到s2中，并把')'丟掉 *///判斷運算符的優(yōu)先級 int getPriority(char op){if(op=='+'||op=='-')return 0; //+或-的優(yōu)先級比較低elsereturn 1; }void infixToPreFix(char infix[], int len, char s2[], int top2){char s1[maxSize]; int top1=-1;int i=len-1;while(i>=0){if('0'<=infix[i]&&infix[i]<='9'){s2[++top2]=infix[i];--i;}else if(infix[i]==')'){s1[++top1]=')';--i;}else if(infix[i]=='+'||infix[i]=='-'||infix[i]=='*'||infix[i]=='/'){if(top1==-1||s1[top1]==')'||getPriority(infix[i])>=getPriority(s1[top1])){s1[++top1]=infix[i];--i;}else s2[++top2]=s1[top1--];}if(infix[i]=='('){while(s1[top1]!=')')s2[++top2]=s1[top1--];--top1;--i;}}while(top1!=-1)s2[++top2]=s1[top1--]; }

總結

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

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