Java中綴表達式怎么轉后綴表達式

這篇文章主要介紹“Java中綴表達式怎么轉后綴表達式”，在日常操作中，相信很多人在Java中綴表達式怎么轉后綴表達式問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Java中綴表達式怎么轉后綴表達式”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

一、棧

1、棧的基本介紹

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

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

2、棧的底層實現

（1）創建一個類，模擬棧

maxSize ：棧的最大容量

top ：表示棧頂

stack ：數組用來存儲數據

public class Stacks {
    public int maxSize;
    public int top ;
    public int[] stack;
    //構造器，傳入棧的最大容量
    public Stacks(int maxSize) {
        this.maxSize = maxSize;
        //初始化棧頂的位置為-1，棧空
        top = -1;
        //初始化數組，最大容量為棧的容量
        stack = new int[maxSize];
    }
}

（2）判斷棧空和棧滿

? 棧滿

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

? 棧空

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

（3）入棧操作

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

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

（4）出棧操作

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

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

（5）顯示棧數據

  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]);
        }
    }

二、中綴表達式轉后綴表達式

1、拆解中綴表達式

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

首先用split分割操作將原數據分割到數組中存放，然后用增強for循環遍歷并同時存放到創建好的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;
    }

補充運算符優先級的判斷

后面我們轉換成后綴表達式時，需要判斷運算符的優先級。

  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、中綴轉后綴的算法

• 初始化兩個棧:運算符棧s1和儲存中間結果的棧s2

• 從左至右掃描中綴表達式

• 遇到操作數時，將其壓s2

•  遇到運算符時, 比較其與s1棧頂運算符的優先級

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

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

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

• 遇到括號時:

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

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

• 重復步驟2至5,直到表達式的最右邊

• 將s1中剩余的運算符依次彈出并壓入s2

• 依次彈出s2中的元素并輸出，結果的逆序即為中綴表達式對應的后綴表達式

3、中綴轉后綴代碼解析

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

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

進行運算符判斷，如果是左括號“（ ” 就直接放入符號棧中，如果是右括號“ ）”，就取出符號棧棧頂的符號放入集合中，直到遇到左括號“（ ”，停止將棧頂的符號放入集合中，此時將棧頂出棧也就是去掉括號。

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

遇到右括號又繼續重復前面的操作。

放入運算符的優先級小于等于棧頂運算符的優先級，于是將棧頂的運算符放入集合中，然后放入的運算符繼續放入符號棧中。

最后循環結束，將符號棧中的運算符依次放入到集合中。

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

最后結果為：結果中不能含括號，否則轉換錯誤！

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

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

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

到此，關于“Java中綴表達式怎么轉后綴表達式”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！