堆疊的應用—中序表示轉後序表示 - 筆記長也

堆疊的應用—中序表示轉後序表示

2018-02-08 21:00:54   資料結構

中序轉後序

中序與後序表示法:

一般我們平常使用的表示方法都屬於中序,如:a*(b+c)*d。該算式的後序則為:abc+*d*。

中序與後序的轉換:

若以上面的算式為例子,我們先依照運算子的計算先後順序將其括弧:

1.  (a*(b+c))*d

2.  ((a*(b+c))*d)

3.  都加上括弧之後,將運算子放到括弧右方

    ((a(bc)+)*d)*

4.再將括弧去除就是後序表示法了

    abc+*d*

堆疊之應用:中序轉後序

概念

上面所介紹的轉換方式是快速的算法,若是以正規的堆疊方式計算,要先知道每個運算子的先後順序:

符 號 in-stack priority(ISP) in-coming priority(ICP)
) - -
+(正)、-(負)、!、^(次方) 3 4
*、/、% 2 2
+(加)、- (減) 1 1
( 0 4

(ISP是堆疊最上層(TOP)之中的順序,ICP是該token的順序。)

當我們開始轉換時,堆疊為空。我們把運算式和運算子當成token,當token為運算元時,則直接print,若為運算子,則比較ICP與ISP:

(1).當ICP <= ISP時,則輸出堆疊直到ICP > ISP。

(2).當 ICP > ISP 十,再把此token加入到堆疊之中。

我們以 A*( B+C ) * D 來示範轉換之過程:

TOKEN 堆  疊 輸  出 說  明
none   none  
A   A A為運算元,直接PRINT出
* * A 堆疊一開始為空,無論如何第一個運算子都會被放入
(

(
*

A ( 的 ICP 大於 * 的 ISP,直接放入堆疊
B

(
*

AB B是運算元直接PRINT出
+ +
(
*
AB + 的 ICP 大於 ( 的 ISP
C +
(
*
ABC C是運算元直接PRINT出
) * ABC+ 遇到 ) 則輸出堆疊,直到 ( 為止,再將 ( 刪去
* * ABC+* 此處輸出的 * 是堆疊中的 * ,由於ICP==ISP,因此會輸出堆疊中的 *
D * ABC+*D D為運算元,直接PRINT出
none   ABC+*D* 遇到運算式末端,直接PRINT堆疊中的所有運算子

以JAVA實作

我們實作的方式是利用個別判斷ICP與ISP的方式,共有三個函數:main、geticp、getisp,有效運算子:(、)、*、/、+、-

geticp:

public static int geticp(char text) { //取得ICP
        int icp = 0;
        switch (text) {
            case '(':
                icp = 4;
                break;
            case '*':
            case '/':
                icp = 2;
                break;
            case '+':
            case '-':
                icp = 1;
                break;
            default:
                break;
        }
        return icp;
    }

getisp :

public static int getisp(char text) {   //取得ISP
        int isp = 0;
        switch (text) {
            case '(':
                isp = 0;
                break;
            case '*':
            case '/':
                isp = 2;
                break;
            case '+':
            case '-':
                isp = 1;
                break;
        }
        return isp;
    }

基本上這2個函式都是傳入一個Char,並個別判斷出該字的icp或isp

main:

public static void main(String[] args) {
        Scanner key = new Scanner(System.in);
        System.out.print("--------------------\n");
        System.out.print("----有效運算子:------\n");
        System.out.print("/(除)、*(乘)、+(加)、-(減)、(、)\n");
        System.out.print("---------------------\n");
        System.out.print("請輸入中序運算式:");
        String str = key.nextLine();

        char[] infix = new char[str.length() + 1]; /*建立一個陣列,將運算式放入*/
        char[] stack_t = new char[str.length()]; /*放入還不用輸出的字元*/
        int top = 0; //堆疊TOP,0不使用
        for (int i = 0; i < str.length(); i++) {
            infix[i] = str.charAt(i);
        }
        infix[str.length()] = '#'; /*在運算式末端加上#代表結束*/
        int icp = 0;
        int isp = 0;
        for (int j = 0; j < infix.length; j++) {
            switch (infix[j]) {   //判斷為運算子或運算元
                case ')':
                    while (stack_t[top] != '(') { //輸出直到(
                        System.out.print(stack_t[top]);
                        top--;
                    }
                    stack_t[top] = '\0'; /*將(清除*/
                    top--;
                    break;
                case '#':
                    for (int s = top; s >= 0; s--) { /*輸出堆疊中剩餘的字元*/
                        if (stack_t[s] != '\0') {
                            System.out.print(stack_t[s]);
                        }
                    }
                    break;
                case '(':
                case '*':
                case '/':
                case '+':
                case '-':
                    //運算子
                    //直接判斷給予ICP值
                    icp=geticp(infix[j]);
                    if (top == -1) { //堆疊為空時直接把運算子放進去
                        top++;
                        stack_t[top] = infix[j];
                    } else {    //否則取得堆疊TOP的ISP
                        isp=getisp(stack_t[top]);
                        //比較ICP與ISP
                        if (icp > isp) {//如果ICP比較大,則直接加入堆疊
                            top++;
                            stack_t[top] = infix[j];
                        } else {//如果比較小,輸出堆疊直到ICP>ISP,再把該運算子加入
                            while(icp<=getisp(stack_t[top])){
                                System.out.print(stack_t[top--]);
                            }
                            top++;
                            stack_t[top]=infix[j];
                        }
                    }
                    break;
                default:
                    System.out.print(infix[j]);//若為運算元則直接輸出
            }
        }
    }

輸入運算式後,先將運算式放入一個陣列當中,並在末端加上"#"符號代表運算式結束。之後開始做轉換。

當遇到運算元時直接print出,當遇到運算子時,若為" ) "則輸出堆疊直到 " ( ",再將 " ( " 刪除。

當遇到(、*、/、+、-時,則取得ICP,再與堆疊頂端(TOP)的ISP比較,直到ICP > ISP ,再將該token加入堆疊當中。

當遇到" # "時,代表運算式已結束,則輸出所有堆疊中的運算子。

執行結果:

run:
--------------------
----有效運算子:------
/(除)、*(乘)、+(加)、-(減)、(、)
---------------------
請輸入中序運算式:A*(B+C)*D
ABC+*D*

總結

除了中序之外,當然也有前序,則與後序剛好是相反的動作。堆疊的應用除了中序與後序轉換外,函式的呼叫也屬於一種堆疊,例如從函數X呼叫函數Y,再從函數Y呼叫函數Z,則會先從Z回傳至Y,再由Y回傳至X,同樣具有堆疊的先進後出的特性。當然,遞迴也是堆疊,只是他是呼叫自己回傳給自己。

關於後序的計算,將另外發文。

關於作者


長也

資管菸酒生,嘗試成為網頁全端工程師(laravel / React),技能樹成長中,閒暇之餘就寫一些筆記。 喔對了,也愛追一些劇,例如火神跟遺物整理師,推推。最愛的樂團應該是告五人吧(?)