最近工作中遇到一个需要，须要校验数学公式字符串是否非法，并计算公式的后果。
数学公式中有括号，运算符和变量，其中变量是从数据库中读取的，能够任意增加和删除。
假如内置变量为：height、length、width、num。对于公式字符串如 (length*(1+width)/height)*num，须要校验公式格局是否非法，而后对变量进行赋值，计算公式的运算后果。
1. 公式校验
对公式进行校验，除了一些常规性的查看之外，还须要对公式的格局进行优化，为后续的公式计算扫清阻碍。
优化内容包含：
- 去掉公式中的空格。
- 对正数和负数进行补零，例如
-a优化为0-a。 - 补充两个括号之间的乘法运算符，例如
(a+b)(b+c)优化为(a+b)*(b+c)。
残缺的校验逻辑如下：
import org.apache.commons.lang3.StringUtils;import org.junit.Test;import java.util.Arrays;import java.util.List;import java.util.Stack;import java.util.regex.Pattern;/** * @author Sumkor * @since 2021/7/14 */public class ValidateTest { @Test public void test() { List<String> variables = Arrays.asList("height", "length", "width", "num"); String result01 = validate("(height+length)(width+num)", variables); System.out.println("result01 = " + result01); String result02 = validate("-num+100", variables); System.out.println("result02 = " + result02); String result03 = validate("(length*(1+width)/height)*num", variables); System.out.println("result03 = " + result03); } /** * 应用正则来校验数学公式 * * @param expression 数学公式，蕴含变量 * @param variables 内置变量汇合 */ private String validate(String expression, List<String> variables) { if (variables == null || variables.isEmpty()) { throw new RuntimeException("内置变量为空"); } // 去空格 expression = expression.replaceAll(" ", ""); // 间断运算符解决 if (expression.split("[\\+\\-\\*\\/]{2,}").length > 1) { throw new RuntimeException("公式不非法，蕴含间断运算符"); } if (StringUtils.contains(expression, "()")) { throw new RuntimeException("公式不非法，蕴含空括号"); } expression = expression.replaceAll("\\)\\(", "\\)*\\("); expression = expression.replaceAll("\\(\\-", "\\(0-"); expression = expression.replaceAll("\\(\\+", "\\(0+"); // 校验变量 String[] splits = expression.split("\\+|\\-|\\*|\\/|\\(|\\)"); for (String split : splits) { if (StringUtils.isBlank(split) || Pattern.matches("[0-9]+", split)) { continue; } if (!variables.contains(split)) { throw new RuntimeException("公式不非法，蕴含非法变量或字符"); } } // 校验括号 Character preChar = null; Stack<Character> stack = new Stack<>(); String resultExpression = expression; for (int i = 0; i < expression.length(); i++) { char currChar = expression.charAt(i); if (i == 0) { if (Pattern.matches("\\*|\\/", String.valueOf(currChar))) { throw new RuntimeException("公式不非法，以谬误运算符结尾"); } if (currChar == '+') { resultExpression = expression.substring(1); } if (currChar == '-') { resultExpression = "0" + expression; } } if ('(' == currChar) { stack.push('('); } else if (')' == currChar) { if (stack.size() > 0) { stack.pop(); } else { throw new RuntimeException("公式不非法，括号不配对"); } } if (preChar != null && preChar == '(' && Pattern.matches("[\\+\\-\\*\\/]+", String.valueOf(currChar))) { throw new RuntimeException("公式不非法，左括号后是运算符"); } if (preChar != null && preChar == ')' && !Pattern.matches("[\\+\\-\\*\\/]+", String.valueOf(currChar))) { throw new RuntimeException("公式不非法，右括号前面不是运算符"); } if (i == expression.length() - 1) { if (Pattern.matches("\\+|\\-|\\*|\\/", String.valueOf(currChar))) throw new RuntimeException("公式不非法，以运算符结尾"); } preChar = currChar; } if (stack.size() > 0) { throw new RuntimeException("公式不非法，括号不配对"); } return resultExpression; }}2. 公式计算
当数学公式字符串的合法性校验通过，并且对其中的变量进行赋值之后，就能够计算它的运算后果了。
这里别离应用 JDK 内置的 JS 引擎、自己实现的后缀表达式算法，来计算数学公式字符串的运算后果，并比照两者的运算效率。
2.1 应用 JS 引擎
利用 JDK 内置的 JS 引擎来计算结果，即不便，后果又精确。毛病是计算效率比拟低。
@Testpublic void scriptEngine() throws ScriptException { String str = "43*(2+1.4)+2*32/(3-2.1)"; ScriptEngineManager manager = new ScriptEngineManager(); ScriptEngine engine = manager.getEngineByName("js"); Object result = engine.eval(str); System.out.println("后果类型:" + result.getClass().getName() + ",计算结果:" + result);}运行后果：
后果类型:java.lang.Double,计算结果:217.31111111111112.2 应用算法
自行编写一个算法来实现公式计算，能够在更短的工夫内拿到计算结果，不过须要保障算法的准确性。
网上这篇文章 java实现计算简单数学表达式 提供了一个很好的思路，不过这篇文章的代码只反对单位数的计算，并且在局部状况下会计算错误。
思路就是分两步来进行
- 翻译输出的数学表达式，也就是中断表达式转后缀表达式。例如
a+b*(c-d)转为后缀表达式就是abcd-*+- 对后缀表达式计算结果。这里用到了栈存储计算结果，每次都是对两个数计算，例如
abcd-*+，计算方法是先从头遍历，数字间接入栈，当遇到计算符，则从栈顶取出来两个数计算而后再把后果压栈，最终全副计算完之后栈外面只剩下一个元素就是后果。
本文同样以这种思路进行实现，反对对多位数、小数点的计算，并进行验证。
2.2.1 如何应用后缀表达式
本算法的外围思路是把数学公式从中缀表达式转后缀表达式，例如 3-10*2+5 转换为后缀表达式就是 3, 10, 2, *, -, 5, +。
在探讨如何生成后缀表达式之前，先看下如何应用后缀表达式来计算结果。
参数定义
- 应用链表 LinkedList 来存储后缀表达式的每一个元素，元素可能是数值，也可能是运算符，因而定义元素类型为字符串。
- 因为反对多位数、小数点的计算，应用 BigDecimal 类型作为运算后果。
/** * 依据后缀表达式，失去计算结果 */private static BigDecimal doCalculate(LinkedList<String> postfixList) { // 操作数栈 Stack<BigDecimal> numStack = new Stack<>(); while (!postfixList.isEmpty()) { String item = postfixList.removeFirst(); BigDecimal a, b; switch (item) { case "+": a = numStack.pop(); b = numStack.pop(); numStack.push(b.add(a)); break; case "-": a = numStack.pop(); b = numStack.pop(); numStack.push(b.subtract(a)); break; case "*": a = numStack.pop(); b = numStack.pop(); numStack.push(b.multiply(a)); break; case "/": a = numStack.pop(); b = numStack.pop(); numStack.push(b.divide(a, 2, RoundingMode.HALF_UP)); break; default: numStack.push(new BigDecimal(item)); break; } } return numStack.pop();}2.2.2 如何生成后缀表达式
利用后缀表达式来取得计算结果，实现起来比较简单，关键在于如何转换失去正确的后缀表达式。
参数定义
- 定义一个运算符栈
Stack<Character> optStack，用于按优先级来调整运算符的程序。 - 定义一个多位数链
LinkedList<Character> multiDigitList，用于暂存数学算式中的多位数、小数点。 - 出参应用链表
LinkedList<String> postfixList来存储后缀表达式。
一一字符遍历数学算式的字符串，生成后缀表达式，步骤如下：
- 如果遇到数字或小数点，则将以后字符暂存到多位数链中。
- 如果遇到运算符，先将多位数链中的已有内容全副取出，存入后缀表达式链，再进行下一步判断。
- 如果以后字符是左括号，间接将其压入运算符栈。
- 如果以后字符是加减乘除运算符，则须要与运算符栈栈顶的运算符进行比照：
如果以后运算符优先级更高，则间接入栈；
否则重复弹出栈顶元素至后缀表达式链，直到以后运算符优先级高于栈顶运算符，再将以后运算符入栈。 - 如果以后字符是右括号，重复将运算符栈顶元素弹出到后缀表达式，直到栈顶元素是左括号为止，并将左括号从栈中弹出抛弃。
- 遍历完结时，如果多位数链或运算符栈中还有数据，则补到后缀表达式链中。
实现如下：
/** * 将中断表达式，转换为后缀表达式，反对多位数、小数 * * @author Sumkor * @since 2021/7/14 */private static LinkedList<String> getPostfix(String mathStr) { // 后缀表达式链 LinkedList<String> postfixList = new LinkedList<>(); // 运算符栈 Stack<Character> optStack = new Stack<>(); // 多位数链 LinkedList<Character> multiDigitList = new LinkedList<>(); char[] arr = mathStr.toCharArray(); for (char c : arr) { if (Character.isDigit(c) || '.' == c) { multiDigitList.addLast(c); } else { // 解决以后的运算符之前，先解决多位数链中暂存的数据 if (!multiDigitList.isEmpty()) { StringBuilder temp = new StringBuilder(); while (!multiDigitList.isEmpty()) { temp.append(multiDigitList.removeFirst()); } postfixList.addLast(temp.toString()); } } // 如果以后字符是左括号，将其压入运算符栈 if ('(' == c) { optStack.push(c); } // 如果以后字符为运算符 else if ('+' == c || '-' == c || '*' == c || '/' == c) { while (!optStack.isEmpty()) { char stackTop = optStack.pop(); // 若以后运算符的优先级高于栈顶元素，则一起入栈 if (compare(c, stackTop)) { optStack.push(stackTop); break; } // 否则，弹出栈顶运算符到后缀表达式，持续下一次循环 else { postfixList.addLast(String.valueOf(stackTop)); } } optStack.push(c); } // 如果以后字符是右括号，重复将运算符栈顶元素弹出到后缀表达式，直到栈顶元素是左括号（为止，并将左括号从栈中弹出抛弃。 else if (c == ')') { while (!optStack.isEmpty()) { char stackTop = optStack.pop(); if (stackTop != '(') { postfixList.addLast(String.valueOf(stackTop)); } else { break; } } } } // 遍历完结时，若多位数链中具备数据，阐明公式是以数字结尾 if (!multiDigitList.isEmpty()) { StringBuilder temp = new StringBuilder(); while (!multiDigitList.isEmpty()) { temp.append(multiDigitList.removeFirst()); } postfixList.addLast(temp.toString()); } // 遍历完结时，运算符栈若有数据，阐明是由括号所致，须要补回去 while (!optStack.isEmpty()) { postfixList.addLast(String.valueOf(optStack.pop())); } return postfixList;}对于运算符栈，左括号会间接入栈，右括号不会入栈。
因而，比照栈顶元素与以后元素的优先级，代码如下：
/** * 比拟优先级 * 返回 true 示意 curr 优先级大于 stackTop */private static boolean compare(char curr, char stackTop) { // 左括号会间接入栈，这里是其余运算符与栈顶左括号比照 if (stackTop == '(') { return true; } // 乘除法的优先级大于加减法 if (curr == '*' || curr == '/') { return stackTop == '+' || stackTop == '-'; } // 运算符优先级雷同时，先入栈的优先级更高 return false;}2.2.3 验证
编写多个 test case 如下。
@Testpublic void calculateTest() { String str = "5-1*(5+6)+2"; System.out.println(str + " = " + calculate(str)); str = "50-1*(5+6)+2"; System.out.println(str + " = " + calculate(str)); str = "(50.5-1)*(5+6)+2"; System.out.println(str + " = " + calculate(str)); str = "1+2*(3-4*(5+6))"; System.out.println(str + " = " + calculate(str)); str = "1/2*(3-4*(5+6))*10"; System.out.println(str + " = " + calculate(str)); str = "43*(2+1)+2*32+98"; System.out.println(str + " = " + calculate(str)); str = "3-10*2+5"; System.out.println(str + " = " + calculate(str));}/** * 1. 将中断表达式转后缀表达式 * 2. 依据后缀表达式进行计算 */public static BigDecimal calculate(String mathStr) { if (mathStr == null || mathStr.length() == 0) { return null; } LinkedList<String> postfixList = getPostfix(mathStr); // System.out.println("后缀表达式：" + postfixList.toString()); return doCalculate(postfixList);}执行后果如下，运算后果正确。
5-1*(5+6)+2 = -450-1*(5+6)+2 = 41(50.5-1)*(5+6)+2 = 546.51+2*(3-4*(5+6)) = -811/2*(3-4*(5+6))*10 = -20543*(2+1)+2*32+98 = 2913-10*2+5 = -122.3 性能比照
执行 10000 条公式计算，比照耗时。
/** * 耗时比照 */@Testpublic void vs() throws ScriptException { long start = System.currentTimeMillis(); ScriptEngineManager manager = new ScriptEngineManager(); ScriptEngine engine = manager.getEngineByName("js"); for (int i = 0; i < 10000; i++) { String str = "43*(2+1.4)+2*32/(3-2.1)" + "+" + i; Object result = engine.eval(str); } System.out.println("耗时：" + (System.currentTimeMillis() - start)); start = System.currentTimeMillis(); for (int i = 0; i < 10000; i++) { String str = "43*(2+1.4)+2*32/(3-2.1)" + "+" + i; BigDecimal result = TransferTest.calculate(str); } System.out.println("耗时：" + (System.currentTimeMillis() - start));}能够看到，JDK 内置 JS 引擎的计算效率，远不如后缀表达式算法。
耗时：5989耗时：71作者：Sumkor
链接：https://segmentfault.com/a/11...