Java中綴表達式轉(zhuǎn)后綴表達式流程詳解

更新時間：2022年09月24日 15:03:47 作者：小黎的培培筆錄

中綴表達式是一個通用的算術(shù)或邏輯公式表示方法。，中綴表達式不容易被計算機解析，但仍被許多程序語言使用，因為它符合人們的普遍用法。本文介紹了實現(xiàn)中綴表達式的方法，需要的可以參考一下

一、棧

1、棧的基本介紹

棧是?個先?后出的有序列表。棧(stack)是限制線性表中元素的插?和刪除只能在線性表的同?端進?的?種特殊線性表。允許插?和刪除的?端，為變化的?端，稱為棧頂(Top)，另?端為固定的?端，稱為棧底(Bottom)。

根據(jù)棧的定義可知，最先放?棧中元素在棧底，最后放?的元素在棧頂，?刪除元素剛好相反，最后放?的元素最先刪除，最先放?的元素最后刪除。

2、棧的底層實現(xiàn)

（1）創(chuàng)建一個類，模擬棧

maxSize ：棧的最大容量

top ：表示棧頂

stack ：數(shù)組用來存儲數(shù)據(jù)

public class Stacks {
    public int maxSize;
    public int top ;
    public int[] stack;
    //構(gòu)造器，傳入棧的最大容量
    public Stacks(int maxSize) {
        this.maxSize = maxSize;
        //初始化棧頂?shù)奈恢脼?1，?？?
        top = -1;
        //初始化數(shù)組，最大容量為棧的容量
        stack = new int[maxSize];
    }
}

（2）判斷?？蘸蜅M

??????? 棧滿

    //因為底層是數(shù)組存儲數(shù)據(jù)，所以索引從0開始，
    //判斷條件為 top == maxSize - 1
    public boolean isFull(){
        return top == maxSize - 1;
    }

? 棧空

    public boolean isEmpty(){
        return top == -1;
    }

（3）入棧操作

首先判斷是否棧滿，棧滿后則不能繼續(xù)添加，先對棧頂進行加一，然后再放入數(shù)據(jù)。

    public void push(int data){
        //判斷是否棧滿
        if (isFull()){
            System.out.println("棧滿，無法入棧");
            return;
        }
        top++;
        stack[top] = data;
    }

（4）出棧操作

首先判斷?？?，出棧操作其實就是將top減一即可，return stack[top--]; 這樣操作是為了讓我們知道出棧的數(shù)據(jù)是什么。

    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("?？?，無法出棧！");
        }
        //先出棧，后減減
        return stack[top--];
    }

（5）顯示棧數(shù)據(jù)

  public void show(){
        if (isEmpty()){
            System.out.println("棧空，無法顯示！");
            return;
        }
        for (int i = top ; i >= 0; i--){
            System.out.printf("stack[%d] = %d\n", i , stack[i]);
        }
    }

二、中綴表達式轉(zhuǎn)后綴表達式

1、拆解中綴表達式

首先將中綴表達式拆解成一個一個的字符，存放到集合中，方便后面我們將中綴轉(zhuǎn)后綴時的遍歷操作。

首先用split分割操作將原數(shù)據(jù)分割到數(shù)組中存放，然后用增強for循環(huán)遍歷并同時存放到創(chuàng)建好的stringList集合中。

    public static List<String> endList(String s){
        String[] s1 = s.split("");
        List<String> stringList = new ArrayList<>();
        for (String s2 : s1) {
            stringList.add(s2);
        }
        return stringList;
    }

補充運算符優(yōu)先級的判斷

后面我們轉(zhuǎn)換成后綴表達式時，需要判斷運算符的優(yōu)先級。

  public static int Calcu(String s){
        char ch = s.charAt(0);
        if (ch == '-' || ch == '+'){
            return 0;
        } else if (ch == '*' || ch == '/') {
            return 1;
        }
        return -1;
    }

2、中綴轉(zhuǎn)后綴的算法

初始化兩個棧:運算符棧s1和儲存中間結(jié)果的棧s2
從左至右掃描中綴表達式
遇到操作數(shù)時，將其壓s2
遇到運算符時, 比較其與s1棧頂運算符的優(yōu)先級

?如果s1為空，或棧頂運算符為左括號“(”，則直接將此運算符入棧

?否則，若優(yōu)先級比棧項運算符的高，也將運算符壓入s1

?否則,將s1棧頂?shù)倪\算符彈出并壓入到s2中 ,再次與s1中新的棧頂運算符相比較

遇到括號時:

? 如果是左括號“(”，則直接壓入s1

? 如果是右括號“)”，則依次彈出s1棧頂?shù)倪\算符, 并壓入s2，直到遇到左括號為止，此時將這一對括號丟棄

重復(fù)步驟2至5,直到表達式的最右邊
將s1中剩余的運算符依次彈出并壓入s2
依次彈出s2中的元素并輸出，結(jié)果的逆序即為中綴表達式對應(yīng)的后綴表達式

3、中綴轉(zhuǎn)后綴代碼解析

前面的算法說到，首先創(chuàng)建兩個棧一個運算符棧和一個中間結(jié)果棧，但是根據(jù)上面算法的介紹，中間結(jié)果棧沒有出棧操作，就是數(shù)據(jù)全部是存入，于是在寫代碼的時候我們可以將中間結(jié)果棧換成集合來存放數(shù)據(jù)。

首先用增強for循環(huán)遍歷原數(shù)據(jù)集合，然后進行判斷，如果是數(shù)字就放入右方的集合中，如果是運算符就放入左方的符號棧中。

進行運算符判斷，如果是左括號“（ ” 就直接放入符號棧中，如果是右括號“ ）”，就取出符號棧棧頂?shù)姆柗湃爰现?，直到遇到左括?ldquo;（ ”，停止將棧頂?shù)姆柗湃爰现校藭r將棧頂出棧也就是去掉括號。

然后繼續(xù)進行遍歷放入數(shù)據(jù)和符號，如果是符號，就與符號棧的棧頂?shù)姆栠M行比較，要放入運算符的運算級如果小于等于棧頂運算符的運算級，就將棧頂?shù)倪\算符放入集合中，但下面的圖中，運算符為括號，所以不用管，因為括號有單獨的判斷條件，所以直接放入。

遇到右括號又繼續(xù)重復(fù)前面的操作。

放入運算符的優(yōu)先級小于等于棧頂運算符的優(yōu)先級，于是將棧頂?shù)倪\算符放入集合中，然后放入的運算符繼續(xù)放入符號棧中。

最后循環(huán)結(jié)束，將符號棧中的運算符依次放入到集合中。

public static List<String> MiddleToEndExpress(List<String> strings){
        //創(chuàng)建棧，存放運算符
        Stack<String> operStack = new Stack<>();
        //因為這個棧不需要出棧，所以使用集合
        List<String> sumList = new ArrayList<>();
        for (String s : strings) {
            //判斷是否是數(shù)據(jù)
            if (s.matches("\\d+")){
               sumList.add(s);//是數(shù)據(jù)直接加入
            }else if (s.equals("(")){//判斷是否是左括號
                operStack.push(s);//是，直接放入符號棧
            }else if (s.equals(")")){//判斷是否是右括號
                while (!operStack.peek().equals("(")){//如果棧頂是左括號，退出循環(huán)
                    sumList.add(operStack.pop());//不是左括號，就將棧頂?shù)姆栆来畏湃爰?
                }
                //循環(huán)結(jié)束，表示棧頂是左括號，把左括號去掉，就去掉了一對括號
                operStack.pop();
            }else {//前面的判斷都不是，那就是運算符
               //如果符號棧為空，并且運算符小于等于棧頂?shù)倪\算符優(yōu)先級
                while (operStack.size() != 0 && Calcu(s) <= Calcu(operStack.peek())){
                    //就將棧頂?shù)倪\算符放入集合中
                    sumList.add(operStack.pop());
                }
                //然后將符號放入符號棧中
                operStack.push(s);
            }
        }
        //遍歷結(jié)束，將符號棧剩余的符號依次取出放入集合中
        while (operStack.size() != 0){
            sumList.add(operStack.pop());
        }
        //最后將集合返回
        return sumList;
    }

最后結(jié)果為：結(jié)果中不能含括號，否則轉(zhuǎn)換錯誤！

4、對后綴表達式進行計算

前面我們已經(jīng)將中綴轉(zhuǎn)成后綴表達式了，那么我們只需要直接計算了，首先還是遍歷我們的集合（存放后綴表達式的）將數(shù)據(jù)暫時放入棧中方便我們操作，然后在遍歷過程中進行判斷，如果是數(shù)據(jù)就直接放入棧中，如果是運算符就從棧中取出兩個數(shù)據(jù)進行運算，運算結(jié)果又放入棧中，直到棧中只存在一個數(shù)據(jù)時，就是最后的運算結(jié)果。

public static int endCalculator(List<String> stringList){
        //創(chuàng)建棧，存放數(shù)據(jù)
        Stack<String> dataStack = new Stack<>();
        //循環(huán)遍歷集合
        for (String s : stringList) {
            //正則表達式判斷是否是數(shù)據(jù)，如果是，就放入棧中
            if (s.matches("\\d+")){
                dataStack.push(s);
            }else {//否則就是運算符
                //取出兩個數(shù)據(jù)
                int num1 = Integer.parseInt(dataStack.pop());
                int num2 = Integer.parseInt(dataStack.pop());
                //存放運算結(jié)果的變量
                int res = 0;
                //判斷運算符繼續(xù)相應(yīng)的運算
                if (s.equals("+")){
                    res = num1 + num2;
                }else if (s.equals("-")) {
                    res = num2 - num1;
                }else if (s.equals("*")) {
                    res = num1 * num2;
                }else if (s.equals("/")) {
                    res = num2 / num1;
                }else {
                    throw new RuntimeException("運算符異常！");
                }
                //運算過后將結(jié)果又放入棧中
                dataStack.push("" + res);
            }
        }
        //最后返回棧中唯一的數(shù)據(jù)既是結(jié)果
        return Integer.parseInt(dataStack.pop());
    }

到此這篇關(guān)于Java中綴表達式轉(zhuǎn)后綴表達式流程詳解的文章就介紹到這了,更多相關(guān)Java中綴表達式內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: