0
0

Java数据结构-中缀转后缀与逆波兰表达式及其计算器完整版[面试必备] 看完对于你而言,有手就行(超长,超带劲)

前言:

    本系列博客中,主要是对常用的数据结构进行讲解,本篇博客主要讲解的是**逆波兰计算器的完整版**的实现.因为逆波兰计算机涉及到的概念和转换较多,本篇博客会较以前更长,旨在更好的服务读者!

** 传统技能:应用场景-->代码思路-->具体做法-->代码实现-->代码分析-->总结**

** * 在应用场景后,我会详细说明什么是逆波兰表达式,波兰表达式,转换规则等***

应用场景:

    逆波兰计算器主要运用于对表达式求值问题的解决,如上篇博客的中缀表达式计算器一样,都具有相同的功能,但是,逆波兰计算器却有无可比拟的优点.

逆波兰计算器的优点:

  • 逆波兰计算器的逻辑更加简单
  • 逆波兰计算器不涉及优先级问题
  • 逆波兰计算器更"好写"

相关概念

波兰表达式

    波兰表达式又被称为前缀表达式,即运算符都在操作数之前

如"+12"

逆波兰表达式

    逆波兰表达式又被成为后缀表达式,即运算符都在操作数之后

如"12+"

中缀表达式

    最传统的表达式,即运算符都在操作数之间

如"1+2"

代码思路

逆波兰表达式计算

  • 建立一个栈,用于专门存放数字
  • 建立一个索引,从左到右去扫描表达式
  • 若扫描到了数字,则直接放入栈中
  • 若扫描到了运算符,则在栈中弹出栈顶元素和次顶元素,并结合运算符进行运算,将结果压回栈中
  • 减法和除法是栈顶元素-/次顶元素

波兰表达式计算

  • 建立一个栈,用于专门存放数字
  • 建立一个索引,从右向左扫描表达式
  • 如果扫描到了数字,则直接压栈
  • 若扫描到了运算符,则将栈中的栈顶元素和次顶元素弹出,并结合运算符进行运算,并将结果压回
  • 减法和除法是**次顶元素-/栈顶元素 **

区别

  1. 扫描顺序不同
  2. 运算顺序不同

中缀表达式转化成逆波兰表达式 (实际操作有所不同)

  • 1.创建两个栈,第一个栈是专门用于存放运算符,第二个栈专门用于存放中间结果
  • 2.建立一个索引,从左到右遍历中缀表达式,如果发现是数字,则直接压入第二个栈中
  • 3.1如果发现是符号,且第一个栈为空或者栈顶符号为左括号"(",则直接压入第一个栈
  • 3.2如果栈不为空,则比较优先级,若优先级比栈顶元素高,则直接压入,否则将栈顶元素弹栈,并压入第二个栈,重复以上操作,知道该运算符被压入为止
  • 4.1若符号是左括号"(",直接压入
  • 4.2若符号是右括号")"则两个括号之间的元素依次弹出,并压入第二个栈
  • 5.重复2-4的操作,直至扫描完中缀表达式
  • 6.将剩余符号全部依次压入第二个栈
  • 7.逆序输出栈的元素就是后缀表达式

具体操作+代码实现(含代码分析)

  • 创建一个方法,将中缀表达式转换成集合
public static List<String> toInfixList(String str) {
        var list = new ArrayList<String>();
        var strbuf = new StringBuffer();
        var ch = '\u0000';
        for (int index = 0; index < str.length(); index++) {
            ch = str.charAt(index);
//如果遍历到了下面这些间隔符,直接下一次循环,目的是提高程序的健壮性
            if(ch == ' ' || ch == '\t' || ch == '\n') {
                continue;
            }
//通过ASCII码去判断是否为符号,特别的是!= . 是用于去除小数点的,否则下面的数字不会有小数
            if(ch > 57 || ch < 48 && ch != '.') {
                list.add(String.valueOf(ch));
            }else {
//delete的目的是由于上一次已经有字符串.若再拼接则是上次的数字+这次的数字,会出错
                strbuf.delete(0,strbuf.length());
                strbuf.append(ch);
//index + 1 < str.length() 的目的是防止下标越界异常
//而且要放在第一位,放在后面短路与的保护作用就会丧失
                while((index + 1 < str.length()) && ((str.charAt(index + 1)) <= 57 && (str.charAt(index + 1)) >= 48 || (str.charAt(index + 1) == '.'))) {
                    strbuf.append(str.charAt(++index));
                }
                list.add(strbuf.toString());
            }
        }
        return list;
    }
  1. 第一步就是创建一个集合,用于存储取出来的元素,泛型应该被指定为String,后面有用
  2. StringBuffer的作用是做字符串拼接,用于解决多位数和小数的问题
  3. 通过循环,用index去遍历,调用charAt()方法,将对应下标的字符取出放入ch中
  4. 如果ch是运算符,直接放入集合中(不需要有任何操作)
  5. 如果ch是数字,则要考虑是否是多位数或者是小数.如果是则要字符串拼接
  • 创建一个方法,将中缀表达式的集合转化成后缀表达式的集合
public static List<String> toSuffixList(List<String> list) {
        var s1 = new Stack<String>();
        var resList = new ArrayList<String>();
        for(var item : list) {
//运用了正则表达式,可暂时不管,只需知道只要是数字就能为true
            if(item.matches("^\\d+(\\.\\d+)?")) {
                resList.add(item);
            }else {
                if(item.equals("(")) {
                    s1.push(item);
                }else if(item.equals(")")) {
                    while (!s1.peek().equals("(")) {
                        resList.add(s1.pop());
                    }
//这里弹栈的目的是,把左括号弹出去
                    s1.pop();
                } else {
//这里是比较优先级,只要优先级小于等于栈顶元素.就将栈顶元素弹栈,继续比较
                    while(!s1.isEmpty()) {
                        if(Operation.getPriority(s1.peek()) >= Operation.getPriority(item)){
                            resList.add(s1.pop());
                        }else {
                            break;
                        }
                    }
                    s1.push(item);
                }
            }
        }
        while(!s1.isEmpty()) {
            resList.add(s1.pop());
        }
        return resList;
    }
  1. 第一步是创建一个栈和一个集合,因为第二个栈只有压栈不弹栈,为了方便,直接创建集合
  2. 根据思路完成代码即可
  • 补充上述的一个判断优先级的类
public class Operation {
    private static final int ADD = 1;
    private static final int SUB = 1;
    private static final int MUL = 2;
    private static final int DIV = 2;
    private static final int OTHER = 0;

    public static int getPriority(String s) {
        return switch (s) {
            case "+" -> ADD;
            case "-" -> SUB;
            case "*" -> MUL;
            case "/" -> DIV;
            default -> OTHER;
        };
    }
}
  1. 通过数字映射优先级大小
  2. OTHER的存在解决了只要是左括号直接压栈这一个步骤
  • 创建一个方法,是真正的逆波兰计算机的方法
public static double cal(List<String> list) {
        var stack = new Stack<String>();
        var num1 = 0.0;
        var num2 = 0.0;
        var res = 0.0;
        for (var item : list) {
            if(item.matches("\\d+(\\.\\d+)?")){
                stack.push(item);
            }else {
                num1 = Double.parseDouble(stack.pop());
                num2 = Double.parseDouble(stack.pop());
                switch (item) {
                    case "+" -> res = num1 + num2;
//次顶元素-栈顶元素的理解
                    case "-" -> res = num2 - num1;
                    case "*" -> res = num1 * num2;
                    case "/" -> res = num2 / num1;
                }
//转化为String类型重新压入栈中
                stack.push(res + "");
            }
        }
        return Double.parseDouble(stack.pop());
    }
  1. double类型的定义是为了适应小数运算,var是局部变量类型推断,评论区留言我可以专门写一篇博客
  2. 栈的泛型应该是String,对小数有好处

完整代码:

package datastructure.chapter02.stack.poland;

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

public class CalculatorDemo {
    public static void main(String[] args) {
        System.out.println(cal(toSuffixList(toInfixList("11.1 + 11.1"))));
    }

    public static List<String> toInfixList(String str) {
        var list = new ArrayList<String>();
        var strbuf = new StringBuffer();
        var ch = '\u0000';
        for (int index = 0; index < str.length(); index++) {
            ch = str.charAt(index);
            if(ch == ' ' || ch == '\t' || ch == '\n') {
                continue;
            }
            if(ch > 57 || ch < 48 && ch != '.') {
                list.add(String.valueOf(ch));
            }else {
                strbuf.delete(0,strbuf.length());
                strbuf.append(ch);
                while((index + 1 < str.length()) && ((str.charAt(index + 1)) <= 57 && (str.charAt(index + 1)) >= 48 || (str.charAt(index + 1) == '.'))) {
                    strbuf.append(str.charAt(++index));
                }
                list.add(strbuf.toString());
            }
        }
        return list;
    }

    public static List<String> toSuffixList(List<String> list) {
        var s1 = new Stack<String>();
        var resList = new ArrayList<String>();
        for(var item : list) {
            if(item.matches("^\\d+(\\.\\d+)?")) {
                resList.add(item);
            }else {
                if(item.equals("(")) {
                    s1.push(item);
                }else if(item.equals(")")) {
                    while (!s1.peek().equals("(")) {
                        resList.add(s1.pop());
                    }
                    s1.pop();
                } else {
                    while(!s1.isEmpty()) {
                        if(Operation.getPriority(s1.peek()) >= Operation.getPriority(item)){
                            resList.add(s1.pop());
                        }else {
                            break;
                        }
                    }
                    s1.push(item);
                }
            }
        }
        while(!s1.isEmpty()) {
            resList.add(s1.pop());
        }
        return resList;
    }

    public static double cal(List<String> list) {
        var stack = new Stack<String>();
        var num1 = 0.0;
        var num2 = 0.0;
        var res = 0.0;
        for (var item : list) {
            if(item.matches("\\d+(\\.\\d+)?")){
                stack.push(item);
            }else {
                num1 = Double.parseDouble(stack.pop());
                num2 = Double.parseDouble(stack.pop());
                switch (item) {
                    case "+" -> res = num1 + num2;
                    case "-" -> res = num2 - num1;
                    case "*" -> res = num1 * num2;
                    case "/" -> res = num2 / num1;
                }
                stack.push(res + "");
            }
        }
        return Double.parseDouble(stack.pop());
    }
}
package datastructure.chapter02.stack.poland;

import java.util.ArrayList;
import java.util.Iterator;

public class Operation {
    private static final int ADD = 1;
    private static final int SUB = 1;
    private static final int MUL = 2;
    private static final int DIV = 2;
    private static final int OTHER = 0;

    public static int getPriority(String s) {
        return switch (s) {
            case "+" -> ADD;
            case "-" -> SUB;
            case "*" -> MUL;
            case "/" -> DIV;
            default -> OTHER;
        };
    }
}

结论:

    感谢看到博客最后,您的观看就是对作者最大的鼓励,对于该知识点,我做出以下必须要掌握的总结

1.我们知道逆波兰/波兰表达式的定义

2.我们要知道中缀表达式转后缀表达式的思路与实现

3.逆波兰计算器的运算规则

往期精彩:

数据结构(用栈实现对表达式的求值)

Java数据结构-稀疏数组的实现[用最简单的语言理解最复杂的问题]

标签： java 数据结构 算法
本文转载自: https://blog.csdn.net/JOElib/article/details/123365348
版权归原作者 JOElib 所有， 如有侵权，请联系我们删除。
登录后发布评论

“Java数据结构-中缀转后缀与逆波兰表达式及其计算器完整版[面试必备] 看完对于你而言,有手就行(超长,超带劲)”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

网络安全法-网络运行安全

使用selenium/drissionpage时如何阻止chrome自动跳转http到https

docker desktop 里部署的Open WebUI 管理员密码忘记了的处理方法

在ubuntu20.04中搭建onsite比赛运行环境

利用开源的低代码表单设计器FcDesigner高效管理和渲染复杂表单结构

Kafka学习笔记

【前端】浏览器输入url到页面呈现发生了什么？

文章导航