数据结构与算法之逆波兰计算器-蒲公英云

前言

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

综合计算器

算术表达式类

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