数据结构与算法之逆波兰计算器

拼搏现实的明天。 2021-12-07 12:55 333阅读 0赞

## 前言 ##

在上篇文章我们介绍了什么是前缀(波兰表达式)、中缀、后缀表达式(逆波兰表达式)。中缀表达式是通用的算术表达式，也是我们人常用算术表示方法。因为中缀表达式本身不容易被计算机解析，所以通常会转换为前缀或者后缀表达式。前面分别有介绍两种表达式的计算过程，可以看到前缀表达式计算过于复杂，所以通常转换为后缀表达式来进行计算，本编文章我们将结合后缀表达式来实现一个综合计算器。

## 综合计算器 ##

算术表达式类

public class ArithmeticExpression {
    
        /**
         * 匹配+ - * / ( ) 运算符正则表达式
         */
        private static final String OPERATOR_REGEX = "\\+|-|\\*|/|\$|\$";
        /**
         * 匹配数字正则表达式
         */
        private static final String NUMBER_REGEX = "^(([0-9]+\\.[0-9]*[1-9][0-9]*)|([0-9]*[1-9][0-9]*\\.[0-9]+)|([0-9]*[1-9][0-9]*))$";
    
        /**
         * 运算符
         */
        public static final String LEFT_SYMBOL = "(";
        public static final String RIGHT_SYMBOL = ")";
        public static final String ADD_SYMBOL = "+";
        public static final String SUB_SYMBOL = "-";
        public static final String MUL_SYMBOL = "*";
        public static final String DIV_SYMBOL = "/";
    
        /**
         * 运算符优先级
         */
        private static final int OPERATOR_PRIORITY_LEVEL_00 = 0;
        private static final int OPERATOR_PRIORITY_LEVEL_01 = 1;
        private static final int OPERATOR_PRIORITY_LEVEL_02 = 2;
    
        /**
         * 表达式转list
         *
         * @param expression 中缀表达式
         * @return
         */
        public static List<String> toExpressionList(String expression) {
            List<String> result = new ArrayList<>();
            String temp = "";
            for (int i = 0; i < expression.length(); i++) {
                String str = expression.substring(i, i + 1);
                // 使用正则表达示判断是否是数字
                if (!isNumber(str)) {
                    result.add(str);
                } else {
                    // 判断是否是表达式最后一个字符，如果是，直接放入list
                    if (i == expression.length() - 1) {
                        result.add(str);
                        continue;
                    }
    
                    temp += str;
                    // 处理多位数
                    String nextStr = expression.substring(i + 1, i + 2);
                    if (!isNumber(nextStr)) {
                        result.add(temp);
                        temp = "";
                    }
                }
            }
            return result;
        }
    
        /**
         * 去除空白字符
         *
         * @param str
         * @return
         */
        public static String replaceAllBlank(String str) {
            // \\s+ 匹配任何空白字符，包括空格、制表符、换行符等等，等价于[\f\n\t\v]
            return str.replaceAll("\\s+", "");
        }
    
        /**
         * 判断是不是数字（int float double long）
         *
         * @param str
         * @return
         */
        public static boolean isNumber(String str) {
            Pattern pattern = Pattern.compile(NUMBER_REGEX);
            return pattern.matcher(str).matches();
        }
    
        /**
         * 判断是不是运算符
         *
         * @param str
         * @return
         */
        public static boolean isOperator(String str) {
            return str.matches(OPERATOR_REGEX);
        }
    
        /**
         * 匹配运算优先级
         *
         * @param operator
         * @return
         */
        public static int calcLevel(String operator) {
            if (ADD_SYMBOL.equals(operator) || SUB_SYMBOL.equals(operator)) {
                return OPERATOR_PRIORITY_LEVEL_01;
            } else if (MUL_SYMBOL.equals(operator) || DIV_SYMBOL.equals(operator)) {
                return OPERATOR_PRIORITY_LEVEL_02;
            } else {
                return OPERATOR_PRIORITY_LEVEL_00;
            }
        }
    
        /**
         * 中缀表达式转后缀表达式
         *
         * @param expression 中缀表达式
         * @return
         */
        public static List<String> parseSuffixExpression(String expression){
            List<String> result = new ArrayList<>();
            // 中缀表达式转list
            List<String> toInfixExpressionList = toExpressionList(expression);
    
            Stack<String> stack = new Stack<>();
            for (String item : toInfixExpressionList) {
                if (isNumber(item)) { // 如果是数字直接放入结果集中
                    result.add(item);
                } else if (LEFT_SYMBOL.equals(item)) { // 如果是左括号直接入栈
                    stack.push(item);
                } else if (RIGHT_SYMBOL.equals(item)) {
                    // 如果是右括号，则依次弹出栈顶的运算符，并放入result list中，直到遇到左括号为止，此时将这一对括号丢弃
                    while (!LEFT_SYMBOL.equals(stack.peek())) {
                        result.add(stack.pop());
                    }
                    stack.pop(); // 消除左括号
                } else {
                    // 当item的优先级小于等于栈顶的运算符，将栈顶的运算符弹出并加入到result中，并重复此步骤，直到条件不满足时结束
                    while (stack.size() != 0 && calcLevel(stack.peek()) >= calcLevel(item)) {
                        result.add(stack.pop());
                    }
    
                    // 还需要将item入栈
                    stack.push(item);
                }
            }
    
            // 将栈中剩余的运算符弹出放入result中
            while (stack.size() != 0){
                result.add(stack.pop());
            }
            return result;
        }
    }

综合计算器类

public class ReversePolishMultiCalc {
    
        /**
         * 根据表达式计算结果
         *
         * @param expression 表达式
         * @return
         */
        public static double calculation(String expression) {
            double result = 0d;
            if (null == expression || "".equals(expression.trim())) {
                throw new RuntimeException("expression is empty");
            }
    
            // 过滤表达式，去除无效字符
            expression = ArithmeticExpression.replaceAllBlank(expression);
    
            // 将中缀表达式转换为后缀表达式
            List<String> expressionList = ArithmeticExpression.parseSuffixExpression(expression);
            result = calculator(expressionList);
            return result;
        }
    
        /**
         * 根据后缀表达式计算结果
         * 
         * 从左至右扫描，如果是数字则压入栈中，如果是运算符则取出栈顶元素和次栈顶元素进行运算，并将运算结果入栈
         * 重复上述过程，直到循环结束，最终留到栈中的就是运算结果
         *
         * @param dataList
         * @return
         */
        public static double calculator(List<String> dataList) {
            Stack<String> stack = new Stack<>();
            for (String item : dataList) {
                // 使用正则表达示判断是否是数字
                if (ArithmeticExpression.isNumber(item)) {
                    // 入栈
                    stack.push(item);
                } else {
                    String num1 = stack.pop();
                    String num2 = stack.pop();
                    double calRsult = cal(num2, num1, item);
                    // 将计算结果入栈
                    stack.push(String.valueOf(calRsult));
                }
            }
            return Double.valueOf(stack.pop());
        }
    
        /**
         * 计算
         *
         * @param num1      数据1
         * @param num2      数据2
         * @param operation 运算符
         * @return
         */
        private static double cal(String num1, String num2, String operation) {
            double result = 0d;
            switch (operation) {
                case ArithmeticExpression.ADD_SYMBOL:
                    result = Double.valueOf(num1) + Double.valueOf(num2);
                    break;
                case ArithmeticExpression.SUB_SYMBOL:
                    result = Double.valueOf(num1) - Double.valueOf(num2);
                    break;
                case ArithmeticExpression.MUL_SYMBOL:
                    result = Double.valueOf(num1) * Double.valueOf(num2);
                    break;
                case ArithmeticExpression.DIV_SYMBOL:
                    result = Double.valueOf(num1) / Double.valueOf(num2);
                    break;
                default:
                    break;
            }
            return result;
        }
    }

测试：

public class ReversePolishMultiCalcTest {
    
        public static void main(String[] args) {
            String expression = "1+((2+3)*4)-5";
            double calculation = ReversePolishMultiCalc.calculation(expression);
            System.out.println("calculation result is " + calculation);
        }
    }

输出结果：

calculation result is 16.0