C语言实现中缀表达式转换为后缀表达式
- 格式：pdf
- 大小：105.08 KB
- 文档页数：4
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]!='\0')
{
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]=='\0')
{
break;
}
else
{
printf("\n输⼊格式错误！\n");
return ;
}
i++;
}
/*最后把栈中剩余的运算符依次弹栈打印*/
while(StackLength(S))
{
PopStack(S,&e);
printf("%c ",e);
}
}
完整代码如下：
#include
#include
#include
#include
#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]!='\0')
{
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]=='\0')
{
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;
}运⾏效果截图如下：
以上就是本⽂的全部内容，希望对⼤家的学习有所帮助，也希望⼤家多多⽀持。
