一、主要思路
由于操作符具有优先级，因此我们应该先设置操作符的优先级
操作符的优先级
操作符 # ( + - * /
优先级 -1 0 1 1 2 2
主要的方法为：
（1）初始化一个顺序栈
（2）设表达式的结束符为“#”，预设操作符栈的栈底为“#”
（3）若当前字符是操作数，则直接放入后缀式
（4）若当前字符是操作符且优先级大于栈顶操作符，则入栈，否则退出栈顶操作符放到后缀式，继续下次判断，直到可以入栈
（5）若当前字符是“#”，则自栈顶至栈底依次将栈中所有操作符发送给后缀式
（6）遇到“（”直接入栈
（7）遇到“）” ，从栈顶开始判断，并放入后缀式，一直到栈顶元素为“（”时，出栈“（”
二、具体分析
接下来我们通过一个例子来分析后缀表达式的生成过程
将 23-(2-4)*2+36/(20-14)# 转换为后缀表达式的过程：
序号 读取字符 类型 操作 栈内变化 输出的后缀式
0 初始化顺序栈，置栈底 # #
1 2 操作数 # 2
2 3 操作数 # 23
3 - 操作符 - 优先级大于 # ，入栈 # - 23
4 ( 操作符 （ 直接入栈 # - ( 23
5 2 操作数 # - ( 23 2
6 - 操作符 - 优先级大于 ( ，入栈 # - ( - 23 2
7 4 操作数 # - ( - 23 2 4
8 ) 操作符 先出栈再判断，直到遇到 ( # - ( 23 2 4 -
9 遇到 ( 不用放到后缀式 # - 23 2 4 -
10 操作符 优先级大于 - ，入栈 # - * 23 2 4 -
11 2 操作数 # - * 23 2 4 - 2
12 + 操作符 + 优先级小于 ，出栈 # - 23 2 4 - 2 *
13 + 优先级等于 - 优先级，出栈 # 23 2 4 - 2 * -
14 + 优先级大于 #，入栈 # + 23 2 4 - 2 * -
15 3 操作数 # + 23 2 4 - 2 * - 3
16 6 操作数 # + 23 2 4 -2 * - 36
17 / 操作符 / 优先级大于+，入栈 # + / 23 2 4 -2 * - 36
18 ( 操作符 ( 直接入栈 # + / ( 23 2 4 -2 * - 36
19 2 操作数 # + / ( 23 2 4 -2 * - 36 2
20 0 操作数 # + / ( 23 2 4 -2 * - 36 20
21 - 操作符 - 优先级大于 ( ，入栈 # + / ( - 23 2 4 -2 * - 36 20
22 1 操作数 # + / ( - 23 2 4 -2 * - 36 20 1
23 4 操作数 # + / ( - 23 2 4 -2 * - 36 20 14
24 ) 操作符 先出栈栈顶元素，再判断 # + / ( 23 2 4 -2 * - 36 20 14 -
25 遇到 ( 出栈，不需要放到后缀式 # + / 23 2 4 -2 * - 36 20 14 -
26 # 结束符 依次出栈发送给后缀式 # + 23 2 4 -2 * - 36 20 14 - /
27 # 23 2 4 -2 * - 36 20 14 - / +
这个过程很复杂，其中包括了遇到连续的操作数时，需要将他们放到一起的过程
而这个过程在表格里没有体现，我们需要用代码将他体现出来
例如两位数23，你读取的时候分别读取2，3，但是放入后缀式的时候你需要将他们放到一起，使他们保持自己是一个整体，这就需要动一下小脑筋了
三、核心算法
void Change_Char(char *s1,char *s2){
Stack s;
int i=0,e;
Push_Stack(&s,'#'); //初始化栈，置栈底为“#”
while(*s1!='\0'){ //当遇到空格时结束循环
if(*s1>='0'&&*s1<='9'){ //如果遇到操作数
while(*s1>='0'&&*s1<='9'){ //这个方法将连续的操作数放到一起
s2[i++]=*s1;
s1++;
}
s2[i++]=' '; //打印空格用于分隔
s1--;
}else{ //当遇到操作符时
Get_Top(&s,&e); //获取栈顶元素
if((f(*s1)>f(e)&&*s1!=')')||*s1=='('){ //如果该操作符优先级大于栈顶元素且不等
Push_Stack(&s,*s1); //于“）”或者是“（”时，入栈
}else if(*s1==')'){ //当操作符时“）”时
Pop_Stack(&s,&e); //先出栈
while(e!='('){ //再判断，如果不是“（”，放到后缀式
s2[i++]=e;
s2[i++]=' ';
Pop_Stack(&s,&e); //再次执行出栈，继续判断
}
}else{
while(f(*s1)<=f(e)){ //当操作符优先级小于栈顶元素时
Pop_Stack(&s,&e); //出栈
s2[i++]=e; //放到后缀式
s2[i++]=' ';
Get_Top(&s,&e); //重新获取栈顶元素继续执行判断
}
Push_Stack(&s,*s1); //最后当前操作符优先级大于栈顶操作符时，入栈
}
}
s1++; //指针指向下一个字符，继续判断
}
while(!Empty_Stack(&s)){ //当栈非空时，将栈中操作符依次出栈放入后缀式
Pop_Stack(&s,&e);
s2[i++]=e;
}
int k=0;
while(1){ //打印后缀式
if(s2[k]=='#') break;
printf("%c",s2[k++]);
}
}四、完整代码
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define SIZE 10
#define INCREAM 10
typedef struct Stack{
int *base;
int *top;
int size;
}Stack,*PStack;
int Init_Stack(PStack S){
S->base=(int *)malloc(sizeof(int)*SIZE);
S->top=S->base;
S->size=SIZE;
return 1;
}
int Push_Stack(PStack S,int e){
if(S->top-S->base>=S->size){
S->base=(int *)realloc(S->base,(S->size+INCREAM)*sizeof(int));
S->top=S->base+S->size;
S->size+=INCREAM;
}
*S->top=e;
S->top++;
return 1;
}
int Pop_Stack(PStack S,int *e){
if(S->base==S->top){
return 0;
}
--S->top;
*e=*S->top;
return 1;
}
int Get_Top(PStack S,int *e){
if(S->base==S->top) return 0;
*e=*(S->top-1);
return 1;
}
int Empty_Stack(PStack S){
if(S->base==S->top) return 1;
else return 0;
}
int f(char s){
if(s=='#') return -1;
else if(s=='('||s==')') return 0;
else if(s=='+'||s=='-') return 1;
else if(s=='*'||s=='/') return 2;
}
void Change_Char(char *s1,char *s2){
Stack s;
int i=0,e;
Push_Stack(&s,'#');
while(*s1!='\0'){
if(*s1>='0'&&*s1<='9'){
while(*s1>='0'&&*s1<='9'){
s2[i++]=*s1;
s1++;
}
s2[i++]=' ';
s1--;
}else{
Get_Top(&s,&e);
if((f(*s1)>f(e)&&*s1!=')')||*s1=='('){
Push_Stack(&s,*s1);
}else if(*s1==')'){
Pop_Stack(&s,&e);
while(e!='('){
s2[i++]=e;
s2[i++]=' ';
Pop_Stack(&s,&e);
}
}else{
while(f(*s1)<=f(e)){
Pop_Stack(&s,&e);
s2[i++]=e;
s2[i++]=' ';
Get_Top(&s,&e);
}
Push_Stack(&s,*s1);
}
}
s1++;
}
while(!Empty_Stack(&s)){
Pop_Stack(&s,&e);
s2[i++]=e;
}
int k=0;
while(1){
if(s2[k]=='#') break;
printf("%c",s2[k++]);
}
}
int main(){
char s1[100],s2[100];
scanf("%s",s1);
Change_Char(s1,s2);
return 0;
}五、运行结果
