iT邦幫忙

1

【資料結構】前中後運算式轉置

前中後運算式轉置

中置運算式是人腦的計算中最直觀且最習慣理解的表示式,會將運算子(EX:加號)放在兩個運算元中間,然而這並不是電腦對運算式的處理方式,電腦會消除括號,並將運算子放在運算元的前後,分別稱為前置運算式後置運算式,以下便是將中置的運算式處理為電腦所熟悉的表示法。

中轉前序

程式說明

相關函式

reverse():將特定字串反轉

說明:
將存入字串做反轉的處理。
void reverse(char str[MAX]) {
  int i, j;
  char c;
  for (i = 0, j = strlen(str) - 1; i < j; ++i, --j)
    c = str[i], str[i] = str[j], str[j] = c;
}

compare():判別運算子並回傳優先度

說明:
利用switch來判斷引入字元,並回傳其優先度。
int compare(char op) {
  switch (op) {
  case '+':
  case '-':
    return 1;
  case '*':
  case '/':
  case '%':
    return 2;
  default:
    return 0;
  }
}

Prefix():帶入原中置運算式,並生成前置運算式

說明:
原運算式會經過轉換,並存入新的陣列中,原運算式經過倒經過倒的順序,
會生成與結果運算式相反的字串。
void Prefix(char *str, char *new_str) {
  char stack[MAX];
  int top = 0, j = 0, i;
  for (i = strlen(str) - 1; i >= 0; i--) {
    // printf("\n--------%c--------\n", str[i]);
    //由最後一個開始處理到第一個字元
    switch (str[i]) {
    case '+':
    case '-':
    case '*':
    case '/':
    case '%':
      while (compare(str[i]) < compare(stack[top])) {
        new_str[j++] = stack[top--];
      }
      //遇到運算符號時,先在while迴圈中利用compare判斷優先度,
      //將stack堆疊中大於目前運算子優先度提出
      stack[++top] = str[i];
      //存入當前運算子到stack堆疊中
      continue;
    case ')':
      stack[++top] = str[i];
      continue;
      //因為是倒著輸出,因此在合法的運算式中會最先遇到')',
      //一樣將')'存入堆疊,等待'('出現
    case '(':
      while (stack[top] != ')') {
        new_str[j++] = stack[top--];
      }
      top--;
      continue;
      //遇到'('時,將堆疊內的運算子全數輸出,直到遇見')'
    default:
      new_str[j++] = str[i];
      continue;
      //非運算子的字元直接存入新字串
    }
  }
  while (top != 0) {
    new_str[j++] = stack[top--];
  }
}

Infix_to_Prefix():整合中置轉前置之功能

說明:
因為Prefix在處理運算式的過程是倒著處理,所以輸出的結果是相反
的,需要藉由reverse函式,將運算結果倒回來。
void Infix_to_Prefix(char str[]) {
  char new_str[MAX] = {"\0"};
  printf("\n--------------------------\n");
  printf("中置式:%s\n", str);
  Prefix(str, new_str);
  reverse(new_str);
  printf("前置式:%s", new_str);
}

主程式:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define MAX 20
int main() {
  char str1[MAX] = {"2+3*2/2-2"};
  char str2[MAX] = {"4/2-1+2*3-4*1"};
  //測資1,2
  Infix_to_Prefix(str1);
  Infix_to_Prefix(str2);
  return 0;
}

中轉後序

程式說明

與前序差異

avatar
1:

  • 前置式:由最後一個字元判斷到第一個字元。
  • 後置式:第一個判斷到最後一個。

2:

  • 前置式:在判斷取代運算子的時候,是以大於其運算子為依據。
  • 後置式:在判斷取代運算子的時候,是以大於且等於其運算子為依據。

3:

  • 前置式:因為在引入字元順序式相反的,所以要將')'作為優先存入,並判斷結束的'('。
  • 後置式:因為在引入字元的順序是正常的,所以優先存入按照'('後')'的基本法則就好

之後再用看看能不能前後直接互換和轉中置表示法。


尚未有邦友留言

立即登入留言