• Java数据结构：前缀、中缀、后缀表达式与逆波兰计算器的实现

    在这里插入图片描述

    文章目录

    1 前缀表达式

    前缀表达式又称波兰式，在该表达式中，运算符位于操作数之前。

    eg：（3+4）*5-6 对应的前缀表达式

    - * + 3 4 5 6

    前缀表达式的计算机求值：
    从右向左扫描表达式。遇到数字，将数字压入数字栈；遇到运算符，弹出两个数字，用运算符进行计算（栈顶与次顶），将计算的结果再次压入数字栈。重复操作，直到扫描到表达式的最左端，此时最后运算的值，即为结果。

    eg：简述（3+4）*5-6 对应的前缀表达式- * + 3 4 5 6计算机求值过程

    1. 从右向左扫描，依次将6、5、4、3压入数字栈；
    2. 遇到 + 运算符，计算3+4=7，将7压入数字栈；
    3. 遇到*运算符，弹出7、5，计算得35，再次压入数字栈；
    4. 遇到-运算符，弹出35、6，计算35-6=29，29即为表达式的结果。

    2 中缀表达式

    中缀表达式就是我们平时最熟悉的运算表达式。在上一节中，我们已经实现了中缀表达式综合计算器的实现。可以看出，虽然我们很好解读中缀表达式，但是对计算机来说却不好操作，需要在每次判断是否为操作符、判断优先级等等。因此，我们常常将中缀表达式转化成其他表达式来进行操作。

    中缀表达式计算器的实现：Java数据结构：栈与综合计算器的实现（图解+完整代码）

    在这里插入图片描述

    3 后缀表达式

    后缀表达式又称逆波兰表达式。运算符位于操作数的后面。

    eg：（3+4）*5-6 对应的后缀表达式

    3 4 + 5 * 6 -

    后缀表达式的计算机求值：
    从左至右扫描表达式，遇到数字时，将数字压入数字栈。遇到符号时，弹出两个栈顶元素，用运算符进行相应的运算，并将结果入栈。重复操作，直到扫描到表达式的最右端，最后计算的值即为表达式的结果。

    eg：简述（3+4）*5-6 对应的前缀表达式3 4 + 5 * 6 - 计算机求值过程

    1. 从左至右扫描，将3和4入数字栈；
    2. 遇到 + 运算符，弹出 4、 3，计算 3 + 4 = 7，将 7 压入数字栈；
    3. 将 5 压入数字栈；
    4. 遇到 * ，弹出 5、7，计算 7 * 5 = 35，将 35 压入数字栈；
    5. 将 6 压入数字栈；
    6. 遇到 - ，弹出 6、35，计算 35 - 6 = 29，29即为表达式的值。

    4 逆波兰计算器

    4.1 逆波兰计算器简单实现

    （1）输入一个逆波兰表达式，使用Stack来进行运算
    （2）需要支持小括号和多位整数的运算（简化，只计算整数）

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

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 逆波兰表达式计算器的实现
 */
@SuppressWarnings({"all"})
public class PolandNotation {

    public static void main(String[] args) {
        //定义一个逆波兰表达式，以空格分隔
        String suffixExpression = "3 4 + 5 * 6 -";
        System.out.println("逆波兰表达式: " + suffixExpression);
        //转成list
        List<String> suffixExpressionList = getListString(suffixExpression);
        //计算求值
        int res = calculate(suffixExpressionList);
        System.out.println("结果: " + res);
    }

    //将逆波兰表达式存入List中，便于配合栈的遍历扫描
    public static List<String> getListString(String suffixExpression){
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }

    //遍历list，并对list中存储的逆波兰表达式进行运算
    public static int calculate(List<String> list){
        //创建一个栈，只需要数字栈，符号扫描到时即直接运算
        Stack<String> stack = new Stack<>();
        //遍历并计算
        for (String item: list){
            //正则表达式取数字
            if (item.matches("\\d+")){ //匹配多位数字
                //入栈
                stack.push(item);
            }else {
                //处理符号，计算两个数，压栈
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;
                res = quadricOperation(num1, num2, item);
                stack.push("" + res);
            }
        }
        //最后留下的一个为结果
        return Integer.parseInt(stack.peek());
    }

    //计算四则运算
    public static int quadricOperation(int num1, int num2, String operation){
        int res = 0; //存放返回的结果
        switch (operation){
            case "+":
                res = num1 + num2;
                break;
            case "-":
                res = num2 - num1;
                break;
            case "*":
                res = num1 * num2;
                break;
            case "/":
                res = num2 / num1;
                break;
            default:
                break;
        }
        return res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78

    在这里插入图片描述
    以上，解决了简单逆波兰表达式的求值问题，但是，如果输入的不是后缀表达式，则无法求值。

    在该样例中，使用到了 Java中的正则表达式， 补充一点知识如下：
    在这里插入图片描述
    更多正则表达式的资料参考文章：java基础之正则表达式

    4.2 中缀表达式转后缀表达式

    4.2.1 思路分析

    1. 初始化两个栈：运算符栈s1与存储中间结果的栈s2；
    2. 从左到右扫描整个中缀表达式；
    3. 遇到操作数，压入栈s2；
    4. 遇到运算符，比较其与s1栈顶运算符的优先级
      4.1 s1为空，或者栈顶元素为"("，则直接将运算符压入栈；
      4.2 若优先级比栈顶运算符高，则直接压入；
      4.3 反之，则将s1的栈顶pop出并压入s2，并再次转到与s1新栈顶进行运算符比较。
    5. 遇到括号时：
      5.1 左括号，则直接压入s1；
      5.2 右括号，则依次弹出s1的运算符压入s2，直到遇到左括号为止，将左右括号丢弃
    6. 重复2-5步骤，直到扫描完成；
    7. 将s1剩余的运算符弹出压入s2；
    8. 依次弹出s2的元素，s2的逆序即为后缀表达式。

    4.2.2 代码实现

    将中缀表达式的数字和符号扫描到List中，便于遍历

        //将中缀表达式转成对应的list
    public static List<String> toInfixExpressionList(String s){
        //定义List存放中缀表达式对应内容
        List<String> ls = new ArrayList<>();
        int i = 0; //用于遍历中缀表达式的指针
        String str; //对多位数拼接
        char c; //每遍历一个字符就放入c
        do{
            //如果c不是数字,加入ls
            //ASCII 48-57
            if ((c=s.charAt(i)) < '0' || (c=s.charAt(i)) > '9'){
                ls.add("" + c);
                i++;
            }else {
                //是数字，则拼接(考虑多位数)
                str = "";
                while (i < s.length() && (c=s.charAt(i)) >= '0' && (c=s.charAt(i)) <= '9'){
                    str += c; //拼接
                    i++;
                }
                ls.add(str);
            }
        }while (i < s.length());
        return ls;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    将得到的中缀表达式的List转成对应的后缀表达式的List

    Tips：s2栈在整个过程中没有进行出栈操作，且结果的逆序才是后缀表达式，因此，使用List来存储结果

        //中缀表达式List转后缀表达式List
    public static List<String> parseSuffixExpressionList(List<String> ls){
        //定义两个栈
        Stack<String> s1 = new Stack<>(); //符号栈
//        Stack s2 = new Stack<>(); //存放中间结果的栈
        //s2栈在整个过程中没有进行出栈操作，且结果的逆序才是后缀表达式，因此，使用List来存储结果
        List<String> s2 = new ArrayList<>();
        
        //遍历ls
        for (String item: ls){
            //数字加入s2
            if (item.matches("\\d+")){
                s2.add(item);
            }else {
                //括号进行操作
                if (item.equals("(")){
                    //左括号直接入
                    s1.push(item);
                }else if (item.equals(")")){
                    //右括号则依次弹出s1的运算符，压入s2，直到遇到左括号为止，并丢弃
                    while (true){
                        String pop = s1.pop();
                        if ("(".equals(pop)){
                            break;
                        }
                        s2.add(pop);
                    }
                }else {
                    //操作符的操作
                    //item的优先级小于等于s1栈顶运算符，则将s1栈顶运算符加入到s2中，再次转到与s1中的运算符进行比较
                    while (s1.size() > 0 && priority(item) <= priority(s1.peek())){
                        s2.add(s1.pop());
                    }
                    //item压栈
                    s1.push(item);
                }
            }
        }
        //将s1剩余的加入s2
        while (!s1.isEmpty()){
            s2.add(s1.pop());
        }
        
        return s2;
    }
    
    //判断优先级大小
    //返回运算符号的优先级，返回数字越大，优先级越大
    public static int priority(String operation){
        int result = 0;
        switch (operation){
            case "+", "-":
                result = 1;
                break;
            case "*", "/":
                result = 2;
                break;
            default:
                break;
        }
        return result;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62

    4.3 完整的逆波兰表达式计算器实现

    实现对多位整数的中缀表达式转后缀表达式并求值的需求。

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

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 中缀表达式转后缀表达式
 * 完整逆波兰表达式计算器的实现
 */
@SuppressWarnings({"all"})
public class PolandNotation {

    public static void main(String[] args) {
        //定义中缀表达式，进行转换并求值
        String expression = "1+((2+3)*4)-5";
        System.out.println("输入: " + expression);
        System.out.println("中缀表达式: " + toInfixExpressionList(expression));
        System.out.println("转换后缀表达式: " + parseSuffixExpressionList(toInfixExpressionList(expression)));
        System.out.println("计算结果为: " + calculate(parseSuffixExpressionList(toInfixExpressionList(expression))));
    }

    //中缀表达式List转后缀表达式List
    public static List<String> parseSuffixExpressionList(List<String> ls){
        //定义两个栈
        Stack<String> s1 = new Stack<>(); //符号栈
//        Stack s2 = new Stack<>(); //存放中间结果的栈
        //s2栈在整个过程中没有进行出栈操作，且结果的逆序才是后缀表达式，因此，使用List来存储结果
        List<String> s2 = new ArrayList<>();

        //遍历ls
        for (String item: ls){
            //数字加入s2
            if (item.matches("\\d+")){
                s2.add(item);
            }else {
                //括号进行操作
                if (item.equals("(")){
                    //左括号直接入
                    s1.push(item);
                }else if (item.equals(")")){
                    //右括号则依次弹出s1的运算符，压入s2，直到遇到左括号为止，并丢弃
                    while (true){
                        String pop = s1.pop();
                        if ("(".equals(pop)){
                            break;
                        }
                        s2.add(pop);
                    }
                }else {
                    //操作符的操作
                    //item的优先级小于等于s1栈顶运算符，则将s1栈顶运算符加入到s2中，再次转到与s1中的运算符进行比较
                    while (s1.size() > 0 && priority(item) <= priority(s1.peek())){
                        s2.add(s1.pop());
                    }
                    //item压栈
                    s1.push(item);
                }
            }
        }
        //将s1剩余的加入s2
        while (!s1.isEmpty()){
            s2.add(s1.pop());
        }

        return s2;
    }

    //判断优先级大小
    //返回运算符号的优先级，返回数字越大，优先级越大
    public static int priority(String operation){
        int result = 0;
        switch (operation){
            case "+":
            case "-":
                result = 1;
                break;
            case "*":
            case "/":
                result = 2;
                break;
            default:
                break;
        }
        return result;
    }

    //将中缀表达式转成对应的list
    public static List<String> toInfixExpressionList(String s){
        //定义List存放中缀表达式对应内容
        List<String> ls = new ArrayList<>();
        int i = 0; //用于遍历中缀表达式的指针
        String str; //对多位数拼接
        char c; //每遍历一个字符就放入c
        do{
            //如果c不是数字,加入ls
            //ASCII 48-57
            if ((c=s.charAt(i)) < '0' || (c=s.charAt(i)) > '9'){
                ls.add("" + c);
                i++;
            }else {
                //是数字，则拼接(考虑多位数)
                str = "";
                while (i < s.length() && (c=s.charAt(i)) >= '0' && (c=s.charAt(i)) <= '9'){
                    str += c; //拼接
                    i++;
                }
                ls.add(str);
            }
        }while (i < s.length());
        return ls;
    }

    //将逆波兰表达式存入List中，便于配合栈的遍历扫描
    public static List<String> getListString(String suffixExpression){
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }

    //遍历list，并对list中存储的逆波兰表达式进行运算
    public static int calculate(List<String> list){
        //创建一个栈，只需要数字栈，符号扫描到时即直接运算
        Stack<String> stack = new Stack<>();
        //遍历并计算
        for (String item: list){
            //正则表达式取数字
            if (item.matches("\\d+")){ //匹配多位数字
                //入栈
                stack.push(item);
            }else {
                //处理符号，计算两个数，压栈
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;
                res = quadricOperation(num1, num2, item);
                stack.push("" + res);
            }
        }
        //最后留下的一个为结果
        return Integer.parseInt(stack.peek());
    }

    //计算四则运算
    public static int quadricOperation(int num1, int num2, String operation){
        int res = 0; //存放返回的结果
        switch (operation){
            case "+":
                res = num1 + num2;
                break;
            case "-":
                res = num2 - num1;
                break;
            case "*":
                res = num1 * num2;
                break;
            case "/":
                res = num2 / num1;
                break;
            default:
                break;
        }
        return res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168

    在这里插入图片描述

    写在最后

     本文被 Java数据结构 收录点击订阅专栏 ， 持续更新中。
     创作不易，如果你有任何问题，欢迎私信，感谢您的支持！
    在这里插入图片描述在这里插入图片描述

  • 相关阅读:
    iOS runtime
    Nuxt3+pinia --- 路由拦截
    golang 线程 定时器 --chatGPT
    Image Sensor卷帘曝光（Rolling Shutter）基本原理
    避免遮掩继承而来的名称
    linux之管道符详解
    Django验证码(一）
    用DIV+CSS技术设计的公益主题网站——防止电信诈骗（web前端网页制作课作业）
    web-traffic-generator：一款功能强大的HTTP和HTTPs流量混淆工具
    元器件正反（极性）检测案例
  • 原文地址：https://blog.csdn.net/m0_60353039/article/details/127582846