C++經典演算法題-中序式轉後序式（前序式）
- 2020 年 2 月 13 日
- 筆記
22.Algorithm Gossip: 中序式轉後序式（前序式）
說明
平常所使用的運算式，主要是將運算元放在運運算元的兩旁，例如a+b/d這樣的式子，這稱 之為中序（Infix）表示式，對於人類來說，這樣的式子很容易理 解，但由於電腦執行指令時是有順序的，遇到中序表示式時，無法直接進行運算，而必須進一步判斷運算的先後順序，所以必須將中序表示式轉換為另一種表示方法。
可以將中序表示式轉換為後序（Postfix）表示式，後序表示式又稱之為逆向波蘭表示式（Reverse polish notation），它是由波蘭的數學家盧卡謝維奇提出，例如(a+b)*(c+d)這個式子，表示為後序表示式時是ab+cd+*。
解法
用手算的方式來計算後序式相當的簡單，將運運算元兩旁的運算元依先後順序全括弧起來，然後將所有的右括弧取代為左邊最接近的運運算元（從最內層括弧開始），最後去掉所有的左括弧就可以完成後序表示式，例如：
a+b*d+c/d => ((a+(b*d))+(c/d)) -> bd*+cd/+
如果要用程式來進行中序轉後序，則必須使用堆疊，演演算法很簡單，直接敘述的話就是使用迴圈，取出中序式的字元，遇運算元直接輸出，堆疊運運算元與左括弧， ISP>ICP的話直接輸出堆疊中的運運算元，遇右括弧輸出堆疊中的運運算元至左括弧。
如果要將中序式轉為前序式，則在讀取中序式時是由後往前讀取，而左右括弧的處理方式相反， 其餘不變，但輸出之前必須先置入堆疊，待轉換完成後再將堆疊中的 值由上往下讀出，如此就是前序表示式。
程式碼示例
#include <stdio.h> #include <stdlib.h> int postfix(char*); // 中序轉後序 int priority(char); // 決定運運算元優先順序 int main(void) { char input[80]; printf("輸入中序運算式："); scanf("%s", input); postfix(input); return 0; } int postfix(char* infix) { int i = 0, top = 0; char stack[80] = {' '}; char op; while(1) { op = infix[i]; switch(op) { case ' ': while(top > 0) { printf("%c", stack[top]); top--; } printf("n"); return 0; // 運運算元堆疊 case '(': if(top < (sizeof(stack) / sizeof(char))) { top++; stack[top] = op; } break; case '+': case '-': case '*': case '/': while(priority(stack[top]) >= priority(op)) { printf("%c", stack[top]); top--; } // 存入堆疊 if(top < (sizeof(stack) / sizeof(char))) { top++; stack[top] = op; } break; // 遇 ) 輸出至 ( case ')': while(stack[top] != '(') { printf("%c", stack[top]); top--; } i++; } } } top--; // 不輸出( break; // 運算元直接輸出 default: printf("%c", op); break; int priority(char op) { int p; switch(op) { case '+': case '-': p = 1; break; case '*': case '/': p = 2; break; default: p = 0; break; } return p; }
