C语言编程—中缀表达式转换为后缀表达式

简介: 1.创建栈2.从左向右顺序获取中缀表达式a.数字直接输出b.运算符情况一:遇到左括号直接入栈,遇到右括号将栈中左括号之后入栈的运算符全部弹栈输出,同时左括号出栈但是不输出。情况二:遇到乘号和除号直接入栈,直到遇到优先级比它更低的运算符,依次弹栈。情况三:遇到加号和减号,如果此时栈空,则直接入栈,否则,将栈中优先级高的运算符依次弹栈(注意:加号和减号属于同一个优先级,所以也依次弹栈)直到栈空或则遇到左括号为止,停止弹栈。(因为左括号要匹配右括号时才弹出)。情况四:获取完后,将栈中剩余的运算符号依次弹栈输出例:将:2*(9+6/3-5)+4转化为后缀表达式 2 9

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;
}

运行效果截图如下:

目录
相关文章
|
1月前
|
监控 网络协议 API
C语言系统编程
C语言系统编程
|
1月前
|
Linux C语言 开发者
Linux系统下C语言的高阶编程
Linux系统下C语言的高阶编程
15 0
|
1月前
|
存储 C语言 索引
掌握多维数组,让你的C语言编程技能暴涨!
掌握多维数组,让你的C语言编程技能暴涨!
|
1月前
|
存储 编译器 程序员
汽车电子行业的 C 语言编程标准
汽车电子行业的 C 语言编程标准
55 0
汽车电子行业的 C 语言编程标准
|
1月前
|
存储 人工智能 安全
C语言:选择+编程(每日一练Day15)
C语言:选择+编程(每日一练Day15)
51 2
|
19天前
|
Linux 测试技术 C语言
【Linux】应用编程之C语言文件操作
【Linux】应用编程之C语言文件操作
|
1月前
|
自然语言处理 算法 搜索推荐
C语言的编程
C语言的编程
9 1
|
1月前
|
存储 C语言 索引
遍历一维数组C语言,掌握这个技能,你的编程能力直线上升!
遍历一维数组C语言,掌握这个技能,你的编程能力直线上升!
|
1月前
|
存储 C语言
3分钟搞定阶乘!C语言编程新手也能轻松学会的秘籍
3分钟搞定阶乘!C语言编程新手也能轻松学会的秘籍
|
1月前
|
存储 人工智能 C语言
C语言:选择+编程(每日一练Day16)
C语言:选择+编程(每日一练Day16)
33 3