中缀表达式转后缀表达式的代码实现及逆波兰计算器求值（后缀表达式求值）的代码实现

╰+哭是因爲堅強的太久メ 2023-07-03 08:20 18阅读 0赞

**1、案例**

1+((2+3)*4)-5

**2、思路步骤分析：**

本代码实现只考虑3类符号：正整数，运算符(+,-,*,/)、小括号，后续扩展，
    转换核心是这3类符号的比较特点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70][]

**3、代码实现**

package com.zzb.stack;
    
    import java.io.Serializable;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    /**
     * @Auther: Administrator
     * @Date: 2020/2/4 20:41
     * @Description: 中缀表达式 转 后缀表达式 的代码实现 及 逆波兰计算器求值（后缀表达式求值）的代码实现
     * 1、中缀表达式 转 后缀表达式 说明：
     * 本代码实现只考虑3类符号：正整数，运算符(+,-,*,/)、小括号，转换核心是这3类符号的比较特点
     * 后续扩展
     */
    public class InfixChangeToSuffixTest {
        public static void main(String[] args) {
            String infixStr = "1+((2+3)*4)-5";
    
            // 将一个中缀表达式字符串转换成对应的list集合形式
            List<String> infixList = formatToList(infixStr);
            System.out.println(infixList);
            /*[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]*/
    
            // 中缀表达式 转 后缀表达式
            List<String> suffixList = infixChangeToSuffix(infixList);
            System.out.println(suffixList);
            /*[1, 2, 3, +, 4, *, +, 5, -]*/
    
            // 逆波兰计算器（后缀表达式求值）
            int result = suffixCalculate(suffixList);
            System.out.println("逆波兰计算器（后缀表达式求值）" + suffixList + " == " + result);
            /*逆波兰计算器（后缀表达式求值）[1, 2, 3, +, 4, *, +, 5, -] == 16*/
        }
    
        /**
         * 逆波兰计算器
         * 后缀表达式求值
         * @param suffixList 后缀表达式的集合形式
         * @return 计算结果
         *
         * 思路分析：
         * (3+4)*5-6 对应的后缀表达式就是 3 4 + 5 * 6 - , 后缀表达式求值步骤如下
         * 1、从左至右扫描，将 3 和 4 压入栈
         * 2、扫描到 + 运算符，弹出 4 和 3（4 为栈顶元素，3 为次栈顶元素），计算出 3+4=7，将 7 入栈
         * 3、将 5 入栈
         * 4、扫描到 × 运算符，弹出 5 和 7，计算出 7*5=35，将 35 入栈
         * 5、将 6 入栈
         * 6、扫描到 - 运算符，计算出 35-6=29，将 29 入栈，得出最终结果
         */
        public static int suffixCalculate(List<String> suffixList) {
            // 创建栈
            Stack<String> stack = new Stack<>();
            // 遍历suffixList
            for (String str : suffixList) {
                // 这里使用正则表达式来取出数字
                if (str.matches("\\d+")) { // 匹配多位数
                    // 入栈
                    stack.push(str);
                } else {  // 运算符
                    // pop出两个数，并运算， 再入栈
                    // 注意操作数的顺序，主要是针对减法与除法的运算，操作数顺序错误会导致结果不正确
                    // num2 为栈顶元素
                    // num1 为次栈顶元素
                    int num2 = Integer.parseInt(stack.pop());
                    int num1 = Integer.parseInt(stack.pop());
                    int result = 0;
                    if ("+".equals(str)) {
                        result = num1 + num2;
                    } else if ("-".equals(str)) {
                        result = num1 - num2;
                    } else if ("*".equals(str)) {
                        result = num1 * num2;
                    } else if ("/".equals(str)) {
                        result = num1 / num2;
                    } else {
                        throw new RuntimeException("运算符有误！");
                    }
                    // 将 result 入栈
                    stack.push("" + result);
                }
            }
            return Integer.parseInt(stack.pop());
        }
    
        /**
         * 中缀表达式 转 后缀表达式
         * @param infixList 中缀表达式的集合形式
         * @return 后缀表达式的集合形式
         */
        public static List<String> infixChangeToSuffix(List<String> infixList) {
            // 初始化两个栈：运算符栈s1与储存中间结果的操作数栈s2
            // 运算符栈s1
            Stack<String> s1 = new Stack<>();
            // 储存中间结果的操作数集合s2
            // 使用集合的原因：整个转换的过程都没有涉及到栈的pop弹出操作，
            // 并且是为了以后计算后缀表达式（逆波兰计算器）方便取数据而设计的
            ArrayList<String> s2 = new ArrayList<>();
            for(String str : infixList) {
                // 多位数，使用正则判断
                // 扫描到操作数时，将操作数直接压入操作数栈s2
                if(str.matches("\\d+")) {
                    s2.add(str);
                } else if(str.equals("(")) { // 如果是左括号"("，则直接压入运算符栈s1
                    s1.push(str);
                } else if(str.equals(")")) {
                    while(!s1.peek().equals("(")) {
                        s2.add(s1.pop());
                    }
                    // 弹出左括号
                    // 消除一对左右括号
                    s1.pop();
                } else { // 运算符
                    // 优化版（选择其中一种都可以实现功能）
                    // 只有运算符栈s1的栈顶运算符的优先级大于或等于当前遍历到的运算符的优先级，才需要弹栈s1与压栈s2操作
                    while(s1.size() > 0 && Operator.getPriority(s1.peek()) >= Operator.getPriority(str)) {
                        s2.add(s1.pop());
                    }
                    s1.push(str);
    
                    // 思路分析版（递归实现）（选择其中一种都可以实现功能）
                    /*comparePriority(s1,s2,str);*/
                }
            }
            // 将运算符栈s1中剩余的运算符依次弹出运算符s1栈并压入操作数栈s2
            while(!s1.empty()) {
                s2.add(s1.pop());
            }
            return s2;
        }
    
        // 思路分析版（递归实现）
        private static void comparePriority(Stack<String> s1, ArrayList<String> s2, String str) {
            // 如果运算符栈s1为空，或者运算符栈s1的栈顶元素为左括号”(”，则直接将扫描到的运算符压入运算符栈s1
            if(s1.isEmpty() || "(".equals(s1.peek())) {
                s1.push(str);
            } else if(Operator.getPriority(str) > Operator.getPriority(s1.peek())) {
                // 否则，若优先级比运算符栈s1的栈顶运算符的高，也将扫描到的运算符直接压入运算符栈s1
                s1.push(str);
            } else if(Operator.getPriority(str) <= Operator.getPriority(s1.peek())) {
                // 否则，将运算符栈s1的栈顶运算符弹出运算符栈s1并压入操作数栈s2，
                // 再次转到步骤4.1与运算符栈s1的新栈顶运算符比较两者的运算符优先级
                s2.add(s1.pop());
                // 递归
                comparePriority(s1,s2,str);
            }
        }
    
        /**
         * 将一个中缀表达式字符串转换成对应的list集合形式
         * list集合保存中缀表达式中的各个部分，方便中缀转后缀时循环遍历取出数据
         * @param infixStr 中缀表达式字符串
         * @return 对应的list集合形式
         */
        public static List<String> formatToList(String infixStr) {
            // 扫描中缀表达式字符串获取数据
            int index = 0;
            // 保存在中缀表达式中扫描到的单个字符
            char ch;
            // 多位数拼接
            String numStr;
            // 保存在中缀表达式字符串中扫描到的数据
            List<String> infixList = new ArrayList<>();
            do {
                // 非数字
                // ASCII 码表中 字符'0'到'9' 对应 十进制48到57
                if(((ch = infixStr.charAt(index)) < 48) || ((ch = infixStr.charAt(index)) > 57)) {
                    infixList.add(ch + "");
                    index++;
                } else { // 多位数
                    // 清空
                    numStr = "";
                    while(index < infixStr.length() && (ch = infixStr.charAt(index)) >= 48 && (ch = infixStr.charAt(index)) <= 57) {
                        // 多位数拼接
                        numStr = numStr + ch;
                        index++;
                    }
                    infixList.add(numStr);
                }
            } while(index < infixStr.length());
            return infixList;
        }
    }
    
    /**
     * 操作符工具类
     */
    class Operator implements Serializable {
        private static final long serialVersionUID = 8861403813600893623L;
    
        //自定义各个操作符的优先级
        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 Operator() {
    
        }
    
        /**
         * 获取操作符优先级
         * @param operator 操作符字符串
         * @return 操作符优先级
         */
        public static int getPriority(String operator) {
            int priority = 0;
            switch (operator) {
                case "+":
                    priority = Operator.ADD;
                    break;
                case "-":
                    priority = Operator.SUB;
                    break;
                case "*":
                    priority = Operator.MUL;
                    break;
                case "/":
                    priority = Operator.DIV;
                    break;
                default:
                    break;
            }
            return priority;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200205002624389.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5,size_16,color_FFFFFF,t_70