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

清疚 2023-09-23 12:54 146阅读 0赞

![在这里插入图片描述][02a1d9de256e4900996a336aad26ac5b.png]

--------------------

### 文章目录 ###

*  1 前缀表达式
 *  2 中缀表达式
 *  3 后缀表达式
 *  4 逆波兰计算器
 *   *  4.1 逆波兰计算器简单实现
     *  4.2 中缀表达式转后缀表达式
     *   *  4.2.1 思路分析
         *  4.2.2 代码实现
     *  4.3 完整的逆波兰表达式计算器实现
 *  写在最后

--------------------

# 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数据结构：栈与综合计算器的实现（图解+完整代码）][Java]

![在这里插入图片描述][ee728a25eb0042a5aa33492f0207ab38.png]

--------------------

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

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

在该样例中，使用到了 **Java中的正则表达式，** 补充一点知识如下：  
![在这里插入图片描述][f52a2d877fa94966a22ca8737a1bc5c6.png]  
更多正则表达式的资料参考文章：[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;
        }

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

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

//中缀表达式List转后缀表达式List
        public static List<String> parseSuffixExpressionList(List<String> ls){
        
            //定义两个栈
            Stack<String> s1 = new Stack<>(); //符号栈
    //        Stack<String> 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;
        }

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

![在这里插入图片描述][7287e6b3692e4cbc9004d702413a42cf.png]

--------------------

# 写在最后 #

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

[02a1d9de256e4900996a336aad26ac5b.png]: https://img-blog.csdnimg.cn/02a1d9de256e4900996a336aad26ac5b.png
[Java]: https://blog.csdn.net/m0_60353039/article/details/127541994?spm=1001.2014.3001.5501
[ee728a25eb0042a5aa33492f0207ab38.png]: https://img-blog.csdnimg.cn/ee728a25eb0042a5aa33492f0207ab38.png
[de99fcb6643b4778b6a40b67043f1cb3.png]: https://img-blog.csdnimg.cn/de99fcb6643b4778b6a40b67043f1cb3.png
[f52a2d877fa94966a22ca8737a1bc5c6.png]: https://img-blog.csdnimg.cn/f52a2d877fa94966a22ca8737a1bc5c6.png
[java]: https://blog.csdn.net/qq_44835120/article/details/117606305?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522166700810316800182775678%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=166700810316800182775678&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-2-117606305-null-null.142%5Ev62%5Ejs_top,201%5Ev3%5Econtrol_2,213%5Ev1%5Et3_esquery_v1&utm_term=Java%E6%AD%A3%E5%88%99%E8%A1%A8%E8%BE%BE%E5%BC%8F&spm=1018.2226.3001.4187
[7287e6b3692e4cbc9004d702413a42cf.png]: https://img-blog.csdnimg.cn/7287e6b3692e4cbc9004d702413a42cf.png
[Java 1]: https://blog.csdn.net/m0_60353039/category_12062687.html
[33ad3bfbfa084fe792cdcea04e64ede9.gif_pic_center]: https://img-blog.csdnimg.cn/33ad3bfbfa084fe792cdcea04e64ede9.gif#pic_center
[ad16d93416c74666a97b046cb173134c.gif_pic_center]: https://img-blog.csdnimg.cn/ad16d93416c74666a97b046cb173134c.gif#pic_center