C语言实现中缀表达式转换为后缀表达式

175 阅读 0 评论 116 点赞

我是靠谱客的博主踏实路人，这篇文章主要介绍C语言实现中缀表达式转换为后缀表达式，现在分享给大家，希望可以做个参考。

本文实例为大家分享了C语言实现中缀表达式转后缀表达式的具体代码，供大家参考，具体内容如下

中缀表达式转换为后缀表达式（思路）

1.创建栈

2.从左向右顺序获取中缀表达式

a.数字直接输出
b.运算符

情况一：遇到左括号直接入栈，遇到右括号将栈中左括号之后入栈的运算符全部弹栈输出，同时左括号出栈但是不输出。

情况二：遇到乘号和除号直接入栈，直到遇到优先级比它更低的运算符，依次弹栈。

情况三：遇到加号和减号，如果此时栈空，则直接入栈，否则，将栈中优先级高的运算符依次弹栈（注意：加号和减号属于同一个优先级，所以也依次弹栈）直到栈空或则遇到左括号为止，停止弹栈。（因为左括号要匹配右括号时才弹出）。

情况四：获取完后，将栈中剩余的运算符号依次弹栈输出

例:比如将:2*(9+6/3-5)+4转化为后缀表达式 2 9 6 3 / +5 - * 4 +

转换算法代码如下：

复制代码

/*中缀转后缀函数*/
void Change(SqStack *S,Elemtype str[])
{
 int i=0;
 Elemtype e;
 InitStack(S);
 while(str[i]!='')
 {
 while(isdigit(str[i])) 
 {/*过滤数字字符，直接输出，直到下一位不是数字字符打印空格跳出循环 */
 printf("%c",str[i++]);
 if(!isdigit(str[i]))
 {
 printf(" ");
 }
 }
 /*加减运算符优先级最低，如果栈顶元素为空则直接入栈，否则将栈中存储
 的运算符全部弹栈，如果遇到左括号则停止，将弹出的左括号从新压栈，因为左
 括号要和又括号匹配时弹出，这个后面单独讨论。弹出后将优先级低的运算符压入栈中*/
 if(str[i]=='+'||str[i]=='-')
 {
 if(!StackLength(S))
 {
 PushStack(S,str[i]);
 }
 else
 {
 do
 {
  PopStack(S,&e);
  if(e=='(')
  {
  PushStack(S,e);
  }
  else
  {
  printf("%c ",e);
  }
 }while( StackLength(S) && e != '(' );
 
 PushStack(S,str[i]);
 }
 }
 /*当遇到右括号是，把括号里剩余的运算符弹出，直到匹配到左括号为止
 左括号只弹出不打印（右括号也不压栈）*/
 else if(str[i]==')')
 {
 PopStack(S,&e);
 while(e!='(')
 {
 printf("%c ",e);
 PopStack(S,&e);
 }
 }
 /*乘、除、左括号都是优先级高的，直接压栈*/
 else if(str[i]=='*'||str[i]=='/'||str[i]=='(')
 {
 PushStack(S,str[i]);
 }
 
 else if(str[i]=='')
 {
 break;
 }
 
 else
 {
 printf("n输入格式错误！n");
 return ;
 }
 i++;
 }
 /*最后把栈中剩余的运算符依次弹栈打印*/
 while(StackLength(S))
 {
 PopStack(S,&e);
 printf("%c ",e);
 }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/*中缀转后缀函数*/
void Change(SqStack *S,Elemtype str[])
{
 int i=0;
 Elemtype e;
 InitStack(S);
 while(str[i]!='')
 {
 while(isdigit(str[i])) 
 {/*过滤数字字符，直接输出，直到下一位不是数字字符打印空格跳出循环 */
 printf("%c",str[i++]);
 if(!isdigit(str[i]))
 {
 printf(" ");
 }
 }
 /*加减运算符优先级最低，如果栈顶元素为空则直接入栈，否则将栈中存储
 的运算符全部弹栈，如果遇到左括号则停止，将弹出的左括号从新压栈，因为左
 括号要和又括号匹配时弹出，这个后面单独讨论。弹出后将优先级低的运算符压入栈中*/
 if(str[i]=='+'||str[i]=='-')
 {
 if(!StackLength(S))
 {
 PushStack(S,str[i]);
 }
 else
 {
 do
 {
  PopStack(S,&e);
  if(e=='(')
  {
  PushStack(S,e);
  }
  else
  {
  printf("%c ",e);
  }
 }while( StackLength(S) && e != '(' );
 
 PushStack(S,str[i]);
 }
 }
 /*当遇到右括号是，把括号里剩余的运算符弹出，直到匹配到左括号为止
 左括号只弹出不打印（右括号也不压栈）*/
 else if(str[i]==')')
 {
 PopStack(S,&e);
 while(e!='(')
 {
 printf("%c ",e);
 PopStack(S,&e);
 }
 }
 /*乘、除、左括号都是优先级高的，直接压栈*/
 else if(str[i]=='*'||str[i]=='/'||str[i]=='(')
 {
 PushStack(S,str[i]);
 }
 
 else if(str[i]=='')
 {
 break;
 }
 
 else
 {
 printf("n输入格式错误！n");
 return ;
 }
 i++;
 }
 /*最后把栈中剩余的运算符依次弹栈打印*/
 while(StackLength(S))
 {
 PopStack(S,&e);
 printf("%c ",e);
 }
}

完整代码如下：

复制代码

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h> 
#include<assert.h>

#define INITSIZE 20
#define INCREMENT 10
#define MAXBUFFER 20
#define LEN sizeof(Elemtype)

/*栈的动态分配存储结构*/ 
typedef char Elemtype;
typedef struct{
 Elemtype *base;
 Elemtype *top;
 int StackSize;
}SqStack;

/*初始化栈*/
void InitStack(SqStack *S)
{
 S->base=(Elemtype*)malloc(LEN*INITSIZE);
 assert(S->base !=NULL);
 S->top=S->base;
 S->StackSize=INITSIZE;
}

/*压栈操作*/ 
void PushStack(SqStack *S,Elemtype c)
{
 if(S->top - S->base >= S->StackSize)
 {
 S->base=(Elemtype*)realloc(S->base,LEN*(S->StackSize+INCREMENT));
 assert(S->base !=NULL);
 S->top =S->base+S->StackSize;
 S->StackSize+=INCREMENT;
 }
 *S->top++ = c;
}
/*求栈长*/
int StackLength(SqStack *S)
{
 return (S->top - S->base);
}
/*弹栈操作*/
int PopStack(SqStack *S,Elemtype *c)
{
 if(!StackLength(S))
 {
 return 0;
 }
 *c=*--S->top;
 return 1;
}

int main()
{
 Elemtype str[MAXBUFFER];
 SqStack S;
 gets(str);
 Change(&S,str);
 return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h> 
#include<assert.h>

#define INITSIZE 20
#define INCREMENT 10
#define MAXBUFFER 20
#define LEN sizeof(Elemtype)

/*栈的动态分配存储结构*/ 
typedef char Elemtype;
typedef struct{
 Elemtype *base;
 Elemtype *top;
 int StackSize;
}SqStack;

/*初始化栈*/
void InitStack(SqStack *S)
{
 S->base=(Elemtype*)malloc(LEN*INITSIZE);
 assert(S->base !=NULL);
 S->top=S->base;
 S->StackSize=INITSIZE;
}

/*压栈操作*/ 
void PushStack(SqStack *S,Elemtype c)
{
 if(S->top - S->base >= S->StackSize)
 {
 S->base=(Elemtype*)realloc(S->base,LEN*(S->StackSize+INCREMENT));
 assert(S->base !=NULL);
 S->top =S->base+S->StackSize;
 S->StackSize+=INCREMENT;
 }
 *S->top++ = c;
}
/*求栈长*/
int StackLength(SqStack *S)
{
 return (S->top - S->base);
}
/*弹栈操作*/
int PopStack(SqStack *S,Elemtype *c)
{
 if(!StackLength(S))
 {
 return 0;
 }
 *c=*--S->top;
 return 1;
}

/*中缀转后缀函数*/
void Change(SqStack *S,Elemtype str[])
{
 int i=0;
 Elemtype e;
 InitStack(S);
 while(str[i]!='')
 {
 while(isdigit(str[i])) 
 {/*过滤数字字符，直接输出，直到下一位不是数字字符打印空格跳出循环 */
 printf("%c",str[i++]);
 if(!isdigit(str[i]))
 {
 printf(" ");
 }
 }
 /*加减运算符优先级最低，如果栈顶元素为空则直接入栈，否则将栈中存储
 的运算符全部弹栈，如果遇到左括号则停止，将弹出的左括号从新压栈，因为左
 括号要和又括号匹配时弹出，这个后面单独讨论。弹出后将优先级低的运算符压入栈中*/
 if(str[i]=='+'||str[i]=='-')
 {
 if(!StackLength(S))
 {
 PushStack(S,str[i]);
 }
 else
 {
 do
 {
  PopStack(S,&e);
  if(e=='(')
  {
  PushStack(S,e);
  }
  else
  {
  printf("%c ",e);
  }
 }while( StackLength(S) && e != '(' );
 
 PushStack(S,str[i]);
 }
 }
 /*当遇到右括号是，把括号里剩余的运算符弹出，直到匹配到左括号为止
 左括号只弹出不打印（右括号也不压栈）*/
 else if(str[i]==')')
 {
 PopStack(S,&e);
 while(e!='(')
 {
 printf("%c ",e);
 PopStack(S,&e);
 }
 }
 /*乘、除、左括号都是优先级高的，直接压栈*/
 else if(str[i]=='*'||str[i]=='/'||str[i]=='(')
 {
 PushStack(S,str[i]);
 }
 
 else if(str[i]=='')
 {
 break;
 }
 
 else
 {
 printf("n输入格式错误！n");
 return ;
 }
 i++;
 }
 /*最后把栈中剩余的运算符依次弹栈打印*/
 while(StackLength(S))
 {
 PopStack(S,&e);
 printf("%c ",e);
 }
}

int main()
{
 Elemtype str[MAXBUFFER];
 SqStack S;
 gets(str);
 Change(&S,str);
 return 0;
}