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

来源: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
  • WPF 已知問題 監聽 WMI 事件導致觸摸失效
    示例項目結構 在 Visual Studio 中創建一個 WinForms 應用程式後，項目結構如下所示： MyWinFormsApp/ │ ├───Properties/ │ └───Settings.settings │ ├───bin/ │ ├───Debug/ │ └───Release/ ...
  • [STAThread]特性
    [STAThread] 特性用於需要與 COM 組件交互的應用程式，尤其是依賴單線程模型（如 Windows Forms 應用程式）的組件。在 STA 模式下，線程擁有自己的消息迴圈，這對於處理用戶界面和某些 COM 組件是必要的。 [STAThread] static void Main(stri ...
  • UWP WinUI3 傳入 AddHandler 的 RoutedEventHandler 類型與事件所需不匹配將拋出參數異常
    在WinForm中使用全局異常捕獲處理 在WinForm應用程式中，全局異常捕獲是確保程式穩定性的關鍵。通過在Program類的Main方法中設置全局異常處理，可以有效地捕獲並處理未預見的異常，從而避免程式崩潰。 註冊全局異常事件 [STAThread] static void Main() { / ...
  • .NET 多版本 WinForm 開源控制項庫 SunnyUI
    前言 給大家推薦一款開源的 Winform 控制項庫，可以幫助我們開發更加美觀、漂亮的 WinForm 界面。 項目介紹 SunnyUI.NET 是一個基於 .NET Framework 4.0+、.NET 6、.NET 7 和 .NET 8 的 WinForm 開源控制項庫，同時也提供了工具類庫、擴展 ...
  • .net core8 使用Swagger（附當前源碼）
    說明 該文章是屬於OverallAuth2.0系列文章，每周更新一篇該系列文章（從0到1完成系統開發）。 該系統文章，我會儘量說的非常詳細，做到不管新手、老手都能看懂。 說明：OverallAuth2.0 是一個簡單、易懂、功能強大的許可權+可視化流程管理系統。 有興趣的朋友，請關註我吧(*^▽^*) ...
  • WPF 什麼時候 VisualTreeHelper.GetDescendantBounds 將返回無窮大
    一、下載安裝 1.下載git 必須先下載並安裝git，再TortoiseGit下載安裝 git安裝參考教程：https://blog.csdn.net/mukes/article/details/115693833 2.TortoiseGit下載與安裝 TortoiseGit，Git客戶端，32/6 ...
  • C# 開源教程帶你輕鬆掌握數據結構與演算法
    前言 在項目開發過程中，理解數據結構和演算法如同掌握蓋房子的秘訣。演算法不僅能幫助我們編寫高效、優質的代碼，還能解決項目中遇到的各種難題。 給大家推薦一個支持C#的開源免費、新手友好的數據結構與演算法入門教程：Hello演算法。 項目介紹 《Hello Algo》是一本開源免費、新手友好的數據結構與演算法入門 ...
  • 第22篇 生成proto文件bat腳本
    1.生成單個Proto.bat內容 @rem Copyright 2016, Google Inc. @rem All rights reserved. @rem @rem Redistribution and use in source and binary forms, with or with ...
  • 記一次 .NET某上位機視覺程式 卡死分析
    一：背景 1. 講故事 前段時間有位朋友找到我，說他的窗體程式在客戶這邊出現了卡死，讓我幫忙看下怎麼回事？dump也生成了，既然有dump了那就上 windbg 分析吧。 二：WinDbg 分析 1. 為什麼會卡死 窗體程式的卡死，入口門檻很低，後續往下分析就不一定了，不管怎麼說先用 !clrsta ...
  • 醫學DICOM文件與PACS系統進行數據傳輸
    前言 人工智慧時代，人臉識別技術已成為安全驗證、身份識別和用戶交互的關鍵工具。 給大家推薦一款.NET 開源提供了強大的人臉識別 API，工具不僅易於集成，還具備高效處理能力。 本文將介紹一款如何利用這些API，為我們的項目添加智能識別的亮點。 項目介紹 GitHub 上擁有 1.2k 星標的 C# ...
所有分類