各位看官們，大家好，前幾回中咱們說了堆棧的原理，并且舉了實際的例子進行解說，這一回咱們說的例 子是：表達式求值。表達式求值和上一回中說的括號匹配一樣，都使用了堆棧的原理，大家可以從例子中 看出來，所以我們把它們放在一起。閑話休提，言歸正轉(zhuǎn)。讓我們一起talk C栗子吧！

看官們，我們在這里說的表達式為包含加，減，乘除的四則運算表達式。例如：1+23-4/5就是一個四則運 算表達式。這個表達式中，運算符在數(shù)字中間，所以我們叫它中綴表達式，這也是符合我們思維的一種表 現(xiàn)形式，不過，計算機就不理解中綴表達式了，因為它沒有辦法像我們一樣先進行乘除運算，然后再進行 加減運算，所以我們需要把中綴表達式轉(zhuǎn)換成計算機能理解的后綴表達式?！笆裁词呛缶Y表達式”，這時候 臺下有看官在提問了，看官莫急，所謂的后綴表達式就是運算符在數(shù)字后面。例如：" 1+23-6/3 "這個中綴 表達式可以為" 123*+63/- "這種后綴表達式.

表達式求值有兩個大的步驟：

• 1.中綴表達式轉(zhuǎn)換為后綴表達式。
• 2.對后綴表達式進行求值。

這兩個大的步驟中還有一些小的步驟，接下來我們詳細說說這些小步驟。在說之前，我首先說明一個概念： 優(yōu)先級。優(yōu)先級代表著先后順序，舉一個日常為生活中的例子：排隊買東西的時候，排在隊列前面的人， 比排在隊列后面人具有優(yōu)先買東西的權(quán)利，我們就可以說：排在隊列前面的人買東西的優(yōu)先級高。優(yōu)先級 在表達式運算過程中體現(xiàn)為：乘法和除法的優(yōu)先級比加法和減法的優(yōu)先級高。也就是我們通常說的先乘除 后加減，這個內(nèi)容我就不多說了，大家在小學(xué)數(shù)學(xué)中都學(xué)過。我們在表達式求值過程中把中綴表達式轉(zhuǎn)換 為后綴表達式也與優(yōu)先級有關(guān)，因為后綴表達式可以去掉運算符的優(yōu)先級。沒有優(yōu)先級了，計算機就能理 解后綴表達式并對其進行相關(guān)的運算。

中綴表達式轉(zhuǎn)換為后綴表達式的步驟如下：

• 1.從頭到尾依次遍歷中綴表達式，每次從表達式中讀取一個字符；
• 2.判斷步驟1中讀取的字符，如果是數(shù)字則保存到數(shù)組a中，如果是+*等運算符，請看下一個步驟；
• 3.對存放運算符的棧進行出棧操作，把步驟的2中的運算符和剛才出棧的運算符進行優(yōu)先級比較；
• 4.如果步驟2中的運算符優(yōu)先級高，那么把參與比較的這兩個運算符都入棧。否則看下一步；
• 5.如果步驟2中的運算符優(yōu)先級低，那么讓棧中的運算符繼續(xù)出棧，并且把出棧的運算符存放數(shù)組a中；
• 6.重復(fù)步驟4和步驟5,直到出棧運算符的優(yōu)先級比步驟2中運算符的優(yōu)先級高為止；
• 7.重復(fù)步驟1到步驟6.直到遍歷完中綴表達式為止；
• 8.判斷棧中是否還有運算符，如果有的話，就把所有運算符出棧，并且把出棧的運算符存放數(shù)組a中。

對后綴表達式求值的步驟如下：

• 1.從頭到尾依次遍歷后綴表達式，每次從表達式中讀取一個字符；
• 2.判斷步驟1中讀取的字符，如果是數(shù)字則入棧，如果是+*等運算符，請看下一個步驟；
• 3.對存放數(shù)字的棧進行兩次出棧操作，依據(jù)步驟2中運算符的類型，對出棧的兩個數(shù)字進行運算；
• 4.對步驟3中的運算結(jié)果進行入棧操作，這樣可以把運算結(jié)果保存到存放數(shù)字的棧中；
• 5.重復(fù)步驟1到步驟4.直到遍歷完后綴表達式為止；
• 6.棧中最后一個元素就是該表達式的運算結(jié)果。

看官們，詳細的代碼如下，請大家參考：

     1  /* **************************
     2   * Head file of Expression Evaluation
     3   * *************************/
     4  #ifndef EXPRESSION_EVALUATION_H
     5  #define EXPRESSION_EVALUATION_H
     6  
     7  #include<stdio.h>
     8  #include<stdlib.h>
     9  
    10  #define SUCCESS 0
    11  #define FAILE 1
    12  
    13  #define LEN 20 //棧的長度先定義為5,需要時可自行修改
    14  
    15  typedef char StackElmt; //把char當作棧中元素的類型，實際中可以使用其它的類型或者自己定義一個元素類型
    16  typedef struct _Stack{
    17      StackElmt *base;
    18      StackElmt *top;
    19      int size;
    20  }Stack;
    21  
    22  StackElmt STACK[LEN+1] = {0}; //順序存儲方式的棧,防止數(shù)組越界，最后一個位置不放元素
    23  
    24  //聲明函數(shù)原型，這里有入棧和出棧操的函數(shù)
    25  int StackInit(Stack *s);
    26  int StackDestroy(Stack *s);
    27  int StackPrint(Stack *s);
    28  int StackPush(Stack *s, StackElmt e);
    29  int StackPop(Stack *s, StackElmt *e);
    30  
    31  #endif /* EXPRESSION_EVALUATION_H */

     1  /* **************************
     2   * Soure file of Expression Evaluation
     3   * *************************/
     4  
     5  #include"ExpressionEvaluation.h"
     6  
     7  //實現(xiàn)棧相關(guān)的函數(shù)，為了方便,放到了主函數(shù)所在的文件中，最好是單獨建立實現(xiàn)函數(shù)的源文件
     8  //初始化中棧
     9  int StackInit(Stack *s)
    10  {
    11      if(NULL == s)
    12          return FAILE;
    13  
    14      s->top = s->base = &STACK[0];
    15      s->size = 0;
    16  
    17  }
    18  int StackDestroy(Stack *s)
    19  {
    20      int i =0;
    21  
    22      if(NULL == s)
    23          return FAILE;
    24  
    25      while(i<LEN)
    26      {
    27          STACK[i] = 0;
    28          i++;
    29      }
    30      s->top = s->base = NULL;
    31      s->size = 0;
    32  }
    33  //輸出棧中存放的元素
    34  int StackPrint(Stack *s)
    35  {
    36      int index = 0;
    37  
    38      if(NULL == s)
    39          return FAILE;
    40  
    41      if(s->size == 0)
    42      {
    43          printf("the Stack is empty,there is not any element \n");
    44          return FAILE;
    45      }
    46  
    47      while(index < (s->size))
    48      {
    49          printf("%d  ",*((s->base)+index) );
    50          index++;
    51      }
    52  
    53      printf("\n ");
    54  
    55      return SUCCESS;
    56  }
    57  
    58  //入棧函數(shù),top指向棧頂,先把元素入棧,然后向棧頂移動一位
    59  int StackPush(Stack *s, StackElmt e)
    60  {
    61      if(NULL == s)
    62          return FAILE;
    63  
    64      if(s->size >= LEN)
    65      {
    66          printf("the Stack is full \n");
    67          return FAILE;
    68      }
    69  
    70      *(s->top) = e;
    71      (s->top)++;
    72      (s->size)++;
    73  
    74      return SUCCESS;
    75  }
    76  
    77  //出棧函數(shù),top先向棧底移到一位，然后移出當前它所指向的元素
    78  int StackPop(Stack *s, StackElmt *e)
    79  {
    80      if(NULL == s)
    81          return FAILE;
    82  
    83      if(s->size == 0)
    84      {
    85          //printf("the Stack is empty \n");
    86          return FAILE;
    87      }
    88  
    89      (s->top)--;
    90      *e = *(s->top);
    91      (s->size)--;
    92  
    93      return SUCCESS;
    94  }
    95  
    96  int main()
    97  {
    98      char ch = '\0';
    99      char str[2];
   100      char *a1= "1+2*3-6/3"; // 存放中綴表達式
   101      //char *a1="1+2+3*4";
   102      char a2[LEN]={'\0'}; // 存放后綴表達式
   103      Stack s;
   104      int i,j;
   105      int a,b;
   106      int res = 0;
   107      int stack[LEN] ={0};
   108  
   109      i = j = a = b = 0;
   110      StackInit(&s);
   111  
   112      while(*(a1+i) != '\0') //遍歷中綴表達式
   113      {
   114          printf("%c",*(a1+i));
   115  
   116          if(*(a1+i) == '+' || *(a1+i) == '-')
   117          {
   118              if(s.size != 0)
   119              {
   120                  while( s.size >= 0 && !StackPop(&s,&ch))
   121                  {
   122                      *(a2+j) = ch;
   123                      ch = '\0';
   124                      j++;
   125                  }
   126                  StackPush( &s,*(a1+i) );
   127              }
   128              else
   129                  StackPush(&s,*(a1+i));
   130          }
   131          else if( *(a1+i) == '*' || *(a1+i) == '/')
   132          {
   133              if(s.size != 0)
   134              {
   135                  if(!StackPop(&s,&ch))
   136                  {
   137                      if(ch == '+' || ch == '-')
   138                      {
   139                          StackPush(&s,ch);
   140                          StackPush( &s,*(a1+i) );
   141                      }
   142                      else
   143                      {
   144                          StackPush(&s,ch);
   145                          while( !StackPop(&s,&ch) && (ch == '*' || ch == '/') )
   146                          {
   147                              *(a2+j) = ch;
   148                              ch = '\0';
   149                              j++;
   150                          }
   151                          StackPush( &s,*(a1+i) );
   152                      }
   153                  }
   154              }
   155              else
   156                  StackPush(&s,*(a1+i));
   157          }
   158          else //從中綴表達式中讀取的字符是數(shù)字，保存到數(shù)組中
   159          {
   160              *(a2+j) = *(a1+i);
   161              j++;
   162          }
   163  
   164          i++;
   165      }
   166  
   167      while( s.size >= 0 && !StackPop(&s,&ch)) //棧中還有運算符的話，需要全部取出，放到后綴表達式中
   168      {
   169          *(a2+j) = ch;
   170          ch = '\0';
   171          j++;
   172      }
   173      *(a2+j) = '\0';
   174  
   175      i=j=0;
   176      StackDestroy(&s);
   177      StackInit(&s);
   178  
   179      while(*(a2+i) != '\0') //遍歷后綴表達式
   180      {
   181          if(*(a2+i) == '+')
   182          {
   183              j--;
   184              a = stack[j];
   185              j--;
   186              b = stack[j];
   187  
   188              stack[j]= a+b;
   189              j++;
   190          }
   191          else if(*(a2+i) == '-')
   192          {
   193              j--;
   194              a = stack[j];
   195              j--;
   196              b = stack[j];
   197  
   198              stack[j]= b-a;
   199              j++;
   200          }
   201          else if(*(a2+i) == '*')
   202          {
   203              j--;
   204              a = stack[j];
   205              j--;
   206              b = stack[j];
   207  
   208              stack[j]= a*b;
   209              j++;
   210          }
   211          else if(*(a2+i) == '/')
   212          {
   213              j--;
   214              a = stack[j];
   215              j--;
   216              b = stack[j];
   217  
   218              stack[j]= b/a;
   219              j++;
   220          }
   221          else
   222          {
   223              str[0] =*(a2+i);
   224              str[1] ='\0';
   225              stack[j]= atoi(str);
   226              j++;
   227          }
   228  
   229          i++;
   230      }
   231      res =stack[0];
   232  
   233      printf(" = %d ",res);
   234      printf("\n");
   235      return SUCCESS;
   236  }

從代碼中可以看到，我們用了兩次棧，一次是在中綴表達式轉(zhuǎn)換成后綴表達式的過程中，棧用來存放運算 符。另外一次是在后綴表達式求值的過程中，棧用來存放參與運算的數(shù)字。

各位看官，關(guān)于表達式求值的例子咱們就說到這里。欲知后面還有什么例子，且聽下回分解。