[Java知识库]Java递归调用—实现自定义四则运算表达式解析/计算

递归调用

先拷贝一下百科上递归调用的定义啊：

• 递归调用是一种特殊的嵌套调用，是某个函数调用自己或者是调用其他函数后再次调用自己的，只要函数之间互相调用能产生循环的则一定是递归调用，递归调用一种解决方案，一种是逻辑思想，将一个大工作分为逐渐减小的小工作。
• 就比如一个人吃饭，我们不知道饭到底有多少，需要多少口能够吃完。我们只定义一个“吃一口”的方法，每次执行“吃一口”之后，就再次调用这个方法，直到饭变成空的了。

递归的思想，一个大型的复杂的问题，层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程。递归过程中，一定有一个结束条件，当满足这个条件之后，程序就返回，不再继续递归调用。

解析一个四则运算表达式

一个自定义的四则运算公式：

(-${a} + (${b} + ${c} * ${d}) - 3 * 7 * ${e}) * ${f}

其中 a ~ f，都是变量，通过 “${}” 包裹，给出 a ~ f 的值以后，计算这个公式的结果。可以将这个表达式，解析为每一步运算的过程，即每次都是两个变量进行操作，最后得出结果。
按照四则运算的规则，先对括号进行解析，当解析为不包含括号的表达式后，再按照先乘除，后加减解析的规则，进行拆分，直到解析为两个变量的操作，得到下面这样的解析结果：

(-${a} + (${b} + ${c} * ${d}) - 3 * 7 * ${e}) * ${f}

var0 = ${c}*${d}
var1 = ${b}+${var0}
var2 = 3*7
var3 = ${var2}*${e}
var4 = 0-${a}
var5 = ${var4}+${var1}
var6 = ${var5}-${var3}
var7 = ${var6}*${f}

每一步的结果，用一个变量保存，下面的表达式会引用该变量，最后一个表达式的结果，就是最终结果。

代码实现

• parseFormula：解析表达式，解析括号部分。
  如果表达式中没有括号了，则调用解析四则运算的方法。如果有括号，将括号中的字符串，再次调用本身方法。最后括号部分用变量替换，再次调用本身方法进行处理。
• parseFourArithmetic：解析四则运算。
  如果表达式中只包含同一类运算符号，即只有加减或者乘除，则调用解析简单表达式的方法。如果加减和乘除都存在，将乘除部分取出，再次调用本身方法。最后乘除部分用变量替换，再次调用本身方法进行处理。
• parseSimpleFormula：解析简单表达式。
  此时的输入的表达式，只包含加减，或者乘除了，只需从左往右进行解析。如果只包含一个操作符号了，则返回；否则将前面两个变量替换后，再次调用本身方法处理。

最终，通过上面三个方法的递归调用，将表达式解析为n条只包含一个运算符号的表达式。
计算时，循环遍历解析结果，进行变量的替换，将每一步的结果都放入变量的map中，后续的计算会用到。最后一个表达式的结果，就是最终的结果了。
PS：解析出的List<Formula>表达式集合，可以根据表达式字符串，缓存下来，下一次就不需要解析了，直接根据字符串获取缓存的表达式集合即可

import lombok.Data;
import lombok.extern.slf4j.Slf4j;

import java.math.BigDecimal;
import java.util.*;

/**
 * @Description 四则运算公式工具类
 */
@Slf4j
public class FormulaUtil {

    public static void main(String[] args) {

        String str = "(-${a} + (${b} + ${c} * ${d}) - 3*7*${e}) * ${f}";
        List<Formula> strings = parseFormula(str);
        for (Formula string : strings) {
            System.out.println(string);
        }

        Map<String, Number> varMap = new HashMap<>();
        varMap.put("a", 1);
        varMap.put("b", 2);
        varMap.put("c", 3);
        varMap.put("d", -5);
        varMap.put("e", 5);
        varMap.put("f", 10);

        double calculate = calculate(strings, varMap);
        System.out.println(calculate);
    }

    /**
     * 解析并计算表达式
     * @param str 表达式
     * @param varMap 变量map
     * @return 结果
     */
    public static double calculate(String str, Map<String, Number> varMap) {
        return calculate(parseFormula(str), varMap);
    }

    /**
     * 计算表达式
     * @param formulaList 步骤表达式
     * @param varMap 变量map
     * @return 结果
     */
    public static double calculate(List<Formula> formulaList, Map<String, Number> varMap) {
        if (formulaList == null || formulaList.isEmpty()) {
            throw new IllegalArgumentException("计算流程不能为空 formulaList is null or empty");
        }

        Number res = null;

        for (Formula formula : formulaList) {
            res = formula.calculate(varMap);
            varMap.put(formula.getVariable(), res);
        }

        return res.doubleValue();
    }

    /**
     * 解析表达式
     * @param formula 表达式
     * @return 结果
     */
    public static List<Formula> parseFormula(String formula) {
        formula = formula.replaceAll(" ", "");
        int length = formula.length();
        int leftBracketSum = 0;
        int rightBracketSum = 0;
        for (int i = 0; i < length; i++) {
            char c = formula.charAt(i);
            if (c == '(') {
                leftBracketSum++;
            }
            if (c == ')') {
                rightBracketSum++;
            }
        }

        if (leftBracketSum != rightBracketSum) {
            throw new IllegalArgumentException("公式异常, 左括号和右括号数量不相等");
        }
        ArrayList<Formula> formulaList = new ArrayList<>();

        if (leftBracketSum == 0) {
            formulaList.addAll(parseFourArithmetic(formula));
            return formulaList;
        }

        int firstBraces = formula.indexOf("(");
        if (firstBraces > -1) {
            int firstBracesOther = getMirrorIndex(formula, firstBraces);
            // 括号里面的表达式
            String subFormula = formula.substring(firstBraces + 1, firstBracesOther);
            List<Formula> sfs = parseFormula(subFormula);
            formulaList.addAll(sfs);

            String fs = new StringBuilder()
                    .append(formula.substring(0, firstBraces))
                    .append(sfs.get(sfs.size() - 1).getVariableStr())
                    .append(formula.substring(firstBracesOther + 1))
                    .toString();
            formulaList.addAll(parseFormula(fs));
        }

        return formulaList;
    }

    /**
     * 解析只包含四则运算的表达式，不包含括号
     * @param formula 表达式
     * @return 结果
     */
    private static List<Formula> parseFourArithmetic(String formula) {
        if (formula.startsWith("-") || formula.startsWith("+")) {
            formula = "0" + formula;
        }

        String[] addSub = new String[]{"+", "-"};
        String[] mutDiv = new String[]{"*", "/"};

        int addSubCount = countChars(formula, addSub);
        int mutDivCount = countChars(formula, mutDiv);
        if (addSubCount == 0 && mutDivCount == 0) {
            throw new IllegalArgumentException("公式错误: " + formula);
        }

        List<Formula> formulaList = new ArrayList<>();

        if ((addSubCount + mutDivCount) == 1) {
            formulaList.add(new Formula(formula));
            return formulaList;
        }

        if (mutDivCount == 0) {
            // 仅有加减算术符号
            formulaList.addAll(parseSimpleFormula(formula, addSub));
            return formulaList;
        } else if (addSubCount == 0) {
            // 仅有乘除算术符号
            formulaList.addAll(parseSimpleFormula(formula, mutDiv));
            return formulaList;
        }

        int maxIndex = formula.length();

        int startIndex = findFirstIndex(formula, 0, maxIndex, mutDiv);

        int nextAddSub = findFirstIndex(formula, startIndex, maxIndex, addSub);
        int preAddSub = findLastIndex(formula, 0, startIndex, addSub);

        preAddSub = preAddSub < 0 ? 0 : preAddSub + 1;
        nextAddSub = nextAddSub < 0 ? maxIndex : nextAddSub;

        String subFormula = formula.substring(preAddSub, nextAddSub);

        List<Formula> subFormulas = parseFourArithmetic(subFormula);
        formulaList.addAll(subFormulas);

        String fs = new StringBuilder()
                .append(formula.substring(0, preAddSub))
                .append(subFormulas.get(subFormulas.size() - 1).getVariableStr())
                .append(formula.substring(nextAddSub))
                .toString();
        formulaList.addAll(parseFourArithmetic(fs));
        return formulaList;
    }

    /**
     * 解析只包含同一类运算符的表达式，只包含加减，或者乘除
     * @param formula 表达式
     * @param typeChars 加减，或者乘除 的运算符号
     * @return 最终结果：仅有两个变量的操作表达式
     */
    private static List<Formula> parseSimpleFormula(String formula, String... typeChars) {
        List<Formula> formulaList = new ArrayList<>();
        int maxIndex = formula.length();

        int firstIndex = findFirstIndex(formula, 0, maxIndex, typeChars);
        int secondIndex = findFirstIndex(formula, firstIndex + 1, maxIndex, typeChars);

        if (secondIndex == -1) {
            Formula ff = new Formula(formula);
            formulaList.add(ff);
            return formulaList;
        }

        String firstFormula = formula.substring(0, secondIndex);
        Formula ff = new Formula(firstFormula);
        formulaList.add(ff);

        String fs = new StringBuilder()
                .append(ff.getVariableStr())
                .append(formula.substring(secondIndex))
                .toString();

        formulaList.addAll(parseSimpleFormula(fs, typeChars));
        return formulaList;
    }

    private static int countChars(String formula, String... chars) {
        int count = 0;
        for (int i = 0; i < formula.length(); i++) {
            for (String aChar : chars) {
                if (aChar.equals(formula.charAt(i) + "")) {
                    count++;
                }
            }
        }
        return count;
    }

    private static int findFirstIndex(String formula, int startIndex, int endIndex, String... chars) {
        String substring = formula.substring(startIndex, endIndex);

        List<Integer> integers = new ArrayList<>();

        for (String s : chars) {
            int index = substring.indexOf(s);
            if (index >= 0) {
                integers.add(index);
            }
        }

        if (integers.isEmpty()) {
            return -1;
        }
        return integers.stream().min((i1, i2) -> i1 - i2).get() + startIndex;
    }

    private static int findLastIndex(String formula, int startIndex, int endIndex, String... chars) {
        String substring = formula.substring(startIndex, endIndex);

        List<Integer> integers = new ArrayList<>();

        for (String s : chars) {
            int index = substring.lastIndexOf(s);
            if (index >= 0) {
                integers.add(index);
            }
        }

        if (integers.isEmpty()) {
            return -1;
        }
        return integers.stream().max((i1, i2) -> i1 - i2).get() + startIndex;
    }

    /**
     * 找到左括号对应的右括号位置
     * @param formula 表达式
     * @param leftIndex 左括号索引位置
     * @return 右括号位置
     */
    private static int getMirrorIndex(String formula, int leftIndex) {
        int num = 1;
        int leftStart = leftIndex + 1;

        while (leftStart > 0) {
            int nextIndex = formula.indexOf("(", leftStart);
            if (nextIndex < 0) {
                break;
            }
            String s = formula.substring(leftStart, nextIndex);
            if (s.contains(")")) {
                break;
            }
            num++;
            leftStart = nextIndex + 1;
        }

        int rIndex = -1;
        for (int i = 0; i < num; i++) {
            int ri = formula.indexOf(")", rIndex + 1);
            if (ri < 0) {
                break;
            }
            rIndex = ri;
        }
        return rIndex;
    }

    /**
     * 公式定义
     */
    @Data
    static class Formula {

        private static final ThreadLocal<Integer> number = ThreadLocal.withInitial(() -> 0);

        private static String varRegex = "^\\$\\{\\S+\\}$";

        private static String symbolRegex = "[\\+\\-\\*/]";

        private static String numberRegex = "^[\\+\\-]*\\d+\\.*\\d*$";

        private static String varChar = "[\\$\\{\\}]";

        /**
         * 该表达式结果的变量名
         */
        private String variable;

        /**
         * 表达式
         */
        private String formulaStr;

        public Formula(String formulaStr) {
            this.variable = "var" + number.get();
            this.formulaStr = formulaStr;
            // 变量每次加1
            number.set(number.get() + 1);
        }

        public String getVariableStr() {
            return "${" + this.variable + "}";
        }

        public Number calculate(Map<String, Number> varMap) {
            String[] fs = formulaStr.split(symbolRegex);
            if (fs.length == 1) {
                String var = fs[0];
                return getVarValue(var, varMap);
            }

            if (fs.length != 2) {
                throw new IllegalArgumentException("表达式错误: " + formulaStr + "，+ - * / 符号两侧必须是变量或者常量");
            }

            String var1 = fs[0];
            String var2 = fs[1];
            // 运算符号
            String symbol = formulaStr.charAt(var1.length()) + "";

            BigDecimal b1 = getVarValue(var1, varMap);
            BigDecimal b2 = getVarValue(var2, varMap);

            BigDecimal res;
            if ("+".equals(symbol)) {
                res = b1.add(b2);
            } else if ("-".equals(symbol)) {
                res = b1.subtract(b2);
            } else if ("*".equals(symbol)) {
                res = b1.multiply(b2);
            } else if ("/".equals(symbol)) {
                if (b2.compareTo(new BigDecimal("0")) == 0) {
                    throw new IllegalArgumentException("被除数 ${" + var2 + "}: 不能为0");
                }
                res = b1.divide(b2, 8, BigDecimal.ROUND_HALF_DOWN);
            } else {
                throw new IllegalArgumentException("运算符号：" + symbol + " 错误，支持: + - * /");
            }

            return res;
        }

        private BigDecimal getVarValue(String var1, Map<String, Number> varMap) {
            Number n1;
            if (var1.matches(varRegex)) {
                var1 = var1.replaceAll(varChar, "");
                n1 = varMap.get(var1);
                if (n1 == null) {
                    throw new IllegalArgumentException("找不到变量：" + var1 + " 的值，请检查");
                }
            } else if (var1.matches(numberRegex)) {
                n1 = Double.valueOf(var1);
            } else {
                throw new IllegalArgumentException("表达式：" + var1 + "，不符合 变量或者常量格式，如：${a}、2、2.3、-5");
            }
            return BigDecimal.valueOf(n1.doubleValue());
        }

        public static void main(String[] args) {
            Formula f = new Formula("${a}*2.3");
            Map<String, Number> numberMap = new HashMap<>();
            numberMap.put("a", 1.1);
            numberMap.put("v", 2);

            Number calculate = f.calculate(numberMap);
            System.out.println(calculate);
        }

        @Override
        public String toString() {
            return variable + " = " + formulaStr;
        }
    }
}