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