2012年11月24日 星期六

Infix to Postfix + Computation of Postfix

程式目的:將中序式(infix)轉換為後序式(postfix),並將postfix的值計算出來
程式語言: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則回傳錯誤的判斷,相當的直觀,故應該很容易理解,當然相對的程式優化程度低,效能也會比較差,只希望對有需要的人有所幫助,有任何錯誤也請不吝指教!