前言:

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

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

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

应用场景:

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

逆波兰计算器的优点:

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

相关概念波兰表达式

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

如"+12"

逆波兰表达式

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

如"12+"

中缀表达式

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

如"1+2"

代码思路逆波兰表达式计算

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

建立一个栈,用于专门存放数字

建立一个索引,从右向左扫描表达式

如果扫描到了数字,则直接压栈

若扫描到了运算符,则将栈中的栈顶元素和次顶元素弹出,并结合运算符进行运算,并将结果压回

减法和除法是次顶元素-/栈顶元素

区别

扫描顺序不同

运算顺序不同

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

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

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

创建一个方法,将中缀表达式转换成集合

public static List toInfixList(String str) {
        var list = new ArrayList();
        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;
    }

第一步就是创建一个集合,用于存储取出来的元素,泛型应该被指定为String,后面有用StringBuffer的作用是做字符串拼接,用于解决多位数和小数的问题通过循环,用index去遍历,调用charAt()方法,将对应下标的字符取出放入ch中如果ch是运算符,直接放入集合中(不需要有任何操作)如果ch是数字,则要考虑是否是多位数或者是小数.如果是则要字符串拼接

创建一个方法,将中缀表达式的集合转化成后缀表达式的集合

public static List toSuffixList(List list) {
        var s1 = new Stack();
        var resList = new ArrayList();
        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;
    }

第一步是创建一个栈和一个集合,因为第二个栈只有压栈不弹栈,为了方便,直接创建集合根据思路完成代码即可

补充上述的一个判断优先级的类

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;
        };
    }
}

通过数字映射优先级大小OTHER的存在解决了只要是左括号直接压栈这一个步骤

创建一个方法,是真正的逆波兰计算机的方法

public static double cal(List list) {
        var stack = new Stack();
        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());
    }

double类型的定义是为了适应小数运算,var是局部变量类型推断,评论区留言我可以专门写一篇博客栈的泛型应该是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 toInfixList(String str) {
        var list = new ArrayList();
        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 toSuffixList(List list) {
        var s1 = new Stack();
        var resList = new ArrayList();
        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 list) {
        var stack = new Stack();
        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数据结构-中缀转后缀与逆波兰表达式及其计算器完整版[面试必备] 看完对于你而言,有手就行(超长,超带劲)

Java相关栏目本月热门文章