遞歸調(diào)用
先拷貝一下百科上遞歸調(diào)用的定義啊：
- 遞歸調(diào)用是一種特殊的嵌套調(diào)用，是某個(gè)函數(shù)調(diào)用自己或者是調(diào)用其他函數(shù)后再次調(diào)用自己的额嘿，只要函數(shù)之間互相調(diào)用能產(chǎn)生循環(huán)的則一定是遞歸調(diào)用交洗，遞歸調(diào)用一種解決方案，一種是邏輯思想，將一個(gè)大工作分為逐漸減小的小工作哼蛆。
- 就比如一個(gè)人吃飯蕊梧，我們不知道飯到底有多少，需要多少口能夠吃完腮介。我們只定義一個(gè)“吃一口”的方法肥矢，每次執(zhí)行“吃一口”之后，就再次調(diào)用這個(gè)方法叠洗，直到飯變成空的了甘改。
遞歸的思想，一個(gè)大型的復(fù)雜的問(wèn)題灭抑，層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解十艾，遞歸策略只需少量的程序就可描述出解題過(guò)程。遞歸過(guò)程中腾节，一定有一個(gè)結(jié)束條件忘嫉，當(dāng)滿足這個(gè)條件之后，程序就返回案腺，不再繼續(xù)遞歸調(diào)用庆冕。
解析一個(gè)四則運(yùn)算表達(dá)式
一個(gè)自定義的四則運(yùn)算公式：
(-${a} + ($ + ${c} * $lrxdpzz) - 3 * 7 * ${e}) * ${f}
其中 a ~ f救湖，都是變量愧杯，通過(guò) "${}" 包裹，給出 a ~ f 的值以后鞋既，計(jì)算這個(gè)公式的結(jié)果力九。可以將這個(gè)表達(dá)式邑闺，解析為每一步運(yùn)算的過(guò)程跌前，即每次都是兩個(gè)變量進(jìn)行操作，最后得出結(jié)果陡舅。
按照四則運(yùn)算的規(guī)則抵乓，先對(duì)括號(hào)進(jìn)行解析，當(dāng)解析為不包含括號(hào)的表達(dá)式后靶衍，再按照先乘除灾炭，后加減解析的規(guī)則，進(jìn)行拆分颅眶，直到解析為兩個(gè)變量的操作蜈出，得到下面這樣的解析結(jié)果：
(-${a} + ($ + ${c} * $1ljz977) - 3 * 7 * ${e}) * ${f}
var0 = ${c}*$zrvjzn9
var1 = $涛酗+${var0}
var2 = 3*7
var3 = ${var2}*${e}
var4 = 0-${a}
var5 = ${var4}+${var1}
var6 = ${var5}-${var3}
var7 = ${var6}*${f}
每一步的結(jié)果铡原，用一個(gè)變量保存偷厦，下面的表達(dá)式會(huì)引用該變量，最后一個(gè)表達(dá)式的結(jié)果燕刻，就是最終結(jié)果只泼。
代碼實(shí)現(xiàn)
- parseFormula：解析表達(dá)式，解析括號(hào)部分卵洗。
如果表達(dá)式中沒(méi)有括號(hào)了请唱，則調(diào)用解析四則運(yùn)算的方法。如果有括號(hào)忌怎，將括號(hào)中的字符串籍滴，再次調(diào)用本身方法。最后括號(hào)部分用變量替換榴啸，再次調(diào)用本身方法進(jìn)行處理孽惰。 - parseFourArithmetic：解析四則運(yùn)算。
如果表達(dá)式中只包含同一類(lèi)運(yùn)算符號(hào)鸥印，即只有加減或者乘除勋功，則調(diào)用解析簡(jiǎn)單表達(dá)式的方法。如果加減和乘除都存在库说，將乘除部分取出狂鞋，再次調(diào)用本身方法。最后乘除部分用變量替換潜的，再次調(diào)用本身方法進(jìn)行處理骚揍。 - parseSimpleFormula：解析簡(jiǎn)單表達(dá)式。
此時(shí)的輸入的表達(dá)式啰挪，只包含加減信不，或者乘除了，只需從左往右進(jìn)行解析亡呵。如果只包含一個(gè)操作符號(hào)了抽活，則返回；否則將前面兩個(gè)變量替換后锰什，再次調(diào)用本身方法處理下硕。
最終，通過(guò)上面三個(gè)方法的遞歸調(diào)用汁胆，將表達(dá)式解析為n條只包含一個(gè)運(yùn)算符號(hào)的表達(dá)式梭姓。
計(jì)算時(shí)，循環(huán)遍歷解析結(jié)果嫩码，進(jìn)行變量的替換誉尖，將每一步的結(jié)果都放入變量的map中，后續(xù)的計(jì)算會(huì)用到谢谦。最后一個(gè)表達(dá)式的結(jié)果释牺，就是最終的結(jié)果了。
PS：解析出的List<Formula>表達(dá)式集合回挽，可以根據(jù)表達(dá)式字符串没咙，緩存下來(lái)，下一次就不需要解析了千劈，直接根據(jù)字符串獲取緩存的表達(dá)式集合即可
import lombok.Data;
import lombok.extern.slf4j.Slf4j;
import java.math.BigDecimal;
import java.util.*;
/**
* @Description 四則運(yùn)算公式工具類(lèi)
*/
@Slf4j
public class FormulaUtil {
public static void main(String[] args) {
String str = "(-${a} + ($祭刚 + ${c} * $pdz7pdf) - 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);
}
/**
* 解析并計(jì)算表達(dá)式
* @param str 表達(dá)式
* @param varMap 變量map
* @return 結(jié)果
*/
public static double calculate(String str, Map<String, Number> varMap) {
return calculate(parseFormula(str), varMap);
}
/**
* 計(jì)算表達(dá)式
* @param formulaList 步驟表達(dá)式
* @param varMap 變量map
* @return 結(jié)果
*/
public static double calculate(List<Formula> formulaList, Map<String, Number> varMap) {
if (formulaList == null || formulaList.isEmpty()) {
throw new IllegalArgumentException("計(jì)算流程不能為空 formulaList is null or empty");
}
Number res = null;
for (Formula formula : formulaList) {
res = formula.calculate(varMap);
varMap.put(formula.getVariable(), res);
}
return res.doubleValue();
}
/**
* 解析表達(dá)式
* @param formula 表達(dá)式
* @return 結(jié)果
*/
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("公式異常, 左括號(hào)和右括號(hào)數(shù)量不相等");
}
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);
// 括號(hào)里面的表達(dá)式
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;
}
/**
* 解析只包含四則運(yùn)算的表達(dá)式，不包含括號(hào)
* @param formula 表達(dá)式
* @return 結(jié)果
*/
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("公式錯(cuò)誤: " + formula);
}
List<Formula> formulaList = new ArrayList<>();
if ((addSubCount + mutDivCount) == 1) {
formulaList.add(new Formula(formula));
return formulaList;
}
if (mutDivCount == 0) {
// 僅有加減算術(shù)符號(hào)
formulaList.addAll(parseSimpleFormula(formula, addSub));
return formulaList;
} else if (addSubCount == 0) {
// 僅有乘除算術(shù)符號(hào)
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;
}
/**
* 解析只包含同一類(lèi)運(yùn)算符的表達(dá)式墙牌，只包含加減涡驮，或者乘除
* @param formula 表達(dá)式
* @param typeChars 加減，或者乘除 的運(yùn)算符號(hào)
* @return 最終結(jié)果：僅有兩個(gè)變量的操作表達(dá)式
*/
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;
}
/**
* 找到左括號(hào)對(duì)應(yīng)的右括號(hào)位置
* @param formula 表達(dá)式
* @param leftIndex 左括號(hào)索引位置
* @return 右括號(hào)位置
*/
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 = "[\\$\\{\\}]";
/**
* 該表達(dá)式結(jié)果的變量名
*/
private String variable;
/**
* 表達(dá)式
*/
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("表達(dá)式錯(cuò)誤: " + formulaStr + "喜滨，+ - * / 符號(hào)兩側(cè)必須是變量或者常量");
}
String var1 = fs[0];
String var2 = fs[1];
// 運(yùn)算符號(hào)
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("被除數(shù) ${" + var2 + "}: 不能為0");
}
res = b1.divide(b2, 8, BigDecimal.ROUND_HALF_DOWN);
} else {
throw new IllegalArgumentException("運(yùn)算符號(hào)：" + symbol + " 錯(cuò)誤捉捅，支持: + - * /");
}
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 + " 的值，請(qǐng)檢查");
}
} else if (var1.matches(numberRegex)) {
n1 = Double.valueOf(var1);
} else {
throw new IllegalArgumentException("表達(dá)式：" + 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;
}
}
}
