題目鏈接：here~~~~~~~

今天看了此題，感覺棧和隊列很好用，進一步深入了解

一個算術表達式，含有數字（為簡化處理，數字只有一位），運算符：+、-、*，以及括號，求表達式的值。

?給出的表達式是一般我們見到的中綴表達式，即運算符位于操作數之間。如果把中綴表達式轉化為后綴表達式，那么對后綴表達式求值將會很方便。

?后綴表達式特點：

　　1.操作符位于操作數之后；

　　2.沒有括號；

　　3.運算符沒有優先級。

?中綴表達式轉化為后綴表達式的步驟：

　　1.初始化一個空操作符棧和空結果字符串；

　　2.從前到后讀取中綴表達式的字符，如果是操作數，加到結果字符串后面；

　　3.如果是操作符，分兩種情況入棧：

　　　　a.如果待入棧操作符優先級大于棧頂操作符，直接入棧；

　　　　b.如果待入棧操作符優先級小于或等于棧頂操作符，棧頂操作符加到結果字符串后面；重復b過程直到遇到前括號‘(’或棧頂操作符優先級比待入棧操作符小，待入棧操作符入棧。

　　4.如果是前括號‘(’，直接入棧；

　　5.如果是后括號，將棧中操作符依次彈出，直至遇到一個前括號‘(’結束。前括號出棧。

? 最后結果字符串就是后綴表達式。

??后綴表達式求值的步驟：

　　1.初始化一個空操作數棧；

　　2.從前到后讀取后綴表達式字符。如果是操作數直接入棧。如果讀到一個操作符@，彈出棧頂元素a和新的棧頂元素b，執行b?@?a，將結果壓入棧中；

　　3.最后棧中只剩下一個元素，即表達式的值。

原鏈接 ：http://www.cnblogs.com/xiaofanke/archive/2013/05/29/3106391.html

經典的數據結構題，用棧跟隊列模擬。

中綴式變后綴式：

stack optr;用來存放運算符棧。隊列queue opnd用來存放后綴表達式。
從左到右掃描中綴表達式，是操作數就放進隊列 opnd的末尾。
如果是運算符的話，分為下面3種情況：
(1）如果是‘（’直接壓入optr棧。
(2）如果是‘）’，依次從optr棧彈出運算符加到隊列 opnd的末尾，直到遇到'（'；
(3) 如果是非括號，比較掃描到的運算符，和optr棧頂的運算符。如果掃描到的運算符優先級高于棧頂運算符
則，把運算符壓入棧。否則的話，就依次把棧中運算符彈出加到隊列 opnd的末尾，直到遇到優先級低于掃描
到的運算符或棧空，并且把掃描到的運算符壓入棧中。
就這樣依次掃描，知道結束為止。
如果掃描結束，棧中還有元素，則依次彈出加到隊列 opnd的末尾，就得到了后綴表達式。

原鏈接：點擊打開鏈接

#include<stdio.h> #include<string.h> #include<queue> #include<stack> using namespace std; queue<char> Q; stack<char> S; int priority(char s) {if(s=='+'||s=='-') return 1;if(s=='*'||s=='/') return 2;if(s=='(') return 0;return -1; } int main() {int n,i,l;char str[1100];S.push('#');scanf("%d",&n);while(n--){getchar();scanf("%s",str);l=strlen(str);for(i=0;i<l;i++){if(str[i]>='0'&&str[i]<='9') Q.push(str[i]);else if(str[i]=='(') S.push(str[i]);else if(str[i]==')'){while(S.top()!='('){Q.push(S.top());S.pop();}S.pop();}else{while(priority(S.top())>=priority(str[i])){Q.push(S.top());S.pop();}S.push(str[i]);}}while(S.top()!='#'){Q.push(S.top());S.pop();}while(!Q.empty()){printf("%c",Q.front());Q.pop();}printf("\n");} }

總結

以上是生活随笔為你收集整理的nyoj-257-郁闷的C小加（一 ）中缀式变后缀式的全部內容，希望文章能夠幫你解決所遇到的問題。

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