关于java:Java-实现数学公式的正则校验和结果计算

96次阅读

共计 8350 个字符,预计需要花费 21 分钟才能阅读完成。

最近工作中遇到一个需要,须要校验数学公式字符串是否非法,并计算公式的后果。

数学公式中有括号,运算符和变量,其中变量是从数据库中读取的,能够任意增加和删除。

假如内置变量为: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.3111111111111

2.2 应用算法

自行编写一个算法来实现公式计算,能够在更短的工夫内拿到计算结果,不过须要保障算法的准确性。

网上这篇文章 java 实现计算简单数学表达式 提供了一个很好的思路,不过这篇文章的代码只反对单位数的计算,并且在局部状况下会计算错误。

思路就是分两步来进行

  1. 翻译输出的数学表达式,也就是中断表达式转后缀表达式。例如 a+b*(c-d) 转为后缀表达式就是 abcd-*+
  2. 对后缀表达式计算结果。这里用到了栈存储计算结果,每次都是对两个数计算,例如 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 来存储后缀表达式。

一一字符遍历数学算式的字符串,生成后缀表达式,步骤如下:

  1. 如果遇到数字或小数点,则将以后字符暂存到多位数链中。
  2. 如果遇到运算符,先将多位数链中的已有内容全副取出,存入后缀表达式链,再进行下一步判断。
  3. 如果以后字符是左括号,间接将其压入运算符栈。
  4. 如果以后字符是加减乘除运算符,则须要与运算符栈栈顶的运算符进行比照:
    如果以后运算符优先级更高,则间接入栈;
    否则重复弹出栈顶元素至后缀表达式链,直到以后运算符优先级高于栈顶运算符,再将以后运算符入栈。
  5. 如果以后字符是右括号,重复将运算符栈顶元素弹出到后缀表达式,直到栈顶元素是左括号为止,并将左括号从栈中弹出抛弃。
  6. 遍历完结时,如果多位数链或运算符栈中还有数据,则补到后缀表达式链中。

实现如下:

/**
 * 将中断表达式,转换为后缀表达式,反对多位数、小数
 * 
 * @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 = -12

2.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…

正文完
 0