C++經典演算法題-後序式的運算

• 2020 年 2 月 13 日
• 筆記

23.Algorithm Gossip: 後序式的運算

說明

將中序式轉換為後序式的好處是，不用處理運運算元先後順序問題，只要依序由運算式由前往後讀取即可。

解法

運算時由後序式的前方開 堆疊始讀取，遇到運算元先存入堆疊，如果遇到運運算元，則由堆疊中取出兩個運算元進行對應的運算，然後將結果存回堆疊，如果運算式讀取完 畢，那麼堆疊頂的值就是答案了， 例如我們計算12+34+這個運算式（也就是(1+2)*(3+4)）： 讀取

1	1  2	1 2  +	3 // 1+2 後存回  3	3 3  4	3 3 4  +	3 7 // 3+4 後存回  *	21 // 3 * 7  後存回

程式碼示例

#include<stdio.h>  #include<stdlib.h>        void evalPf(char*);        double cal(double, char, double);        int main(void) {          char input[ 80];            printf("輸入後序式：");          scanf("%s", input);          evalPf(input);          return 0;      }        void evalPf(char*postfix) {          double stack[ 80] ={              0.0          } ;          char temp[ 2];          char token;          int top = 0, i = 0;          temp[1] = '';          while (1) {              token = postfix[i];              switch (token) {                  case '':                      printf("ans = %fn", stack[top]);                      return;                  case '+':                  case '-':                  case '*':                  case '/':                      stack[top - 1] =                              cal(stack[top], token, stack[top - 1]);                      top--;                      break;                  default:                      if (top < sizeof(stack) / sizeof( float)){                      temp[0] = postfix[i];                      top++;                      stack[top] = atof(temp);                      }                  i++;              }          }        }  	break;          double cal(double p1, char op, double p2) {          switch (op) {              case '+':                  return p1 + p2;                case '-':                  return p1 - p2;              case '*':                  return p1 * p2;              case '/':                  return p1 / p2;          }      }