2022: 暴殺運算式, 腳踩逆波蘭的時候到了-有解無憂

前言

★ 這里是小冷的博客
? 優質技術好文見專欄
個人公眾號，分享一些技術上的文章，以及遇到的坑
當前系列：資料結構系列
源代碼 git 倉庫 ‘
資料結構代碼地址代碼Git 倉庫地址

認識運算式與逆波蘭計算器實作

什么是前綴，什么中綴，什么是后綴？（理論加舉例）

前綴

前綴運算式是一種沒有括號的算術運算式，與中綴運算式不同的是，其將運算子寫在前面，運算元寫在后面，為紀念其發明者波蘭數學家Jan Lukasiewicz，前綴運算式也稱為“波蘭式”，例如，- 1 + 2 3，它等價于1-(2+3)，

我們完成一個逆波蘭計算器，要求完成如下任務:

輸入一個逆波蘭運算式(后綴運算式)，使用堆疊(Stack), 計算其結果
支持小括號和多位數整數，因為這里我們主要講的是資料結構，因此計算器進行簡化，只支持對整數的計算，

中綴

（或中綴記法）是一個通用的算識訓邏輯公式表示方法，運算子是以中綴形式處于運算元的中間（例：3 + 4），中綴運算式是人們常用的算術表示方法，

與前綴運算式（例：+ 3 4）或后綴運算式（例：3 4 +）相比，中綴運算式不容易被計算機決議，但仍被許多程式語言使用，因為它符合人們的普遍用法，

與前綴或后綴記法不同的是，中綴記法中括號是必需的，計算程序中必須用括號將運算子和對應的運算元括起來，用于指示運算的次序，

例：

（1）8+4-6*2用后綴運算式表示為：

? 8 4+6 2*-

（2）2*（3+5）+7/1-4用后綴運算式表示為**：**

? 235+*71/+4-

后綴

這種表示方式把運算子寫在運算物件的后面，例如，把a+b寫成ab+，所以也稱為后綴式，這種表示法的優點是根據運算物件和算符的出現次序進行計算，不需要使用括號，也便于用械實作求值，對于運算式x:=(a+b)(c+d)，其后綴式為xab+cd+:=，

原運算式：a*(b*(c+d/e)-f)# /* # 為運算式結束符號*/

后綴式：abcde/+f-#

為運算子定義優先級：# ( + - * / **

-1 0 1 1 2 2 3

從原運算式求后綴式的規則為：

思路分析

例如: (3+4)×5-6 對應的后綴運算式就是 3 4 + 5 × 6 - , 針對后綴運算式求值步驟如下:

1．從左至右掃描，將 3 和 4 壓入堆疊；

2．遇到+運算子，因此彈出 4 和 3（4 為堆疊頂元素，3 為次頂元素），計算出 3+4 的值，得 7，再將 7 入堆疊；

3．將 5 入堆疊；

4．接下來是×運算子，因此彈出 5 和 7，計算出 7×5=35，將 35 入堆疊；

5．將 6 入堆疊；

6．最后是-運算子，計算出 35-6 的值，即 29，由此得出最終結果

代碼實作

    public static void main(String[] args) {
        //定義逆波蘭運算式
        //    測驗
        String suffixExpression = "3 4 + 5 * 6 -";
        //    思路
        //    1. 先將 3 4 + 5 * 6 - 方法哦 ArrayList中
        //    2. 將 Arraylist 傳遞一個方法 遍歷ArrayList 配合堆疊完成計算
        List<String> list = getListString(suffixExpression);
        System.out.println("rpnlist = " + list);
        int res = calculate(list);
        System.out.println("計算的結果是 = " + res);
    }

    /**
     * @author 冷環淵 Doomwatcher
     * @context: 將一個逆波蘭運算式的資料和運算子 依次放入Arraylist中
     * @date: 2021/12/25 18:09
     * @param suffixExpression
     * @return: java.util.List<java.lang.String> 將分割好的字符List 回傳
     */
    public static List<String> getListString(String suffixExpression) {
        //  分割字串 將后綴運算式的每一個字符取出
        String[] split = suffixExpression.split(" ");
        // 我們用list 來存盤分割出來的運算式，這樣之后我們就需要遍歷即可
        List<String> list = new ArrayList<>();

        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }
/**
     * @author 冷環淵 Doomwatcher
     * @context: 這個方法就是 逆波蘭運算式的運算處理方法
     *  * 實作思路 : 我們以 （3+4）*4-6 對應的后綴運算式 => 3 4 + 5 * 6 -
     *  * 1） 從左至右掃描，將3和4壓入堆疊
     *  * 2） 遇到+運算子號 因此彈出 4 和 3 （4為堆疊頂元素 3 為次頂元素） 計算出3+4的值，將計算的結果加入堆疊
     *  * 3） 將5 入堆疊
     *  * 4） 接下來將 * 是運算子 彈出 5和7 計算出 7*5  = 35 將結果入堆疊
     *  * 5） 將6 入堆疊
     * @date: 2021/12/25 18:14
     * @param ls
     * @return: int 回傳的是一個運算結果
     */
    public static int calculate(List<String> ls) {
        //創建堆疊 只需要一個堆疊即可
        Stack<String> stack = new Stack<>();
        //    遍歷處理
        for (String item : ls) {
            // 這里我們用正則運算式來取出數字 和符號 如果是數字進行處理，如果符號做另外的處理
            if (item.matches("\\d+")) {
                //匹配的是數字
                stack.push(item);
            } else {
                //    如果是符號就 pop出兩個數 運算之后結果入堆疊
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if ("+".equals(item)) {
                    res = num1 + num2;
                } else if ("-".equals(item)) {
                    res = num1 - num2;
                } else if ("*".equals(item)) {
                    res = num1 * num2;
                } else if ("/".equals(item)) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("運算子有誤");
                }
                //    把 res 入堆疊
                stack.push("" + res);
            }
        }
        //最后留在stack 中的資料是運算結果
        return Integer.parseInt(stack.pop());
    }

這里我們用list加堆疊的方式實作了運算式的運算

需要注意的幾點：

從中體會后綴運算式和中綴運算式的轉換
計算上，后綴與中綴的區別

中綴轉后綴運算式

大家看到，后綴運算式適合計算式進行運算，但是人卻不太容易寫出來，尤其是運算式很長的情況下，因此在開發中，我們需要將中綴運算式轉成后綴運算式，所以我們需要用代碼將中綴運算式處理成后綴運算式之后運算一勞永逸

思路

1.初始化兩個堆疊元素安撫堆疊 s1 和存盤中間結果的堆疊2
2.從左至右掃描中綴運算式
3.遇到運算元時將其壓入s2
4.遇到運算子時比較其與s1堆疊頂的運算子優先級別：
1，如果s1為空或者堆疊頂運算子為左括號（則直接將此運算子壓入堆疊
2.否則，若優先級別比堆疊頂運算子的高，也將運算子壓入s1
3.否則將s1堆疊頂的于是暖夫彈出并且壓入s2堆疊內再次轉到 4.1與s1新的扎你當運算子比較
5.遇到括號時：
1.如果是左括號（，則直接壓入s1
2.如果是右括號），則一次彈出s1堆疊頂的運算子，并且壓入s2，直到遇到左括號位置，此時將一對括號丟棄
6.重復步驟 2-5 直到運算式最右邊
7.將s1中剩余的運算子一次彈出并壓入s2
8.依次彈出s2中的元素并且輸出，結果逆序就是中綴運算式對應的后綴的運算式

思路舉例

將中綴運算式“1+((2+3)×4)-5”轉換為后綴運算式的程序如下

因此結果為 :“1 2 3 + 4 × + 5 –”

編碼

跟著思路來實作代碼

代碼實作

package com.hyc.DataStructure.Stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.Stack
 * @className: PolandExpression
 * @author: 冷環淵 doomwatcher
 * @description: TODO
 * 實作思路 : 我們以 （3+4）*4-6 對應的后綴運算式 => 3 4 + 5 * 6 -
 * 1） 從左至右掃描，將3和4壓入堆疊
 * 2） 遇到+運算子號 因此彈出 4 和 3 （4為堆疊頂元素 3 為次頂元素） 計算出3+4的值，將計算的結果加入堆疊
 * 3） 將5 入堆疊
 * 4） 接下來將 * 是運算子 彈出 5和7 計算出 7*5  = 35 將結果入堆疊
 * 5） 將6 入堆疊
 * 最后 是 - 運算子 計算出 35-6  = 29 由此得出最后的結果
 *
 * 使用技術 這里我們用 java給我們提供的 Stack 和 ArrayList組合來實作計算器
 * @date: 2021/12/25 18:00
 * @version: 1.0
 */
public class PolandExpression {
    public static void main(String[] args) {

        //定義中綴運算式 ，轉成后置運算式之后運算
        String expression = "1+((2+3)*4)-5";
        //拆成鏈表
        List<String> infixExpressionList = toinfixExpression(expression);
        System.out.println("中綴運算式對應的list=" + infixExpressionList);
        List<String> suffixexpression = parseSuffixExpressionList(infixExpressionList);
        System.out.println("后綴運算式對應的List" + suffixexpression);
        System.out.printf("expression=%d", calculate(suffixexpression));

        //定義逆波蘭運算式
        //    測驗
        String suffixExpression = "3 4 + 5 * 6 -";
        //    思路
        //    1. 先將 3 4 + 5 * 6 - 方法哦 ArrayList中
        //    2. 將 Arraylist 傳遞一個方法 遍歷ArrayList 配合堆疊完成計算
        List<String> list = getListString(suffixExpression);
        System.out.println("rpnlist = " + list);
        int res = calculate(list);
        System.out.println("計算的結果是 = " + res);
    }

    /**
     * @author 冷環淵 Doomwatcher
     * @context: 將 Arraylist[1,+,(,(,2,+,3,),*,4,),-,5]  轉化成  Arraylist[1,2,3,+,4,*,5,-]
     *  轉換思路：
     * 1. 初始化兩個堆疊 元素安撫堆疊 s1 和存盤中間結果的堆疊2
     * 2.從左至右掃描中綴運算式
     * 3.遇到運算元時 將其壓入s2
     * 4.遇到運算子時 比較其與s1堆疊頂的運算子優先級別：
     *  1，如果s1為空 或者堆疊頂運算子為左括號（ 則直接將此運算子壓入堆疊
     *  2.否則，若優先級別比堆疊頂運算子的高，也將運算子壓入s1
     *  3.否則 將s1堆疊頂的于是暖夫彈出并且壓入s2堆疊內 再次轉到 4.1與s1新的扎你當運算子比較
     * 5.遇到括號時：
     *  1.如果是左括號（ ，則直接壓入s1
     *  2.如果是右括號），則一次彈出s1堆疊頂的運算子，并且壓入s2，直到遇到左括號位置，此時將一對括號丟棄
     * 6.重復步驟 2-5 直到運算式最右邊
     * 7.將s1中剩余的運算子一次彈出并壓入s2
     * 8.依次彈出s2中的元素并且輸出，結果逆序就是中綴運算式對應的后綴的運算式
     *
     * @date: 2021/12/27 17:48
     * @param
     * @return: java.util.List<java.lang.String>
     */
    public static List<String> parseSuffixExpressionList(List<String> ls) {
        //    定義兩個堆疊
        /*符號堆疊*/
        Stack<String> s1 = new Stack<>();
        /* S2 思路說明
         * 這里我們使用堆疊 在轉換程序中我們不需要pop操作，而且這個s2 之后我們需要逆序輸出操作很麻煩
         * 于是這里使用List來當作 s2 的資料存盤結構
         * */
        List<String> s2 = new ArrayList<>();
        //    遍歷 ls
        for (String item : ls) {
            //  如果是一個數字 那么就加入 S2（這里我們字串加入 正則運算式來判斷是不是一個數字）
            if (item.matches("\\d+")) {
                s2.add(item);
            } else if (item.equals("(")) {
                s1.push(item);
            } else if (item.equals(")")) {
                //    如果是 ）右括號 則一次彈出 s1堆疊頂的運算子 并且壓入 s2 知道遇到左括號為止，完成前置的一系列操作之后將這一對括號丟棄
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                // 彈出（ 消除掉一組括號
                s1.pop();
            } else {
                /* 當 item 優先級小于等于s1 堆疊頂運算子的時候 將s1堆疊頂的運算子淡出并且加入到s2 中，再次重復思路中的第四個環節，與s1中的新堆疊頂運算子比較
                 *問題 我們缺少一個比較優先級高低的方法
                 * */
                while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
                    s2.add(s1.pop());
                }
                //    之后將 itea 壓入堆疊
                s1.push(item);
            }

        }
        //    將s1中剩余的運算子一次彈出加入s2
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        //    注意應為存放的是list 這里我們順序不需要改變 直接輸出就是對應的后綴運算式
        return s2;
    }

    /**
     * @author 冷環淵 Doomwatcher
     * @context: 將中綴運算式 轉換成對應的list
     * @date: 2021/12/27 17:32
     * @param s
     * @return: java.util.List<java.lang.String>
     */
    public static List<String> toinfixExpression(String s) {
        /*定義一個List 存放中綴運算式的對應內容*/
        List<String> ls = new ArrayList<>();
        //定義一個指標 用于遍歷 中綴運算式的字串
        int i = 0;
        // 用于拼接字串
        String str;
        //用于存放遍歷的字符
        char c;
        do {
            //   如果c是一個非數字 那么我們需要加入到 ls 中去 ，這里的判斷條件是 ASCLL值
            if ((c = s.charAt(i)) < 48 || ((c = s.charAt(i)) > 57)) {
                ls.add("" + c);
                //    指標后移
                i++;
            } else {
                /*
                 * 如果是一個數字 那么我們還需要考慮是不是多位數
                 * 這里我們將 str 置空
                 * */
                str = "";
                while (i < s.length() && (c = s.charAt(i)) >= 48 && ((c = s.charAt(i)) <= 57)) {
                    //拼接數字字串
                    str += c;
                    i++;
                }
                ls.add(str);
            }
        } while (i < s.length());

        return ls;

    }

    /**
     * @author 冷環淵 Doomwatcher
     * @context: 將一個逆波蘭運算式的資料和運算子 依次放入Arraylist中
     * @date: 2021/12/25 18:09
     * @param suffixExpression
     * @return: java.util.List<java.lang.String> 將分割好的字符List 回傳
     */
    public static List<String> getListString(String suffixExpression) {
        //  分割字串 將后綴運算式的每一個字符取出
        String[] split = suffixExpression.split(" ");
        // 我們用list 來存盤分割出來的運算式，這樣之后我們就需要遍歷即可
        List<String> list = new ArrayList<>();

        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }

    /**
     * @author 冷環淵 Doomwatcher
     * @context: 這個方法就是 逆波蘭運算式的運算處理方法
     *  * 實作思路 : 我們以 （3+4）*4-6 對應的后綴運算式 => 3 4 + 5 * 6 -
     *  * 1） 從左至右掃描，將3和4壓入堆疊
     *  * 2） 遇到+運算子號 因此彈出 4 和 3 （4為堆疊頂元素 3 為次頂元素） 計算出3+4的值，將計算的結果加入堆疊
     *  * 3） 將5 入堆疊
     *  * 4） 接下來將 * 是運算子 彈出 5和7 計算出 7*5  = 35 將結果入堆疊
     *  * 5） 將6 入堆疊
     * @date: 2021/12/25 18:14
     * @param ls
     * @return: int 回傳的是一個運算結果
     */
    public static int calculate(List<String> ls) {
        //創建堆疊 只需要一個堆疊即可
        Stack<String> stack = new Stack<>();
        //    遍歷處理
        for (String item : ls) {
            // 這里我們用正則運算式來取出數字 和符號 如果是數字進行處理，如果符號做另外的處理
            if (item.matches("\\d+")) {
                //匹配的是數字
                stack.push(item);
            } else {
                //    如果是符號就 pop出兩個數 運算之后結果入堆疊
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if ("+".equals(item)) {
                    res = num1 + num2;
                } else if ("-".equals(item)) {
                    res = num1 - num2;
                } else if ("*".equals(item)) {
                    res = num1 * num2;
                } else if ("/".equals(item)) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("運算子有誤");
                }
                //    把 res 入堆疊
                stack.push("" + res);
            }
        }
        //最后留在stack 中的資料是運算結果
        return Integer.parseInt(stack.pop());
    }
}

class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    //   寫一個方法 回傳對應的數字
    public static int getValue(String operation) {
        int result = 0;
        switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("不存在該運算子");
                break;

        }
        return result;
    }
}

總結

計算的思路和我們先前寫的逆波蘭計算器事一樣的
這里我們考慮中綴轉后綴的幾個要點，運算子優先級和運算子的位置
動手之后，debug看看堆疊和List的變化加深理解

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/401692.html

標籤：其他

上一篇：源火星球青龍羊毛簡易教學

下一篇：常見的一些易錯點

2022: 暴殺運算式, 腳踩逆波蘭的時候到了

前言

認識運算式與 逆波蘭計算器實作

什么是前綴，什么中綴，什么是后綴？（理論加舉例）

中綴轉后綴運算式

總結

認識運算式與逆波蘭計算器實作