Java數(shù)據(jù)結(jié)構(gòu)和算法之前綴、中綴和后綴表達(dá)式的示例分析

小編給大家分享一下Java數(shù)據(jù)結(jié)構(gòu)和算法之前綴、中綴和后綴表達(dá)式的示例分析，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

1、人如何解析算術(shù)表達(dá)式

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

①、求值 3+4-5

這個表達(dá)式，我們在看到3+4后都不能直接計算3+4的值，知道看到4后面的 - 號，因?yàn)闇p號的優(yōu)先級和前面的加號一樣，所以可以計算3+4的值了，如果4后面是 * 或者 /，那么就要在乘除過后才能做加法操作，比如：

②、求值 3+4*5

這個不能先求3+4的值，因?yàn)?后面的*運(yùn)算級別比前面的+高。通過這兩個表達(dá)式的說明，我們可以總結(jié)解析表達(dá)式的時候遵循的幾條規(guī)則：

• ①、從左到右讀取算式。

• ②、已經(jīng)讀到了可以計算值的兩個操作數(shù)和一個操作符時，可以計算，并用計算結(jié)果代替那兩個操作數(shù)和一個操作符。

• ③、繼續(xù)這個過程，從左到右，能算就算，直到表達(dá)式的結(jié)尾。

2、計算機(jī)如何解析算術(shù)表達(dá)式

對于前面的表達(dá)式 3+4-5，我們?nèi)耸怯兴季S能力的，能根據(jù)操作符的位置，以及操作符的優(yōu)先級別能算出該表達(dá)式的結(jié)果。但是計算機(jī)怎么算？

計算機(jī)必須要向前（從左到右）來讀取操作數(shù)和操作符，等到讀取足夠的信息來執(zhí)行一個運(yùn)算時，找到兩個操作數(shù)和一個操作符進(jìn)行運(yùn)算，有時候如果后面是更高級別的操作符或者括號時，就必須推遲運(yùn)算，必須要解析到后面級別高的運(yùn)算，然后回頭來執(zhí)行前面的運(yùn)算。我們發(fā)現(xiàn)這個過程是極其繁瑣的，而計算機(jī)是一個機(jī)器，只認(rèn)識高低電平，想要完成一個簡單表達(dá)式的計算，我們可能要設(shè)計出很復(fù)雜的邏輯電路來控制計算過程，那更不用說很復(fù)雜的算術(shù)表達(dá)式，所以這樣來解析算術(shù)表達(dá)式是不合理的，那么我們應(yīng)該采取什么辦法呢？

請大家先看看什么是前綴表達(dá)式，中綴表達(dá)式，后綴表達(dá)式：這三種表達(dá)式其實(shí)就是算術(shù)表達(dá)式的三種寫法，以 3+4-5為例

• ①、前綴表達(dá)式：操作符在操作數(shù)的前面，比如 +-543

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

• ③、后綴表達(dá)式：操作符在操作數(shù)的后面，比如 34+5-

上面我們講的人是如何解析算術(shù)表達(dá)式的，也就是解析中綴表達(dá)式，這是人最容易識別的，但是計算機(jī)不容易識別，計算機(jī)容易識別的是前綴表達(dá)式和后綴表達(dá)式，將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式或者后綴表達(dá)式之后，計算機(jī)能很快計算出表達(dá)式的值，那么中綴表達(dá)式是如何轉(zhuǎn)換為前綴表達(dá)式和后綴表達(dá)式，以及計算機(jī)是如何解析前綴表達(dá)式和后綴表達(dá)式來得到結(jié)果的呢？

3、后綴表達(dá)式

后綴表達(dá)式，指的是不包含括號，運(yùn)算符放在兩個運(yùn)算對象的后面，所有的計算按運(yùn)算符出現(xiàn)的順序，嚴(yán)格從左向右進(jìn)行（不再考慮運(yùn)算符的優(yōu)先規(guī)則）。

由于后綴表達(dá)式的運(yùn)算符在兩個操作數(shù)的后面，那么計算機(jī)在解析后綴表達(dá)式的時候，只需要從左向右掃描，也就是只需要向前掃描，而不用回頭掃描，遇到運(yùn)算符就將運(yùn)算符放在前面兩個操作符的中間（這里先不考慮乘方類似的單目運(yùn)算），一直運(yùn)算到最右邊的運(yùn)算符，那么就得出運(yùn)算結(jié)果了。既然后綴表達(dá)式這么好，那么問題來了：

①、如何將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式？

對于這個問題，轉(zhuǎn)換的規(guī)則如下：

一、先自定義一個棧

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;
    }
    //壓入數(shù)據(jù)
    public void push(char value){
        if(top < maxSize-1){
            array[++top] = value;
        }
    }
    //彈出棧頂數(shù)據(jù)
    public char pop(){
        return array[top--];
    }
    //訪問棧頂數(shù)據(jù)
    public char peek(){
        return array[top];
    }
    //查看指定位置的元素
    public char peekN(int n){
        return array[n];
    }
    //為了便于后面分解展示棧中的內(nèi)容，我們增加了一個遍歷棧的方法(實(shí)際上棧只能訪問棧頂元素的)
    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);
    }
}

二、前綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式

package com.ys.poland;
public class InfixToSuffix {
    private MyCharStack s1;//定義運(yùn)算符棧
    private MyCharStack s2;//定義存儲結(jié)果棧
    private String input;
    //默認(rèn)構(gòu)造方法，參數(shù)為輸入的中綴表達(dá)式
    public InfixToSuffix(String in){
        input = in;
        s1 = new MyCharStack(input.length());
        s2 = new MyCharStack(input.length());
    }
    //中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，將結(jié)果存儲在棧中返回，逆序顯示即后綴表達(dá)式
    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("當(dāng)前解析的字符:"+ch);
            switch (ch) {
            case '+':
            case '-':
                gotOper(ch,1);
                break;
            case '*':
            case '/':
                gotOper(ch,2);
                break;
            case '(':
                s1.push(ch);//如果當(dāng)前字符是'(',則將其入棧
                break;
            case ')':
                gotParen(ch);
                break;
            default:
                //1、如果當(dāng)前解析的字符是操作數(shù)，則直接壓入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){//如果當(dāng)前運(yùn)算符比s1棧頂運(yùn)算符優(yōu)先級高，則將運(yùn)算符壓入s1
                    s1.push(opTop);
                    break;
                }else{//如果當(dāng)前運(yùn)算符與棧頂運(yùn)算符相同或者小于優(yōu)先級別，那么將S1棧頂?shù)倪\(yùn)算符彈出并壓入到S2中
                    //并且要再次再次轉(zhuǎn)到while循環(huán)中與 s1 中新的棧頂運(yùn)算符相比較；
                    s2.push(opTop);
                }
            }
        }//end while
        //如果s1為空，則直接將當(dāng)前解析的運(yùn)算符壓入s1
        s1.push(opThis);
    }
    //當(dāng)前字符是 ')' 時，如果棧頂是'(',則將這一對括號丟棄，否則依次彈出s1棧頂?shù)淖址?，壓入s2，直到遇到'('
    public void gotParen(char ch){
        while(!s1.isEmpty()){
            char chx = s1.pop();
            if(chx == '('){
                break;
            }else{
                s2.push(chx);
            }
        }
    }
}

三、測試

@Test
public 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();
}

四、結(jié)果　　

五、分析　　

②、計算機(jī)如何實(shí)現(xiàn)后綴表達(dá)式的運(yùn)算？　　

4、前綴表達(dá)式

前綴表達(dá)式，指的是不包含括號，運(yùn)算符放在兩個運(yùn)算對象的前面，嚴(yán)格從右向左進(jìn)行（不再考慮運(yùn)算符的優(yōu)先規(guī)則），所有的計算按運(yùn)算符出現(xiàn)的順序。

注意：后綴表達(dá)式是從左向右解析，而前綴表達(dá)式是從右向左解析。

①、如何將中綴表達(dá)式轉(zhuǎn)換為前綴表達(dá)式？　　

②、計算機(jī)如何實(shí)現(xiàn)前綴表達(dá)式的運(yùn)算？　　

看完了這篇文章，相信你對“Java數(shù)據(jù)結(jié)構(gòu)和算法之前綴、中綴和后綴表達(dá)式的示例分析”有了一定的了解，如果想了解更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！