判斷條件都是我經過多次測驗出來的，每次都加上一點，也是耗時比較長的，在這里我并不想借鑒別人的代碼，因為我覺得一個演算法題每一次的測驗每一次的修改不僅僅時加強了我對這個演算法題的了解，更提高了我的耐心和心態，使我可以靜下心來去思考，不會因為長時間沒有看到成效而去放棄，我有時候感覺我真的很笨，但我覺得這并不是天生的，這跟我以前沉迷于游戲，只會去接受別人的東西有很大的關系，失去了獨立思考的能力，再好的工具如果不經常使用終將會壞掉，言歸正傳，來分享一下今天我做出來的這個演算法題吧！
#define MaxSize 500
typedef struct{
char data[MaxSize];
int top;
}list;
int js(char a);
void ints(list &q);
bool stacke(list q);
bool push(list &q,char x);
bool pop(list &q,char &x);
bool get_top(list q,char &x);
void siz();
void ints(list &q){
q.top=-1; //初始化堆疊頂指標
}
bool stacke(list q){
if(q.top==-1)return true; //判斷堆疊是否為空
else return false;
}
bool push(list &q,char x){ //堆疊滿報錯，入堆疊操作
if(q.top==MaxSize-1)return false;
q.data[++q.top]=x;
return true;
}
bool pop(list &q){ //堆疊空報錯，出堆疊操作
if(q.top==-1)return false;
q.top--;
return true;
}
bool get_top(list q,char &x){ //讀取堆疊頂元素，傳入變數記錄堆疊頂元素
if(q.top==-1)return false;
x=q.data[q.top];
return true;
}
既然要用堆疊來實作演算法，首先得做好準備作業，這里是堆疊的一些基本的操作，名字不是很規范，在資料結構試題中可以直接使用這些方法，名字盡量規范，并用注釋寫清楚每個方法的作用，這樣就算名字不規范，批卷老師也不會給你判錯的，
int js(char a){
if(a=='*'||a=='/') return 3;
else if(a=='+'||a=='-') return 2;
else if(a!='('&&a!=')')return 0;//如果是非運算子則回傳0
}
在這里我們使用一個輔助演算法用來比較優先級，數字可以任意定義，但要保證優先級高的運算子數字一定要比低的大，這樣方便我們后面進行比較，
void siz(){
char o,a[MaxSize];
list t;
cin>>a;
int l=strlen(a);//求字串陣列的長度
ints(t);
for(int i=0;i<l-1;i++){ //在這里減一是因為它需要一個#做結束識別符號，遍歷時我們并不需要
if(js(a[i])==0)cout<<a[i]; //如果掃描到不是運算子直接輸出
else if(stacke(t))push(t,a[i]); //如果堆疊為空則直接入堆疊
else if(a[i]=='(')push(t,a[i]);//如果掃描到左括號直接入堆疊
else if(a[i]==')'){
while(1){
get_top(t,o); //如果掃描到右括號，依次出堆疊輸出直到遇到左括號停止輸出，出堆疊左括號
if(o=='('){
pop(t);
break;
}
cout<<o;
pop(t);
}
}
else {
get_top(t,o);
if(o=='('){push(t,a[i]); //如果堆疊頂元素為左括號，直接入堆疊
}
else if(js(o)>=js(a[i])){ //如果掃描到的運算子優先級高于除’(‘外堆疊頂運算子時，直接入堆疊，否則從堆疊頂開始，依次彈出比當前運算子優先級高或相等的運算子，直到遇到比它優先級低的或左括號或堆疊空為止
while(1){
get_top(t,o);
cout<<o;
pop(t);
if(t.data[t.top]=='('||stacke(t)||js(o)<js(a[i])){
push(t,a[i]);
break;}}
}
else push(t,a[i]);} //否則直接入堆疊
} while(!stacke(t)){
get_top(t,o);
cout<<o; //依次彈出堆疊內元素，堆疊空為止
pop(t);}
}
int main(){
siz();
}
這是主要代碼的實作，每個判斷條件的作用已經注釋，相信也比較容易理解吧！
中綴運算式轉后綴運算式規則總結了一下大約是這么幾條：
- 如果掃描到非運算子型別，直接輸出，不需要入堆疊
- 如果掃描到左括號，也是直接入堆疊
- 如果掃描到右括號，右括號不進行入堆疊也不輸出，要對堆疊內元素依次出堆疊輸出，直到遇到左括號停止輸出，并將左括號出堆疊（如果有中括號和大括號，原理一樣，再每次匹配到更高級的右括號時，里面的低級括號是執行完畢的，只需要加適當的判斷條件即可）
- 剩下的肯定是加減乘除運算子了，在這里就用到了以上定義的輔助方法了，如果掃描到的運算子優先級高于除’(‘外堆疊頂運算子時，直接入堆疊，否則從堆疊頂開始，依次彈出比當前運算子優先級高或相等的運算子，直到遇到比它優先級低的或左括號或堆疊空為止，
- 最后把堆疊內元素全部彈出就好了，
這里進行了測驗，結果是沒有問題的，但因為時間有限，不能測驗更多的運算式，大家感興趣的話歡迎測驗，如果出現問題，歡迎來投稿評論，此代碼是我從頭到尾敲下來的，所以我并不敢保證沒有問題，但是我還是希望可以幫助大家去理解這個演算法，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/198770.html
標籤：其他
上一篇：DFS 深度優化搜索