I am struggling with one expression

The basic requirement is 2 variables cannot be divided or multiplied. The expression gets complexed when we have to handle the BODMAS

Lets Say the Expression is

#f_1# this is equal to one variable

#f_1#/#f_2# (Valid) RegEx should Capture this expression

#f_1# 1000/#f_2# (Invalid) RegEx should not capture this

((#f_1#) 1000)/#f_2# (Valid) RegEx should capture this because according to BODMAS first brackets will be solved and the result is #f_1# 1000 and now expression is

#f_1# 1000/#f_2# which means fields are divided and we need to capture this pattern where 2 fields are getting divide and multiplied only

In the end

CodePudding user response：

I doubt regex can handle this. Even if you make it happen with a complex expression you would not be able to maintain it. To stay with simple, easy to understand code go for the recursive descent parser as already suggested.

https://www.antlr.org/ is definitely worth a look. In the documentation you may even get a definition how far you can go with regex, lexers and when to start looking at parsers.

CodePudding user response：

Regular expressions cannot do the nesting of arithmetic expressions with parentheses.

One solution is to consecutively apply redexes, reducible expressions.

Expression: ((#f_1#) 1000*20)/#f_2#
Reduced expression: @6
Expression tree: {@0=#f_1#, @1=#f_2#, @2=1000, @3=20, @4=@2*@3, @5=@0 @4, @6=@5/@1}

Expression nodes are represented as '@' number.

With (quite ugly written):

private void stackOverflow() {
    String expr = "((#f_1#) 1000*20)/#f_2#";
    System.out.println("Expression: "   expr);

    Map<String, String> vars = new HashMap<>();
    expr = reduceVars(expr, vars);
    expr = reduceNumbers(expr, vars);
    boolean changed;
    do {
        changed = false;
        String expr2 = reduceParentheses(expr, vars);
        if (!expr.equals(expr2)) {
            changed = true;
            expr = expr2;
            continue;
        }
        expr2 = reduceMultiplicative(expr, vars);
        if (!expr.equals(expr2)) {
            changed = true;
            expr = expr2;
            continue;
        }
        expr2 = reduceAdditive(expr, vars);
        if (!expr.equals(expr2)) {
            changed = true;
            expr = expr2;
        }
    } while (changed);

    System.out.println("Reduced expression: "   expr);
    System.out.println("Expression tree: "   vars);
}

The above enforces the BODMAS rule.

private String addVar(MatchResult mr,  Map<String, String> vars) {
    String v = "@"   vars.size();
    vars.put(v, mr.group());
    return v;
}

I use a simplified variable '@' number.

private String reduceVars(String expr, Map<String, String> vars) {
    return Pattern.compile("#\\w #").matcher(expr).replaceAll(mr -> addVar(mr, vars));
}

private String reduceNumbers(String expr, Map<String, String> vars) {
    return Pattern.compile("(?<!@)\\d ").matcher(expr).replaceAll(mr -> addVar(mr, vars));
}

private String reduceParentheses(String expr, Map<String, String> vars) {
    return Pattern.compile("\\((@\\d )\\)").matcher(expr).replaceAll(mr -> mr.group(1));
}

private String reduceMultiplicative(String expr, Map<String, String> vars) {
    return Pattern.compile("@\\d [/*]@\\d ").matcher(expr).replaceAll(mr -> addVar(mr, vars));
}

private String reduceAdditive(String expr, Map<String, String> vars) {
    return Pattern.compile("@\\d [- ]@\\d ").matcher(expr).replaceAll(mr -> addVar(mr, vars));
}

This is a simplification. You are actually building an expression tree, and you can do common sub-expression elimination, getting a directed acyclic graph i.o. a tree.