写点什么

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

作者:向阳逐梦
  • 2023-06-19
    四川
  • 本文字数:2100 字

    阅读完需:约 7 分钟

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<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]!='\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;}
复制代码

运行效果截图如下:


发布于: 刚刚阅读数: 4
用户头像

向阳逐梦

关注

人生享受编程,编程造就人生! 2022-06-01 加入

某公司芯片测试工程师,嵌入式开发工程师,InfoQ签约作者,阿里云星级博主,华为云·云享专家。座右铭:向着太阳,追逐梦想!

评论

发布
暂无评论
C语言编程—中缀表达式转换为后缀表达式_C语言_向阳逐梦_InfoQ写作社区