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

完整代码如下：

#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]!='')
 {
 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;
}

运行效果截图如下：

如何实现将中缀表达式转换成后缀表达式后计算值

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持考高分网。