递归调用
先拷贝一下百科上递归调用的定义啊：
- 递归调用是一种特殊的嵌套调用，是某个函数调用自己或者是调用其他函数后再次调用自己的，只要函数之间互相调用能产生循环的则一定是递归调用，递归调用一种解决方案，一种是逻辑思想，将一个大工作分为逐渐减小的小工作。
- 就比如一个人吃饭，我们不知道饭到底有多少，需要多少口能够吃完。我们只定义一个“吃一口”的方法，每次执行“吃一口”之后，就再次调用这个方法，直到饭变成空的了。
递归的思想，一个大型的复杂的问题，层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程。递归过程中，一定有一个结束条件，当满足这个条件之后，程序就返回，不再继续递归调用。
解析一个四则运算表达式
一个自定义的四则运算公式：
(-${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;
}
}
}
