Java实现中缀表达式转后缀表达式

ゝ一纸荒年。 2024-04-08 13:54 40阅读 0赞

#### Java实现中缀表达式转后缀表达式 ####

*  1.后缀表达式介绍
 *   *  1.1简介
     *  1.2实现逆波兰计算器
     *  1.3思路分析
     *  1.4代码实现
 *  2.中缀转后缀表达式
 *   *  2.1 思路分析
     *  2.2图解
     *  2.3代码实现

## 1.后缀表达式介绍 ##

### 1.1简介 ###

逆波兰式（Reverse Polish notation，RPN，或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）  
在实现中缀转后缀之前我们先了解后缀表达式的实现，学习过编译原理这门的课程的同学，应该对逆波兰式非常的熟悉哈，没错他就是后缀表达式。

### 1.2实现逆波兰计算器 ###

*  输入一个逆波兰表达式，使用栈stack，计算其结果
 *  只支持对整数的计算

### 1.3思路分析 ###

> 从左至右扫描表达式，遇到数字时，将数字压入栈，遇到运算符时，弹出栈顶的两个数（栈顶元素和次顶元素），用运算符对他们做相应的计算，计算的结果再次入栈，重复以上过程，直到表达式最右端，最后运算得到的就是表达式的值。

例如： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 \* 6 - ，针对后缀表达式求值的步骤如下：

*  从左至右扫描，将3和4压栈
 *  遇到 “+” 运算符，弹出 栈顶元素和次栈顶元素 ， 3和4，通过运算符 计算 3+4，得到7，再将7入栈
 *  将5入栈
 *  遇到“✖” 运算符，弹出 5 和 7，计算 5\* 7 = 35，将35 入栈
 *  将 6 入栈
 *  遇到“-”运算符，计算出 35-6得29，最终结果29

### 1.4代码实现 ###

import java.util.Arrays;
    import java.util.List;
    import java.util.Stack;
    
    /**
    * @author 尹稳健~
    * @version 1.0
    * @time 2022/8/29
    */
    public class PolandNotation {
        
       public static void main(String[] args) {
        
           // 定义一个人逆波兰式  3 4 + 5 * 6 -
           String express = "3 4 + 5 * 6 - ";
           // 将 逆波兰式转为一个list数组
           List<String> stringList = Arrays.asList(express.split(" "));
           int result = calculate(stringList);
           System.out.println(result);
    
       }
    
       public static int calculate(List<String> list){
        
           // 创建一个栈存放数字
           Stack<String> stack = new Stack<>();
           // 遍历将 数字放入栈
           for (String item : list) {
        
               // 正则表达式匹配数字，可能数字是多位数
               if (item.matches("\\d+")){
        
                   stack.push(item);
                   // 如果不是数字那么就弹出栈顶两个元素通过运算符计算
               }else{
        
                   // 定义一个变量存放计算结果
                   Integer result;
                   // 栈顶元素
                   Integer rear = Integer.parseInt(stack.pop());
                   // 次顶元素
                   Integer front = Integer.parseInt(stack.pop());
                   // 判断item是哪个运算符
                   if ("+".equals(item)){
        
                       result = front + rear;
                   }else if ("-".equals(item)){
        
                       result = front - rear;
                   }else if ("*".equals(item)){
        
                       result = front * rear;
                   }else{
        
                       result = front / rear;
                   }
                   // 计算完将数据存入栈顶
                   stack.push(String.valueOf(result));
               }
           }
           return Integer.parseInt(stack.pop());
       }
    
    }

## 2.中缀转后缀表达式 ##

### 2.1 思路分析 ###

*  初始化一个数组存放表达式，一个栈存放运算符
 *  从左至右扫描中缀表达式，遇到数字直接添加到数组表达式
 *  遇到运算符时，需要判断
    
     *  如果是 “(” 直接入栈
     *  如果是 “）” ，则依次弹出栈顶的元素，压入数组中，直到遇到 “（” 时结束，且需要将 “（” 弹栈，
     *  遇到 + - \* / 运算符时，需要判断运算符的优先级，如果入栈元素小于等于栈顶元素的优先级时，需要将栈顶元素压入数组中，然后入栈元素再次进行运算符优先级比较
 *  如果中缀表达式已经读取完毕，则将栈中的元素依次出栈，放入数组中

### 2.2图解 ###

当遇到“）”右括号要入栈时  
![在这里插入图片描述][2233b57eab5043b3b40cb6d77c4ac691.png]  
弹出符号栈的栈顶元素，直到遇到 “（”左括号为止，并且弹出**左括号**  
![在这里插入图片描述][7a1bd14aae944db8b4900680a7ee629d.png]  
得到  
![在这里插入图片描述][e84839910a6a4fb0b33b2ea665f45bbd.png]  
当减号“-”要入栈时  
![在这里插入图片描述][23cc295a0d7f491797a81a15241ac3cb.png]  
入栈元素“-”和符号栈的栈顶元素进行优先级比较，入栈元素优先集不大于符号栈栈顶元素，将符号栈栈顶元素存放到后缀表达式的数组中，然后“-”入符号栈  
![在这里插入图片描述][f7e4ffeda4414e35a57b749bc71d335e.png]  
得到  
![在这里插入图片描述][92a93a8987c04f0c9af332303da30d64.png]  
最后将符号栈的元素依次pop到后缀表达式中，得到：

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

### 2.3代码实现 ###

package com.sky.stackTest;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.Stack;
    
    /**
     * @author 尹稳健~
     * @version 1.0
     * @time 2022/8/29
     */
    public class PolandNotation {
        
        public static void main(String[] args) {
        
            // 定义一个人逆波兰式  3 4 + 5 * 6 -
            String express = "3 4 + 5 * 6 - ";
            // 将 逆波兰式转为一个list数组
            List<String> stringList = Arrays.asList(express.split(" "));
            int result = calculate(stringList);
            System.out.println(result);
    
            // 完成将一个中缀转后缀的功能
            express = "1+((2+3)*4)-5";
            // 得到中缀表达式转为的List
            List<String> strings = toInfixExpression(express);
            // 将List转为后缀表达式
            List<String> parse = parse(strings);
            System.out.println(parse);
        }
    
        /**
         * 后缀表达式求值
         */
        public static int calculate(List<String> list) {
        
            // 创建一个栈存放数字
            Stack<String> stack = new Stack<>();
            // 遍历将 数字放入栈
            for (String item : list) {
        
                // 正则表达式匹配数字，可能数字是多位数
                if (item.matches("\\d+")) {
        
                    stack.push(item);
                    // 如果不是数字那么就弹出栈顶两个元素通过运算符计算
                } else {
        
                    // 定义一个变量存放计算结果
                    Integer result;
                    // 栈顶元素
                    Integer rear = Integer.parseInt(stack.pop());
                    // 次顶元素
                    Integer front = Integer.parseInt(stack.pop());
                    // 判断item是哪个运算符
                    if ("+".equals(item)) {
        
                        result = front + rear;
                    } else if ("-".equals(item)) {
        
                        result = front - rear;
                    } else if ("*".equals(item)) {
        
                        result = front * rear;
                    } else {
        
                        result = front / rear;
                    }
                    // 计算完将数据存入栈顶
                    stack.push(String.valueOf(result));
                }
            }
            return Integer.parseInt(stack.pop());
        }
    
        /**
         * 将中缀表达式转为List
         */
        public static List<String> toInfixExpression(String string) {
        
            // 索引
            int index = 0;
            // 创建一个数组保存
            List<String> ls = new ArrayList<>();
            while (index < string.length()) {
        
                // 如果是字符那么就直接添加
                if (string.charAt(index) < 48 || string.charAt(index) > 57) {
        
                    ls.add(string.charAt(index) + "");
                    index++;
                } else {
        
                    String str = "";
                    // 判断数字是否是多位数，直到匹配不到数字结束循环
                    while (index < string.length() && (string.charAt(index) >= 48 && string.charAt(index) <= 57)) {
        
                        // 拼接
                        str += string.charAt(index) + "";
                        index++;
                    }
                    ls.add(str);
                }
            }
            return ls;
    
        }
    
        public static List<String> parse(List<String> list) {
        
            // 符号栈
            Stack<String> s1 = new Stack<>();
            // 后缀表达式
            ArrayList<String> s2 = new ArrayList<>();
            for (String s : list) {
        
                // 遇到操作数直接压入s2
                if (s.matches("\\d+")) {
        
                    s2.add(s);
                    // 遇到(直接压入s1
                } else if ("(".equals(s)) {
        
                    s1.push(s);
                    // 依次弹出s1栈顶的运算符压入s2，知道遇到左括号为止
                } else if (")".equals(s)) {
        
                    while (!"(".equals(s1.peek())) {
        
                        // 压入s2
                        s2.add(s1.pop());
                    }
                    // 遇到(时，将(移除s1
                    s1.pop();
                }else{
        
                    // 判断运算符的优先级
                    while (s1.size() != 0 &&getNum(s1.peek()) >= getNum(s)){
        
                        s2.add(s1.pop());
                    }
                    s1.push(s);
                }
            }
            // 将s1中剩余的运算符加入到s2
            while (s1.size()!=0){
        
                s2.add(s1.pop());
            }
            return s2;
    
        }
    
        /** 根据运算符返回值,值越大，优先集越高 */
        public static int getNum(String string){
        
            if ("*".equals(string) || "/".equals(string)){
        
                return 2;
            }else if ("+".equals(string) || "-".equals(string)){
        
                return 1;
            }else{
        
                return 0;
            }
        }
    }

[2233b57eab5043b3b40cb6d77c4ac691.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/d205af9112ed4a8eb43597528856619b.png
[7a1bd14aae944db8b4900680a7ee629d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/0bffa72bdfba4dfdbc70a999439626a6.png
[e84839910a6a4fb0b33b2ea665f45bbd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/0436259b7e7e46d09338fc01512b2b14.png
[23cc295a0d7f491797a81a15241ac3cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/e6355f62ce974772ab42f17c51137ce1.png
[f7e4ffeda4414e35a57b749bc71d335e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/33eae8613a9c40f6bfcc6b6503433c43.png
[92a93a8987c04f0c9af332303da30d64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/fa59627e805d45f98272757a9b4653c9.png
[79bef5e3f4964f61828a9593ed9f5085.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/e0a03c9e68574d7290787a67afa93330.png