前中後运算式转置

中置运算式是人脑的计算中最直观且最习惯理解的表示式，会将运算子(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;
}

中转後序

程序说明

与前序差异

1:

• 前置式:由最後一个字元判断到第一个字元。
• 後置式:第一个判断到最後一个。

2:

• 前置式:在判断取代运算子的时候，是以大於其运算子为依据。
• 後置式:在判断取代运算子的时候，是以大於且等於其运算子为依据。

3:

• 前置式:因为在引入字元顺序式相反的，所以要将')'作为优先存入，并判断结束的'('。
• 後置式:因为在引入字元的顺序是正常的，所以优先存入按照'('後')'的基本法则就好

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