計算器思想-中綴表達式轉化為尾碼表達式

来源:https://www.cnblogs.com/prettyspider/archive/2023/09/14/17703787.html
-Advertisement-
Play Games

電腦思維和人的思維的不同 對於一個算式3+2*（4-3)/5 人的思維是根據括弧和符號優先順序，優先計算括弧中的數據，在進行乘法和除法，在處理加法運算 但是電腦的思維是線性的，電腦會按照算式的前後順序，從前往後進行運算，這樣會導致運算結果錯誤 電腦如何套用人的運算思維 想要讓電腦具有人的”思 ...


電腦思維和人的思維的不同

對於一個算式3+2*（4-3)/5
人的思維是根據括弧和符號優先順序，優先計算括弧中的數據，在進行乘法和除法，在處理加法運算
但是電腦的思維是線性的，電腦會按照算式的前後順序，從前往後進行運算，這樣會導致運算結果錯誤

電腦如何套用人的運算思維

想要讓電腦具有人的”思維“，就需要使用棧，將數據和運算符號之間的順序按照電腦可以理解的方式排列
想要改變規則，就需要將人理解的中綴表達式轉換為尾碼表達式
轉化的規則是：

  • 中綴表達式轉化成尾碼表達式
    1.遇到操作數直接放入到集合中
    2.遇到操作符
    2.1當棧為空，或棧頂元素為（，直接放入到棧中
    2.2當優先順序比棧頂元素高時，直接進棧
    2.3當優先順序小於等於棧頂元素，將棧頂元素出棧放入到集合中，再和棧頂元素比較
    3.遇到左右括弧
    3.1如果為左括弧，直接加入棧
    3.2如果為右括弧，依次將棧頂元素彈出，直到左括弧，並將左括弧彈出
    4.最後將棧頂元素依次彈出

中綴表達式轉換為尾碼表達式的過程

以運算算式 3-（4-3）/5*10
以中綴表達式表示為 3 - 4 - 3 / 5 * 10
尾碼表達式表示為 3 4 3 - 5 / 10 * -
其中涉及到了棧的入棧和出棧，

轉化過程：
1.先創建一個集合，用於記錄尾碼表達式，創建一個棧，用於記錄運算符
2.3進入集合，-進入棧 集合 3 棧 -
3.左括弧進棧 集合3 棧- （
4.4進入集合，-進入棧，與此時的棧頂元素比較，此時棧頂元素是左括弧，-直接放入棧中 集合3 4 棧 - （ -
5.3進入集合，-和棧頂元素比較，優先順序相等或者小於，將棧頂元素-彈出 集合中為 3 4 3 - 棧-（
6.右括弧進棧 將棧頂元素彈出，直到左括弧並彈出左括弧 集合3 4 3 - 棧-
7./進棧，優先順序大於-，直接進棧，5 進入集合 集合3 4 3 - 5 棧- /
8.*進棧，優先等於棧頂元素，彈出棧頂元素，10進入集合 集合 3 4 3 - 5 / 10 棧 - *
9.算式獲取完成，將棧中元素全部彈出 集合 3 4 3 - 5 / 10 * -

實現

整數算式運算

package com.prettyspider.calculate;

import java.util.*;


/**
 * @author prettyspider
 * @ClassName CalcInt
 * @description: 傳入整數運算字元串，計算其數值
 * @date 2023/9/11 6:21
 * @Version V1.0
 */

public class CalcInt {
    /**
     * 中綴表達式轉化成尾碼表達式
     * <p>
     * 1.遇到操作數直接放入到集合中
     * 2.遇到操作符
     * 2.1當棧為空，或棧頂元素為（，直接放入到棧中
     * 2.2當優先順序比棧頂元素高時，直接進棧
     * 2.3當優先順序小於等於棧頂元素，將棧頂元素出棧放入到集合中，再和棧頂元素比較
     * 3.遇到左右括弧
     * 3.1如果為左括弧，直接加入棧
     * 3.2如果為右括弧，依次將棧頂元素彈出，直到左括弧，並將左括弧彈出
     * 4.最後將棧頂元素依次彈出
     */
    public static void main(String[] args) {
        // 要傳入的運算字元串
        String s = "10+2*(3-4)+20*(3*4+3)/3+20";
        // 中綴表達式轉化成尾碼表達式
        List<String> list = inToPastExpression(s);
        // 計算
        int number = calc(list);
        System.out.println("計算的數值為"+number);
    }


    /**
     * 計算尾碼表達式
     * @param list 尾碼表達式集合
     * @return 傳入的整數運算字元串的計算數值
     */
    private static int calc(List<String> list) {
        // 創建棧，用於記錄數據
        Stack<String> stack = new Stack<>();
        for (String s : list) {
            // 1.放入 當是數值時，直接放入棧中
            if (s.matches("\\d+")) {
                stack.push(s);
            } else {
                // 2.去除 當是運算符時，再棧中取出兩個數，進行運算，並將運算之後的結果放入到棧中
                int num1, num2;
                switch (s) {
                    case "+":
                        num1 = Integer.parseInt(stack.pop());
                        num2 = Integer.parseInt(stack.pop());
                        stack.push(String.valueOf(num2 + num1));
                        break;
                    case "-":
                        num1 = Integer.parseInt(stack.pop());
                        num2 = Integer.parseInt(stack.pop());
                        stack.push(String.valueOf(num2 - num1));
                        break;
                    case "*":
                        num1 = Integer.parseInt(stack.pop());
                        num2 = Integer.parseInt(stack.pop());
                        stack.push(String.valueOf(num2 * num1));
                        break;
                    case "/":
                        num1 = Integer.parseInt(stack.pop());
                        num2 = Integer.parseInt(stack.pop());
                        stack.push(String.valueOf(num2 / num1));
                        break;
                }
            }
        }
        return Integer.parseInt(stack.pop());
    }


    /**
     * 將傳入的字元串進行切分，存放到集合中
     * @param str 傳入的算數字元串
     * @return 尾碼表達式集合
     */
    private static List<String> inToPastExpression(String str) {
        // 創建集合和棧
        List<String> list = new ArrayList<>();
        Stack<String> stack = new Stack<>();
        // 切分數據
        ArrayList<String> arr = cutString(str);
        for (int i = 0; i < arr.size(); i++) {
            //       * 1.遇到操作數直接放入到集合中
            String value = arr.get(i);
            if (value.matches("\\d+")) {
                list.add(value);
            }
            //      * 3.遇到左右括弧
            //      *      3.1如果為左括弧，直接加入群
            else if ("(".equals(value)) {
                stack.push(value);
            }
            //      *      3.2如果為右括弧，依次將棧頂元素彈出，直到左括弧，並將左括弧彈出
            else if (")".equals(value)) {
                while (!"(".equals(stack.peek())) {
                    list.add(stack.pop());
                }
                stack.pop();
            }
            //      * 2.遇到操作符
            else {
                //      *      2.1當棧為空，或棧頂元素為（，直接放入到棧中
                //      *      2.3當優先順序小於等於棧頂元素，將棧頂元素出棧放入到集合中，再和棧頂元素比較
                while (stack.size() != 0 && !judgeOperator(value, stack.peek())) {
                    list.add(stack.pop());
                }
                //      *      2.2當優先順序比棧頂元素高時，直接進棧
                stack.push(value);
            }
        }
        //      * 4.最後將棧頂元素依次彈出
        while (!stack.empty()) {
            list.add(stack.pop());
        }
        System.out.println(list);
        return list;
    }

    /**
     * 將運算字元切分切分成集合
     * @param str 待切分字元串
     * @return ArrayList<String> 被切分之後的字元串集合
     */
    private static ArrayList<String> cutString(String str) {
        String[] arr = new String[str.length()-1];
        // 為字元串數組賦初值
        for (int i = 0; i < arr.length; i++) {
            arr[i] = "";
        }
        int index = 0;
        arr[index] = String.valueOf(str.charAt(0));
        for (int i = 1; i < str.length(); i++) {
            // 1.是數值放入
            if (Character.isDigit(str.charAt(i))) {
                // 1.1並看其起一個數據是不是也數值，是數值，將其前一個數據*10+本身
                if (arr[index].matches("\\d+")) {
                    arr[index] = String.valueOf(Integer.parseInt(arr[index]) * 10 + Integer.parseInt(String.valueOf(str.charAt(i))));
                } else {
                    arr[++index] = String.valueOf(str.charAt(i));
                }
            } else {
                // 2.不是數值，直接加入到集合中
                arr[++index] = String.valueOf(str.charAt(i));
            }
        }
        // 去除null
        ArrayList<String> list = removeNull(arr);
        return list;

    }

    /**
     * 將字元串數組中為空的元素去除
     * @param arr 字元串數組
     * @return 去除控制的字元串集合
     */
    private static ArrayList<String> removeNull(String[] arr) {
        ArrayList<String> list = new ArrayList<>();
        for (String s : arr) {
            if (!"".equals(s)) {
                list.add(s);
            }
        }
        return list;
    }

    /**
     * 比較新舊操作符的權重，判斷是存放還是取出
     * @param s1 新的操作符
     * @param s2 舊的操作符
     * @return 新舊操作符的權重比較
     */
    private static boolean judgeOperator(String s1, String s2) {
        int num1 = 0, num2 = 0;
        switch (s1) {
            case "+":
            case "-":
                num1 = 1;
                break;
            case "*":
            case "/":
                num1 = 2;
                break;
        }
        switch (s2) {
            case "+":
            case "-":
                num2 = 1;
                break;
            case "*":
            case "/":
                num2 = 2;
                break;
        }
        // 判斷新舊操作符的優先順序
        if (num1 > num2) {
            return true;
        }
        return false;
    }
}

小數算式運算

小數運算要考慮小數點，相對於整數要比較的複雜
在獲取嫻熟時，需要對小數點的位置進行判斷，對小數點右邊的數據進行處理

package com.prettyspider.calculate;

import java.util.*;


/**
 * @author prettyspider
 * @ClassName CalcInt
 * @description: 傳入整數運算字元串，計算其數值
 * @date 2023/9/11 6:21
 * @Version V1.0
 */

public class CalcDouble {
    /**
     * 中綴表達式轉化成尾碼表達式
     * <p>
     * 1.遇到操作數直接放入到集合中
     * 2.遇到操作符
     * 2.1當棧為空，或棧頂元素為（，直接放入到棧中
     * 2.2當優先順序比棧頂元素高時，直接進棧
     * 2.3當優先順序小於等於棧頂元素，將棧頂元素出棧放入到集合中，再和棧頂元素比較
     * 3.遇到左右括弧
     * 3.1如果為左括弧，直接加入棧
     * 3.2如果為右括弧，依次將棧頂元素彈出，直到左括弧，並將左括弧彈出
     * 4.最後將棧頂元素依次彈出
     */
    public static void main(String[] args) {
        // 要傳入的運算字元串
        String s = "10.32*3.23+2.234";
        // 中綴表達式轉化成尾碼表達式
        List<String> list = inToPastExpression(s);
        // 計算
        double number = calc(list);
        System.out.println("計算的數值為"+number);
    }


    /**
     * 計算尾碼表達式
     * @param list 尾碼表達式集合
     * @return 傳入的整數運算字元串的計算數值
     */
    private static double calc(List<String> list) {
        // 創建棧，用於記錄數據
        Stack<String> stack = new Stack<>();
        for (String s : list) {
            // 1.放入 當是數值時，直接放入棧中
            if (s.matches("(\\d|\\.)+")) {
                stack.push(s);
            } else {
                // 2.去除 當是運算符時，再棧中取出兩個數，進行運算，並將運算之後的結果放入到棧中
                double num1, num2;
                switch (s) {
                    case "+":
                        num1 = Double.valueOf(stack.pop());
                        num2 = Double.valueOf(stack.pop());
                        stack.push(String.valueOf(num2 + num1));
                        break;
                    case "-":
                        num1 = Double.valueOf(stack.pop());
                        num2 = Double.valueOf(stack.pop());
                        stack.push(String.valueOf(num2 - num1));
                        break;
                    case "*":
                        num1 = Double.valueOf(stack.pop());
                        num2 = Double.valueOf(stack.pop());
                        stack.push(String.valueOf(num2 * num1));
                        break;
                    case "/":
                        num1 = Double.valueOf(stack.pop());
                        num2 = Double.valueOf(stack.pop());
                        stack.push(String.valueOf(num2 / num1));
                        break;
                }
            }
        }
        return Double.valueOf(stack.pop());
    }


    /**
     * 將傳入的字元串進行切分，存放到集合中
     * @param str 傳入的算數字元串
     * @return 尾碼表達式集合
     */
    private static List<String> inToPastExpression(String str) {
        // 創建集合和棧
        List<String> list = new ArrayList<>();
        Stack<String> stack = new Stack<>();
        // 切分數據
        ArrayList<String> arr = cutString(str);
        for (int i = 0; i < arr.size(); i++) {
            //       * 1.遇到操作數直接放入到集合中
            String value = arr.get(i);
            if (value.matches("(\\d|\\.)+")) {
                list.add(value);
            }
            //      * 3.遇到左右括弧
            //      *      3.1如果為左括弧，直接加入群
            else if ("(".equals(value)) {
                stack.push(value);
            }
            //      *      3.2如果為右括弧，依次將棧頂元素彈出，直到左括弧，並將左括弧彈出
            else if (")".equals(value)) {
                while (!"(".equals(stack.peek())) {
                    list.add(stack.pop());
                }
                stack.pop();
            }
            //      * 2.遇到操作符
            else {
                //      *      2.1當棧為空，或棧頂元素為（，直接放入到棧中
                //      *      2.3當優先順序小於等於棧頂元素，將棧頂元素出棧放入到集合中，再和棧頂元素比較
                while (stack.size() != 0 && !judgeOperator(value, stack.peek())) {
                    list.add(stack.pop());
                }
                //      *      2.2當優先順序比棧頂元素高時，直接進棧
                stack.push(value);
            }
        }
        //      * 4.最後將棧頂元素依次彈出
        while (!stack.empty()) {
            list.add(stack.pop());
        }
        return list;
    }

    /**
     * 將運算字元切分切分成集合
     * @param str 待切分字元串
     * @return ArrayList<String> 被切分之後的字元串集合
     */
    private static ArrayList<String> cutString(String str) {
        String[] arr = new String[str.length()-1];
        // 為字元串數組賦初值
        for (int i = 0; i < arr.length; i++) {
            arr[i] = "";
        }
        int index = 0;
        arr[index] = String.valueOf(str.charAt(0));
        for (int i = 1; i < str.length(); i++) {
            // 1.是數值放入
            if (Character.isDigit(str.charAt(i))|| ".".equals(String.valueOf(str.charAt(i)))) {
                // 1.1並看其起一個數據是不是也數值，是數值，將其前一個數據拼接
                if (arr[index].matches("(\\d|\\.)+")) {
                    arr[index] = arr[index] + str.charAt(i);
                } else {
                    arr[++index] = String.valueOf(str.charAt(i));
                }
            } else {
                // 2.不是數值，直接加入到集合中
                arr[++index] = String.valueOf(str.charAt(i));
            }
        }
        // 去除null
        ArrayList<String> list = removeNull(arr);
        return list;

    }

    /**
     * 將字元串數組中為空的元素去除
     * @param arr 字元串數組
     * @return 去除控制的字元串集合
     */
    private static ArrayList<String> removeNull(String[] arr) {
        ArrayList<String> list = new ArrayList<>();
        for (String s : arr) {
            if (!"".equals(s)) {
                list.add(s);
            }
        }
        return list;
    }

    /**
     * 比較新舊操作符的權重，判斷是存放還是取出
     * @param s1 新的操作符
     * @param s2 舊的操作符
     * @return 新舊操作符的權重比較
     */
    private static boolean judgeOperator(String s1, String s2) {
        int num1 = 0, num2 = 0;
        switch (s1) {
            case "+":
            case "-":
                num1 = 1;
                break;
            case "*":
            case "/":
                num1 = 2;
                break;
        }
        switch (s2) {
            case "+":
            case "-":
                num2 = 1;
                break;
            case "*":
            case "/":
                num2 = 2;
                break;
        }
        // 判斷新舊操作符的優先順序
        if (num1 > num2) {
            return true;
        }
        return false;
    }
}

在獲取數據時，巧妙的使用正則獲取對應的數據，利於數據的處理


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 個性404頁面HTML源碼分享
    分享的 HTML 與上圖內容一樣，需要修改的小伙伴可以自行修改內容。 <style><!-- @import url("https://fonts.googleapis.com/css?family=Share+Tech+Mono|Montserrat:700"); * { margin: 0; p ...
  • 熟練掌握並充分利用CSS3的新特性，持續更新中。。。
    介紹 ESLint 是一個根據方案識別並報告 ECMAScript/JavaScript 代碼問題的工具，其目的是使代碼風格更加一致並避免錯誤。在很多地方它都與 JSLint 和 JSHint 類似，除了： ESLint 使用 Espree 對 JavaScript 進行解析。 ESLint 在代碼 ...
  • 記錄--如何解決非同步請求中的返回值問題
    這裡給大家分享我在網上總結出來的一些知識，希望對大家有所幫助 在 Web 開發中，非同步請求是一個常見的操作。然而，在非同步請求中正確地獲取返回值卻可能會變得棘手。本文將介紹如何解決非同步請求中的返回值問題，並提供一種解決方案。 一、問題描述 在某個 Web 應用程式中，用戶遇到了無法正確獲取非同步請求返回 ...
  • JS基本原理：對象類型賦值和原生類型賦值
    介紹 在本文中，我試圖以最簡潔的方式來闡明JavaScript編程原理中對象類型賦值和原生類型賦值之間的區別，以及它們各自是如何工作的。這也是我希望在我的JavaScript編程生涯早期就已經理解的東西。 JS中的原生類型和對象類型 首先，讓我們回顧一下JavaScript中不同的原生類型和對象類型 ...
  • JS深入學習筆記 - 第二章.類和對象
    3.類和對象 3.1面向對象 這裡順帶提一句學習JAVA時，老師說的面向對象和麵向過程的區別： 面向過程：強調做什麼事情，具體什麼步驟。舉個把大象放進冰箱的例子： 打開冰箱門 把大象放進冰箱 關上冰箱門 面向對象：強調的是做動作的主體（稱之為對象） 冰箱：打開操作 冰箱：放的操作（放的可以是大象也可 ...
  • 【動畫進階】當路徑動畫遇到滾動驅動！
    我的小冊 《CSS 技術揭秘與實戰通關》上線了，想瞭解更多有趣、進階、系統化的 CSS 內容，可以猛擊 - LINK。 本文，我們將一起利用純 CSS，實現如下這麼個酷炫的效果： 在一年前，我介紹了 CSS 中非常新奇有趣的一個新特性 -- @scroll-timeline：革命性創新，動畫殺手鐧 ...
  • JS深入學習筆記 - 第一章.構造函數原型與原型鏈
    1.構造函數和原型 1.1 概述 在典型的 OOP語言中（如Java)，都存在類的概念，類就是對象的模板，對象就是類的實例，但在ES6之前，JS並沒有引入類的概念。 在ES6之前，對象不是基於類創建的，而是一種稱為構建函數的特殊函數來定義對象和它們的特征。 有三種創建對象的方式： 對象字面量（con ...
  • 2023年值得關註的6個開源日誌管理工具
    日誌管理包含日誌數據存儲、處理、分析和可視化，通過利用日誌管理工具，可以監控性能趨勢、解決問題、檢測異常並優化整體系統性能。 近年來，開源日誌管理解決方案在大家尋求靈活且經濟有效的方式來管理現代系統典型的大量日誌數據時，獲得了顯著的關註。這些工具為商業產品提供了有力的替代方案，使各種規模的企業都能有 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類