王道考研数据机构：中缀表达式转为后缀表达式

实现方法： 

        初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素，直到末尾。可能遇到三种情况:

1. 遇到操作数。直接加入后缀表达式
2. 遇到界限符。遇到“(”直接入栈;遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。注意:“(”不加入后缀表达式。
3. 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式,若磁到“(”或栈空则停止。之后再把当前运算符入栈。

按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef struct Stack{char data[MaxSize];int top;
}Stack;
void initStack(Stack* &S){S = (Stack *)malloc(sizeof(Stack));S->top=-1;
}
bool push(Stack * &S, char e){if(S->top == MaxSize - 1)return false;S->data[++S->top] = e;printf("元素%c进栈\n",e);return true;
}
bool pop(Stack * &S,char &e){if(S->top==-1)return false;e = S->data[S->top--];printf("元素%c出栈\n",e);return true;
}
bool getTop(Stack * &S, char &e){if(S->top==-1)return false;e = S->data[S->top];return true;
}
bool emptyStack(Stack * &S){return S->top==-1;
}
int getSymbolPriority(char c){if(c=='+'||c=='-')return 1;elsereturn 2;
}
int main()
{Stack *s;char str[MaxSize];//中缀表达式 char houZhui[MaxSize];//后缀表达式 int index=0;scanf("%s",str);initStack(s);for(int i=0;str[i]!='\0';i++){printf("第%d次操作\n",i+1); if(str[i]=='+' || str[i]=='-' || str[i]=='*' || str[i]=='/'){int v1 = getSymbolPriority(str[i]);while(!emptyStack(s)){char e;getTop(s,e);if(e=='(')break;int v2 = getSymbolPriority(e);if(v2>=v1){pop(s,e);houZhui[index++]=e;}elsebreak;}push(s,str[i]);}else if(str[i]=='(' || str[i]==')'){if(str[i]=='(')push(s,str[i]);elsewhile(!emptyStack(s)){char e;getTop(s,e);if(e=='('){pop(s,e);break;c}else{pop(s,e);houZhui[index++]=e;}	}}else{houZhui[index++]=str[i];}printf("此时后缀表达式元素为:");for(int j=0;j<index;j++)printf("%c",houZhui[j]);printf("\n\n\n"); }printf("栈中剩余元素依次弹出:\n");while(!emptyStack(s)){char e;pop(s,e);houZhui[index++]=e;}printf("\n最终结果为:\n");for(int i=0;i<index;i++)printf("%c",houZhui[i]);return 0;
} 
//A+B-C*D/E+F
//A+B*(C-D)-E/F

运行结果：

 输入：

A+B-C*D/E+F

输出：
第1次操作
此时后缀表达式元素为:A

第2次操作
元素+进栈
此时后缀表达式元素为:A

第3次操作
此时后缀表达式元素为:AB

第4次操作
元素+出栈
元素-进栈
此时后缀表达式元素为:AB+

第5次操作
此时后缀表达式元素为:AB+C

第6次操作
元素*进栈
此时后缀表达式元素为:AB+C

第7次操作
此时后缀表达式元素为:AB+CD

第8次操作
元素*出栈
元素/进栈
此时后缀表达式元素为:AB+CD*

第9次操作
此时后缀表达式元素为:AB+CD*E

第10次操作
元素/出栈
元素-出栈
元素+进栈
此时后缀表达式元素为:AB+CD*E/-

第11次操作
此时后缀表达式元素为:AB+CD*E/-F

栈中剩余元素依次弹出:
元素+出栈

A+B-C*D/E+F
转为后缀表达式最终结果为:
AB+CD*E/-F+

 输入：

A+B*(C-D)-E/F

输出

第1次操作
此时后缀表达式元素为:A

第2次操作
元素+进栈
此时后缀表达式元素为:A

第3次操作
此时后缀表达式元素为:AB

第4次操作
元素*进栈
此时后缀表达式元素为:AB

第5次操作
元素(进栈
此时后缀表达式元素为:AB

第6次操作
此时后缀表达式元素为:ABC

第7次操作
元素-进栈
此时后缀表达式元素为:ABC

第8次操作
此时后缀表达式元素为:ABCD

第9次操作
元素-出栈
元素(出栈
此时后缀表达式元素为:ABCD-

第10次操作
元素*出栈
元素+出栈
元素-进栈
此时后缀表达式元素为:ABCD-*+

第11次操作
此时后缀表达式元素为:ABCD-*+E

第12次操作
元素/进栈
此时后缀表达式元素为:ABCD-*+E

第13次操作
此时后缀表达式元素为:ABCD-*+EF

栈中剩余元素依次弹出:
元素/出栈
元素-出栈

A+B*(C-D)-E/F
转为后缀表达式最终结果为:
ABCD-*+EF/-