程式語言：C 語言
開發工具：Dev-c++ 5.2.0.2
程式碼分享：cpp檔案、exe檔案
執行結果：
程式碼：
演算法：
理所當然的，要了解一個程式得從其演算法開始理解，若是搞懂了，基本上程式就完成7成囉，剩下的只是把這些步驟轉換為程式語言而已！
讓我們先從最基本的開了解：何謂中序式(infix)與後序式(postfix)？infix就是我們一般所寫的算式，將運算子放在運算元的中間，例如1 * ( 2 + 3 )；而postfix則是把運算子放在運算元的後面，以剛剛的例子而言， 則變為1 2 3 + *，並且可以注意到我們將括號都拿掉了。這次我們要做的就是從infix變為postfix的方法。
當我們拿到一個算式，首先來分析它的組成。一個算式可以簡單分成運算子(符號)及運算元(數字)兩個部分，處理的時候也大致就是分成兩種來工作：凡是遇到運算元，則直接輸出；遇到運算子則與我們準備好的stack最上層的運算子判斷，若是優先權低於等於stack中的運算子(例如 + → * )，輸出stack中的運算子，直到stack中的運算子優先權較低再把比較的運算子存入stack中，若是比較的stack原本優先權就較高，則直接存入stack中。一直重複上面兩種動作來處理運算子及運算元，直到算式結尾，再把stack中剩下的運算子一次輸出，最後即成我們所要求的postfix運算式。
在轉換的過程中，要注意的是遇到括號需要特別處理，括號可以分為左右括號來看。遇到左括號，無條件存入stack中；遇到右括號，從stack最上層開始輸出，直到遇到左括號為止，左右括號本身都不輸出。
好，現在我們有一個postfix算式了(假設前面沒算錯......)，現在該來把它的值計算出來。postfix的計算比起轉換簡單的多，一樣準備一個stack，遇到運算元就丟入stack中，遇到運算子就將stack最上層的兩個數取出來做運算，運算結果再存回stack中，這樣最終stack裡就是我們所求的答案哩！
以上就是本次程式的演算法，若是看不懂，放心不是你太笨，是我表達太差！建議可以參考這位作者的中序式轉後序式以及後序式的運算，寫的相當詳盡喔，同時裡面也有各種語言的程式碼範例，本程式也是以其為架構改寫的。
程式解析：
演算法了解了以後，就來看看這支程式要怎麼實作吧！
本程式分為5個function，分別為main、InToPost、Priority、PostToInt與Cal，main用來做資料的輸入以及輸出，InToPost實作infix與postfix的轉換，Priority比較運算子之間的優先權，PostToInt處理postfix算式的運算，Cal則做兩兩運算元間的計算。
在本程式中，所有的算式以及stack都以陣列來實作，運算元設定為整數，運算子僅處理+ - * / %五種，並且支援正負號，若有其他需要可自行調整，以下就依序來解析。
#define LENGTH 9999
首先在最外面，我們define了一個LENGTH，這個變數代表了未知的陣列長度，可以依需求來調整，通常會給它一個大一點的值，除非我們能明確的知道這個"未知"的範圍是多少。
#include "memory.h"
這個memory.h是用來支援我們在PostToInt所使用的memset，功能是設置陣列的值。
int Err=0;
宣告一個全域變數作為判斷錯誤的依據。
long long int PostToInt(char*);
long long int Cal(char, long long int, long long int);
注意到此處的宣告形態為long long int，是為了因應計算結果可能出現的超長整數，同裡除非我們能確定"值"的範圍，不然預設較寬裕的立場以防錯誤。
int main(void) {...}
main的部分相當單純，在讀入算式之後，分別做轉換、運算以及各自的錯誤判斷。需注意的是錯誤判斷必須分開處理，因為運算邏輯錯誤(例如除以0)只會在計算層面出錯，轉換並無影響。另外印出計算結果因應long long int型態，需使用%lld來取代%d。
void InToPost(char* Infix, char* Postfix) {...}
InToPost在轉換的過程中，除了使用switch case對運算子及運算元做基本的處理之外，最重要的就是大量的錯誤判斷，以下將分別解釋。
for(i = 0; Infix[i] != '\0'; i++){...}
if(temp!=0){...}
在轉換開始之前，先使用一個for loop及if來判斷左右括號的正確性，以temp計算左右括號，左括號+1，右括號-1，如此即可判斷，若是有先右括號再左括號的情形(計算中隨時temp<1)，又或是左右括號數量不對(計算完成temp!=0)，皆為錯誤。
for(i = 0, j = 0, Stack_Top = 0; Infix[i] != '\0'; i++)
{if(i==0){...}
...
switch(Infix[i]){...}
...}
轉換的最主要部分，一開始的if對首位做判斷，如果是數字當然沒問題，運算子的話，+-可以視為正負號，若是其他的則錯誤。switch case的部分，針對不同狀況做出相對的處理，並且判斷錯誤情形，例如右括號後面不會直接接數字之類，此為數學邏輯故不贅述，詳細的請自行參照程式碼。比較特別的是允許類似--3(減負三)或++7(加正七)的寫法。另外在顯示的部分，每個token之間以一個空格隔開，以助分辨，不然數字會擠在一起(例如13和5變成135)。
int Priority(char op) {...}
簡單的判斷符號的優先權，先乘除後加減，相信大家都會。
long long int PostToInt(char* /*Infix*/Postfix)
{...
switch(Postfix[i]){...}
...}
一樣使用switch case做不同運算子與運算元的處理，由於之前是使用字串做儲存，現在遇到數字先存入另一暫存陣列，並使用atoll轉換為long long int型態後再存入stack。其餘仍為數學邏輯判斷，請自行參考程式碼。
long long int Cal(char op, long long int N1, long long int N2){...}
最後的一個部分，由於邏輯判斷在前面都做過了，這裡單純的把傳來的運算子與運算元做計算即可。
結語：
本程式碼相當簡單，並沒有使用什麼高深的方法，例如A情況會是錯誤的，就單純的加個遇到A則回傳錯誤的判斷，相當的直觀，故應該很容易理解，當然相對的程式優化程度低，效能也會比較差，只希望對有需要的人有所幫助，有任何錯誤也請不吝指教！
沒有留言:
張貼留言