C++利用棧實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式

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

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

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

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

請(qǐng)用棧的特性編寫一個(gè)程序，使得程序輸出后綴表達(dá)式

分析如下：

STEP1：

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

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

STEP2：

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

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

STEP3：

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

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

STEP4：

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

緊接著是符號(hào)“*”，直接入棧

STEP5：

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

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

最后把剛剛的那個(gè)加號(hào)入棧，操作如下圖：

STEP6：

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

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

STEP7：

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

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

總結(jié)規(guī)則：

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

代碼實(shí)現(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("請(qǐng)輸入中綴表達(dá)式，以#作為結(jié)束標(biāo)志：");
 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出錯(cuò)：輸入格式錯(cuò)誤！\n");
   return -1;
  }
 
  scanf("%c", &c);
 }
 
 while( StackLen(s) )
 {
  Pop(&s, &e);
  printf("%c ", e);
 }
 
 return 0;
}

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: