數據結構和演算法（六）：前綴、中綴、後綴表達式

目錄

1、人如何解析算術表達式

2、計算機如何解析算術表達式

3、後綴表達式

　　①、如何將中綴表達式轉換為後綴表達式？

　　②、計算機如何實現後綴表達式的運算？

4、前綴表達式

　　①、如何將中綴表達式轉換為前綴表達式？

　　②、計算機如何實現前綴表達式的運算？

　　前面我們介紹了三種數據結構，第一種數組主要用作數據存儲，但是後面的兩種棧和隊列我們說主要作為程序功能實現的輔助工具，其中在介紹棧時我們知道棧可以用來做單詞逆序，匹配關鍵字元等等，那它還有別的什麼功能嗎？以及數據結構與本篇博客的主題前綴、中綴、後綴表達式有什麼關係呢？

1、人如何解析算術表達式

　　如何解析算術表達式？或者換種說法，遇到某個算術表達式，我們是如何計算的：

①、求值 3+4-5

　　這個表達式，我們在看到3+4後都不能直接計算3+4的值，知道看到4後面的 - 號，因為減號的優先順序和前面的加號一樣，所以可以計算3+4的值了，如果4後面是 * 或者 /，那麼就要在乘除過後才能做加法操作，比如：

②、求值 3+4*5

　　這個不能先求3+4的值，因為4後面的*運算級別比前面的+高。通過這兩個表達式的說明，我們可以總結解析表達式的時候遵循的幾條規則：

①、從左到右讀取算式。

　　②、已經讀到了可以計算值的兩個操作數和一個操作符時，可以計算，並用計算結果代替那兩個操作數和一個操作符。

　　③、繼續這個過程，從左到右，能算就算，直到表達式的結尾。

2、計算機如何解析算術表達式

　　對於前面的表達式 3+4-5，我們人是有思維能力的，能根據操作符的位置，以及操作符的優先順序別能算出該表達式的結果。但是計算機怎麼算？

　　計算機必須要向前（從左到右）來讀取操作數和操作符，等到讀取足夠的信息來執行一個運算時，找到兩個操作數和一個操作符進行運算，有時候如果後面是更高級別的操作符或者括弧時，就必須推遲運算，必須要解析到後面級別高的運算，然後回頭來執行前面的運算。我們發現這個過程是極其繁瑣的，而計算機是一個機器，只認識高低電平，想要完成一個簡單表達式的計算，我們可能要設計出很複雜的邏輯電路來控制計算過程，那更不用說很複雜的算術表達式，所以這樣來解析算術表達式是不合理的，那麼我們應該採取什麼辦法呢？

　　請大家先看看什麼是前綴表達式，中綴表達式，後綴表達式：這三種表達式其實就是算術表達式的三種寫法，以 3+4-5為例

　　①、前綴表達式：操作符在操作數的前面，比如 +-543

　　②、中綴表達式：操作符在操作數的中間，這也是人類最容易識別的算術表達式 3+4-5

　　③、後綴表達式：操作符在操作數的後面，比如 34+5-

　　上面我們講的人是如何解析算術表達式的，也就是解析中綴表達式，這是人最容易識別的，但是計算機不容易識別，計算機容易識別的是前綴表達式和後綴表達式，將中綴表達式轉換為前綴表達式或者後綴表達式之後，計算機能很快計算出表達式的值，那麼中綴表達式是如何轉換為前綴表達式和後綴表達式，以及計算機是如何解析前綴表達式和後綴表達式來得到結果的呢？

3、後綴表達式

　　後綴表達式，指的是不包含括弧，運算符放在兩個運算對象的後面，所有的計算按運算符出現的順序，嚴格從左向右進行（不再考慮運算符的優先規則）。

　　由於後綴表達式的運算符在兩個操作數的後面，那麼計算機在解析後綴表達式的時候，只需要從左向右掃描，也就是只需要向前掃描，而不用回頭掃描，遇到運算符就將運算符放在前面兩個操作符的中間（這裡先不考慮乘方類似的單目運算），一直運算到最右邊的運算符，那麼就得出運算結果了。既然後綴表達式這麼好，那麼問題來了：

　　①、如何將中綴表達式轉換為後綴表達式？

　　對於這個問題，轉換的規則如下：

　　一、先自定義一個棧

package com.ys.poland; public class MyCharStack { private char[] array; private int maxSize; private int top; public MyCharStack(int size){ this.maxSize = size; array = new char[size]; top = -1; } //壓入數據 public void push(char value){ if(top < maxSize-1){ array[++top] = value; } } //彈出棧頂數據 public char pop(){ return array[top--]; } //訪問棧頂數據 public char peek(){ return array[top]; } //查看指定位置的元素 public char peekN(int n){ return array[n]; } //為了便於後面分解展示棧中的內容，我們增加了一個遍歷棧的方法(實際上棧只能訪問棧頂元素的) public void displayStack(){ System.out.print("Stack(bottom-->top):"); for(int i = 0 ; i < top+1; i++){ System.out.print(peekN(i)); System.out.print( ); } System.out.println(""); } //判斷棧是否為空 public boolean isEmpty(){ return (top == -1); } //判斷棧是否滿了 public boolean isFull(){ return (top == maxSize-1); } }

　　二、前綴表達式轉換為後綴表達式

package com.ys.poland;public class InfixToSuffix { private MyCharStack s1;// 定義運算符棧 private MyCharStack s2;// 定義存儲結果棧 private String input; // 默認構造方法，參數為輸入的中綴表達式 public InfixToSuffix(String in) { input = in; s1 = new MyCharStack(input.length()); s2 = new MyCharStack(input.length()); } // 中綴表達式轉換為後綴表達式，將結果存儲在棧中返回，逆序顯示即後綴表達式 public MyCharStack doTrans() { for (int j = 0; j < input.length(); j++) { System.out.print("s1棧元素為："); s1.displayStack(); System.out.print("s2棧元素為："); s2.displayStack(); char ch = input.charAt(j); System.out.println("當前解析的字元:" + ch); switch (ch) { case +: case -: gotOper(ch, 1); break; case *: case /: gotOper(ch, 2); break; case (: s1.push(ch);// 如果當前字元是(,則將其入棧 break; case ): gotParen(ch); break; default: // 1、如果當前解析的字元是操作數，則直接壓入s2 // 2、 s2.push(ch); break; }// end switch }// end for while (!s1.isEmpty()) { s2.push(s1.pop()); } return s2; } public void gotOper(char opThis, int prec1) { while (!s1.isEmpty()) { char opTop = s1.pop(); if (opTop == () {// 如果棧頂是(,直接將操作符壓入s1 s1.push(opTop); break; } else { int prec2; if (opTop == + || opTop == -) { prec2 = 1; } else { prec2 = 2; } if (prec2 < prec1) {// 如果當前運算符比s1棧頂運算符優先順序高，則將運算符壓入s1 s1.push(opTop); break; } else {// 如果當前運算符與棧頂運算符相同或者小於優先順序別，那麼將S1棧頂的運算符彈出並壓入到S2中 // 並且要再次再次轉到while循環中與 s1 中新的棧頂運算符相比較； s2.push(opTop); } } }// end while // 如果s1為空，則直接將當前解析的運算符壓入s1 s1.push(opThis); } // 當前字元是 ) 時，如果棧頂是(,則將這一對括弧丟棄，否則依次彈出s1棧頂的字元，壓入s2，直到遇到( public void gotParen(char ch) { while (!s1.isEmpty()) { char chx = s1.pop(); if (chx == () { break; } else { s2.push(chx); } } }}

　　三、測試

@Testpublic void testInfixToSuffix(){ String input; System.out.println("Enter infix:"); Scanner scanner = new Scanner(System.in); input = scanner.nextLine(); InfixToSuffix in = new InfixToSuffix(input); MyCharStack my = in.doTrans(); my.displayStack();}

　　四、結果

　　五、分析

　　②、計算機如何實現後綴表達式的運算？

4、前綴表達式

　　前綴表達式，指的是不包含括弧，運算符放在兩個運算對象的前面，嚴格從右向左進行（不再考慮運算符的優先規則），所有的計算按運算符出現的順序。

　　注意：後綴表達式是從左向右解析，而前綴表達式是從右向左解析。

　　①、如何將中綴表達式轉換為前綴表達式？

　　②、計算機如何實現前綴表達式的運算？

下篇文章：