最近工作中遇到一个需要，须要校验数学公式字符串是否非法，并计算公式的后果。
数学公式中有括号，运算符和变量，其中变量是从数据库中读取的，能够任意增加和删除。
假如内置变量为：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 引擎来计算结果，即不便，后果又精确。毛病是计算效率比拟低。
@Test
public 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 如下。
@Test
public 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 = -4
50-1*(5+6)+2 = 41
(50.5-1)*(5+6)+2 = 546.5
1+2*(3-4*(5+6)) = -81
1/2*(3-4*(5+6))*10 = -205
43*(2+1)+2*32+98 = 291
3-10*2+5 = -122.3 性能比照
执行 10000 条公式计算，比照耗时。
/**
* 耗时比照
*/
@Test
public 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…