C語言實現(xiàn)中綴表達式轉換為后綴表達式

更新時間：2020年04月26日 15:45:09 作者：蒼之羽

這篇文章主要為大家詳細介紹了C語言實現(xiàn)中綴表達式轉換為后綴表達式，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下

本文實例為大家分享了C語言實現(xiàn)中綴表達式轉后綴表達式的具體代碼，供大家參考，具體內(nèi)容如下

中綴表達式轉換為后綴表達式（思路）

1.創(chuàng)建棧

2.從左向右順序獲取中綴表達式

a.數(shù)字直接輸出
b.運算符

情況一：遇到左括號直接入棧，遇到右括號將棧中左括號之后入棧的運算符全部彈棧輸出，同時左括號出棧但是不輸出。

情況二：遇到乘號和除號直接入棧，直到遇到優(yōu)先級比它更低的運算符，依次彈棧。

情況三：遇到加號和減號，如果此時棧空，則直接入棧，否則，將棧中優(yōu)先級高的運算符依次彈棧（注意：加號和減號屬于同一個優(yōu)先級，所以也依次彈棧）直到?？栈騽t遇到左括號為止，停止彈棧。（因為左括號要匹配右括號時才彈出）。

情況四：獲取完后，將棧中剩余的運算符號依次彈棧輸出

例:比如將:2*(9+6/3-5)+4轉化為后綴表達式 2 9 6 3 / +5 - * 4 +

轉換算法代碼如下：

/*中綴轉后綴函數(shù)*/
void Change(SqStack *S,Elemtype str[])
{
 int i=0;
 Elemtype e;
 InitStack(S);
 while(str[i]!='\0')
 {
 while(isdigit(str[i])) 
 {/*過濾數(shù)字字符，直接輸出，直到下一位不是數(shù)字字符打印空格跳出循環(huán) */
 printf("%c",str[i++]);
 if(!isdigit(str[i]))
 {
 printf(" ");
 }
 }
 /*加減運算符優(yōu)先級最低，如果棧頂元素為空則直接入棧，否則將棧中存儲
 的運算符全部彈棧，如果遇到左括號則停止，將彈出的左括號從新壓棧，因為左
 括號要和又括號匹配時彈出，這個后面單獨討論。彈出后將優(yōu)先級低的運算符壓入棧中*/
 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);
 }
 }
 /*乘、除、左括號都是優(yōu)先級高的，直接壓棧*/
 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)

/*棧的動態(tài)分配存儲結構*/ 
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;
}

/*中綴轉后綴函數(shù)*/
void Change(SqStack *S,Elemtype str[])
{
 int i=0;
 Elemtype e;
 InitStack(S);
 while(str[i]!='\0')
 {
 while(isdigit(str[i])) 
 {/*過濾數(shù)字字符，直接輸出，直到下一位不是數(shù)字字符打印空格跳出循環(huán) */
 printf("%c",str[i++]);
 if(!isdigit(str[i]))
 {
 printf(" ");
 }
 }
 /*加減運算符優(yōu)先級最低，如果棧頂元素為空則直接入棧，否則將棧中存儲
 的運算符全部彈棧，如果遇到左括號則停止，將彈出的左括號從新壓棧，因為左
 括號要和又括號匹配時彈出，這個后面單獨討論。彈出后將優(yōu)先級低的運算符壓入棧中*/
 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);
 }
 }
 /*乘、除、左括號都是優(yōu)先級高的，直接壓棧*/
 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;
}

運行效果截圖如下：