王道考研数据机构：中缀表达式转为后缀表达式
实现方法：
初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素，直到末尾。可能遇到三种情况:
- 遇到操作数。直接加入后缀表达式
- 遇到界限符。遇到“(”直接入栈;遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。注意:“(”不加入后缀表达式。
- 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式,若磁到“(”或栈空则停止。之后再把当前运算符入栈。
按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。
#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/-