计算器思想-中缀表达式转化为后缀表达式

转载作者：我是一只小鸟更新时间：2023-09-15 07:01:55

计算机思维和人的思维的不同

对于一个算式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;
    }
}

在获取数据时，巧妙的使用正则获取对应的数据，利于数据的处理。

最后此篇关于计算器思想-中缀表达式转化为后缀表达式的文章就讲到这里了,如果你想了解更多关于计算器思想-中缀表达式转化为后缀表达式的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

文章推荐：文心一言VS讯飞星火VSchatgpt（93）--算法导论9.21题

文章推荐：聊聊神经网络的基础知识

java - 为什么有前缀/后缀++而没有前缀/后缀+=？
这似乎是一个愚蠢的问题，但为什么在许多语言中存在 ++ 和 -- 运算符的前缀和后缀版本，但是没有类似 += 或 -= 等其他运算符的前缀/后缀版本？例如，如果我能写出这段代码: myArray[x+
Cmake 库前缀/后缀
我需要链接到第三方预建共享库。在 Windows 上，这意味着与 Third_party.lib 链接，在 Linux/Android 上，这意味着与 libThird_party.so 链接。所以为
C++ 运算符重载前缀/后缀
我正在学习 C++ 中的运算符重载。原始后缀++ 的特性是它的优先级低于赋值运算符。例如，int i=0, j=0; i=j++; cout using namespace std; class V
javascript - 如何使用javascript为每行文本添加前缀/后缀？
如何在文本区域中添加每行前缀.. 示例: 这是文本区域的内容: hello124 我想为每一行添加一个 [b] 前缀和后缀，这样当我点击一个按钮时，结果将是: [b]hello[/b] [b]124[
algorithm - 逆波兰表示法中的变长运算符(后缀)
背景:在传统的逆波兰表示法中，所有运算符都必须具有固定长度，这使得 RPN 可以很容易地被代码评估和操作，因为每个标记、表达式和子表达式都是“自包含”的，以至于人们可以盲目地替换 y在 x y *为
javascript - 如何在自定义JQuery中添加日期原始/后缀？
我有以下旨在修改日期格式的Javascript，但是我想添加原始日期或后缀，例如“st”，“nd”，“rd”，“th”到每个结束日期编号。例如，假设我们当前的日期设置为 4 月 28 日，但我想将日期
后缀 header 检查多个操作
我想制定一个 header 检查规则来添加回复并将“发件人”更改为“不回复”。我将它用于某种扩散列表地址我试过这个正则表达式代码，但它不起作用: if !/^From:(.+@myserver\.f
r - 使用列名称为列内容添加前缀/后缀
我想改变数据框的列内容，以便单元格内容以列名作为前缀: > x x VarX VarY 1 A C 2 B D 3 A C 4 B D > x$V
Java DNS 后缀
当我执行 ipconfig/all 时，我看到 DNS 后缀搜索列表。我需要从 java 中检索该值。有谁知道如何获得它或它从哪里来？最佳答案 DNS 后缀列表读取自 HKLM\SYSTEM\Cur
c# - 类的前缀/后缀
当您编写一个包含大量类的应用程序时，您是否为类名使用了前缀/后缀？还是我应该只依赖我已经定义的 namespace ？在我的例子中，我有这样的类: Blur Contrast Sharpen Inv
html - 更改编号列表中的十进制前缀/后缀
大多数浏览器会像这样显示有序列表: 1. foo 2. bar 3. baz 有没有办法更改编号以改为使用前缀: #1 foo #2 bar #3 baz 最佳答案这是我能想到的最好的，你只在 Fi
Linux:按名称顺序批量重命名多个文件到父目录+后缀
我需要批量重命名多个图像，并希望使用父目录作为基本名称。为防止一个覆盖另一个，必须添加后缀。重命名过程的顺序必须遵循文件的时间戳。因为“第一个”文件是我正在使用它的网站的特色图片。树: └── ma
linux - 替换部分正则表达式并保留前缀/后缀
我试图使用 sed 替换文件中的一些字符串，但遇到了一个问题。我有以下字符串: TEMPLATE_MODULE TEMPLATE_SOME_ERR TEMPLATE_MORE_ERR 我想用一些字符
c - 后缀/前缀运算符优先级和结合性
我对后缀/前缀运算符的优先级和关联性感到困惑。一方面，当我阅读 K&R 书时，它指出: (*ip)++ The parentheses are necessary in this last ex
algorithm - 所有节点图算法的最小前缀/后缀
我有一个具有以下结构的图 V = {A1, A2, A3, A4, A5, .., An} E = {E1, E2, E3, E4, .., Ek} 现在我们定义A1的后缀: S(A1) = {All
java - 后缀 'f'在Java代码中是什么意思？
这是解释性代码。语言是Java，代码使用Android。 fg.setTextSize(height*0.50f); //<-'f' is in the brackets 或 @Override pr
mysql - 在数据库中存储邮件的最佳方式(后缀)
关闭。这个问题是off-topic .它目前不接受答案。想改进这个问题吗？ Update the question所以它是on-topic用于堆栈溢出。关闭 9 年前。 Improve this
c++后缀/前缀运算符重载为非成员函数
我正在编写自己的数组类作为练习。因为，我读到非成员函数实际上在某些方面比成员函数更好。( Scott Meyers ) 我正在尝试编写尽可能多的运算符重载作为非成员函数。运算符重载 + , - 作为非
c - 后缀、中缀和前缀表示法的解释
谁能解释一下关于 C 编程语言的中缀、后缀和前缀表示法是什么？最佳答案这是对 three terms, and how they apply 的一个很好的讨论. C 语言几乎到处都使用中缀表示法。
javascript - 为输入标签的值添加前缀/后缀
我有这种情况:我需要在输入文本字段 (html) 中添加引号而不更改输入的值。我正在使用 angular，所以我使用 ngModel，它看起来像这样我希望输入字段显示“{{data}} 中的任何内

我是一只小鸟

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城