C++利用棧實現(xiàn)中綴表達式轉后綴表達式

更新時間：2020年04月26日 14:41:09 作者：Halosec_Wei

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

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

題目：現(xiàn)有中綴表達式如：1+(2-3)*4+10/5

請用棧的特性編寫一個程序，使得程序輸出后綴表達式

分析如下：

STEP1：

1+(2-3)*4+10/5

首先遇到第一個輸入是數(shù)字1，數(shù)字在后綴表達式中都是直接輸出，接著是符號“+”，入棧：

STEP2：

1+(2-3)*4+10/5

第三個字符是“(”，依然是符號，入棧，接著是數(shù)字2，輸出，然后是符號“-”，入棧：

STEP3：

1+(2-3)*4+10/5

接下來是數(shù)字3，輸出，緊跟著是“)”，此時，我們需要去匹配棧里的“(”，然后再匹配前將棧頂數(shù)據(jù)依次出棧（這就好比括號里優(yōu)先執(zhí)行的道理）：

STEP4：

1+(2-3)*4+10/5

緊接著是符號“*”，直接入棧

STEP5：

1+(2-3)*4+10/5

遇到數(shù)字4，輸出，之后是符號“+”，此時棧頂元素是符號“*”，按照先乘除后加減原理，此時棧頂?shù)某颂杻?yōu)先級比即將入棧的加好要大，所以出棧。
棧中第二個元素是加號，按理來說大家平起平坐，但是按照先來后到的原則，棧里的加號呆得太久了，也要出棧透透氣。（同理如果棧里還有其他操作符，也是出棧）

最后把剛剛的那個加號入棧，操作如下圖：

STEP6：

1+(2-3)*4+10/5

緊接著數(shù)字10，輸出，最后是符號“/”，進棧：

STEP7：

1+(2-3)*4+10/5

最后一個數(shù)字5，輸出，所有的輸入處理完畢，但是棧中仍然有數(shù)據(jù)，所以將棧中符號依次出棧。

總結規(guī)則：

從左到右遍歷中綴表達式的每個數(shù)字和符號，若是數(shù)字則直接輸出，若是符號，則判斷其與棧頂符號的優(yōu)先級，是右括號或者優(yōu)先級低于棧頂符號，則棧頂元素依次出棧并輸出，直到遇到左括號或棧空才將低優(yōu)先級的那個符號入棧

代碼實現(xiàn)如下：

#include <stdio.h>
#include <stdlib.h>
 
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
 
typedef char ElemType;
typedef struct
{
 ElemType *base;
 ElemType *top;
 int stackSize;
}sqStack;
 
InitStack(sqStack *s)
{
 s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
 if( !s->base )
  exit(0);
 
 s->top = s->base;
 s->stackSize = STACK_INIT_SIZE;
}
 
Push(sqStack *s, ElemType e)
{
 // 棧滿，追加空間，魚油必須懂！
 if( s->top - s->base >= s->stackSize )
 {
  s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
  if( !s->base )
   exit(0);
 
  s->top = s->base + s->stackSize;
  s->stackSize = s->stackSize + STACKINCREMENT;
 }
 
 *(s->top) = e;  // 存放數(shù)據(jù)
 s->top++;
}
 
Pop(sqStack *s, ElemType *e)
{
 if( s->top == s->base )
  return;
 
 *e = *--(s->top); // 將棧頂元素彈出并修改棧頂指針
}
 
int StackLen(sqStack s)
{
 return (s.top - s.base);
}
 
int main()
{
 sqStack s;
 char c, e;
 
 InitStack( &s );
 
 printf("請輸入中綴表達式，以#作為結束標志：");
 scanf("%c", &c);
 
 while( c != '#' )
 {
  while( c>='0' && c<='9' )
  {
   printf("%c", c);
   scanf("%c", &c);
   if( c<'0' || c>'9' )
   {
    printf(" ");
   }
  }
 
  if( ')' == c )
  {
   Pop(&s, &e);
   while( '(' != e )
   {
    printf("%c ", e);
    Pop(&s, &e);
   }
  }
  else if( '+'==c || '-'==c )
  {
   if( !StackLen(s) )
   {
    Push(&s, c);
   }
   else
   {
    do
    {
     Pop(&s, &e);
     if( '(' == e )
     {
      Push(&s, e);
     }
     else
     {
      printf("%c ", e);
     }
    }while( StackLen(s) && '('!=e );
    Push(&s, c);
   }
  }
  else if( '*'==c || '/'==c || '('==c )
  {
   Push(&s, c);
  }
  else if( '#'== c )
  {
   break;
  }
  else
  {
   printf("\n出錯：輸入格式錯誤！\n");
   return -1;
  }
 
  scanf("%c", &c);
 }
 
 while( StackLen(s) )
 {
  Pop(&s, &e);
  printf("%c ", e);
 }
 
 return 0;
}

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: