鍍金池/ 教程/ C/ 一起talk C栗子吧(第二十一回:C語(yǔ)言實(shí)例--表達(dá)式求值)
一起talk C栗子吧(第八回:C語(yǔ)言實(shí)例--素?cái)?shù))
一起talk C栗子吧(第十八回:C語(yǔ)言實(shí)例--輸出十六進(jìn)制)
一起talk C栗子吧(第十七回:C語(yǔ)言實(shí)例--棧二)
一起talk C栗子吧(第十九回:C語(yǔ)言實(shí)例--位操作)
一起talk C栗子吧(第十六回:C語(yǔ)言實(shí)例--棧一)
一起talk C栗子吧(第五回:C語(yǔ)言實(shí)例--數(shù)組巧妙賦值)
一起talk C栗子吧(第十二回:C語(yǔ)言實(shí)例--單鏈表一)
一起talk C栗子吧(第九回:C語(yǔ)言實(shí)例--最大公約數(shù))
一起talk C栗子吧(第二回:C語(yǔ)言實(shí)例--判斷閏年)
一起talk C栗子吧(第六回:C語(yǔ)言實(shí)例--生成隨機(jī)數(shù))
一起talk C栗子吧(第四回:C語(yǔ)言實(shí)例--斐波那契數(shù)列)
一起talk C栗子吧(第十四回:C語(yǔ)言實(shí)例--循環(huán)鏈表)
一起talk C栗子吧(第十五回:C語(yǔ)言實(shí)例--雙向鏈表)
一起talk C栗子吧(第二十一回:C語(yǔ)言實(shí)例--表達(dá)式求值)
一起talk C栗子吧(第三回:C語(yǔ)言實(shí)例--求階乘)
一起talk C栗子吧(第七回:C語(yǔ)言實(shí)例--進(jìn)制轉(zhuǎn)換)
一起talk C栗子吧(第二十回:C語(yǔ)言實(shí)例--括號(hào)匹配)
一起talk C栗子吧(第一回:C語(yǔ)言實(shí)例概述)
一起talk C栗子吧(第十回:C語(yǔ)言實(shí)例--最小公倍數(shù))
一起talk C栗子吧(第十一回:C語(yǔ)言實(shí)例--文件組織結(jié)構(gòu))
一起talk C栗子吧(第十三回:C語(yǔ)言實(shí)例--單鏈表二)

一起talk C栗子吧(第二十一回:C語(yǔ)言實(shí)例--表達(dá)式求值)

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

看官們,我們?cè)谶@里說(shuō)的表達(dá)式為包含加,減,乘除的四則運(yùn)算表達(dá)式。例如:1+23-4/5就是一個(gè)四則運(yùn) 算表達(dá)式。這個(gè)表達(dá)式中,運(yùn)算符在數(shù)字中間,所以我們叫它中綴表達(dá)式,這也是符合我們思維的一種表 現(xiàn)形式,不過(guò),計(jì)算機(jī)就不理解中綴表達(dá)式了,因?yàn)樗鼪](méi)有辦法像我們一樣先進(jìn)行乘除運(yùn)算,然后再進(jìn)行 加減運(yùn)算,所以我們需要把中綴表達(dá)式轉(zhuǎn)換成計(jì)算機(jī)能理解的后綴表達(dá)式。“什么是后綴表達(dá)式”,這時(shí)候 臺(tái)下有看官在提問(wèn)了,看官莫急,所謂的后綴表達(dá)式就是運(yùn)算符在數(shù)字后面。例如:" 1+23-6/3 "這個(gè)中綴 表達(dá)式可以為" 123*+63/- "這種后綴表達(dá)式.

表達(dá)式求值有兩個(gè)大的步驟:

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

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

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

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

對(duì)后綴表達(dá)式求值的步驟如下:

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

看官們,詳細(xì)的代碼如下,請(qǐng)大家參考:

     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 //棧的長(zhǎng)度先定義為5,需要時(shí)可自行修改
    14  
    15  typedef char StackElmt; //把char當(dāng)作棧中元素的類型,實(shí)際中可以使用其它的類型或者自己定義一個(gè)元素類型
    16  typedef struct _Stack{
    17      StackElmt *base;
    18      StackElmt *top;
    19      int size;
    20  }Stack;
    21  
    22  StackElmt STACK[LEN+1] = {0}; //順序存儲(chǔ)方式的棧,防止數(shù)組越界,最后一個(gè)位置不放元素
    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  //實(shí)現(xiàn)棧相關(guān)的函數(shù),為了方便,放到了主函數(shù)所在的文件中,最好是單獨(dú)建立實(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指向棧頂,先把元素入棧,然后向棧頂移動(dòng)一位
    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先向棧底移到一位,然后移出當(dāng)前它所指向的元素
    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"; // 存放中綴表達(dá)式
   101      //char *a1="1+2+3*4";
   102      char a2[LEN]={'\0'}; // 存放后綴表達(dá)式
   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') //遍歷中綴表達(dá)式
   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 //從中綴表達(dá)式中讀取的字符是數(shù)字,保存到數(shù)組中
   159          {
   160              *(a2+j) = *(a1+i);
   161              j++;
   162          }
   163  
   164          i++;
   165      }
   166  
   167      while( s.size >= 0 && !StackPop(&s,&ch)) //棧中還有運(yùn)算符的話,需要全部取出,放到后綴表達(dá)式中
   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') //遍歷后綴表達(dá)式
   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  }

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

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