Predicate Interpreter

Introduction

For various reasons, I needed to code a logic evaluator in Java to evaluate strings that are really just predicates. An example would be the string "5+3 > 2 && !(33-22 == 121 / 11 || false)", a statement or condition that can only be evaluated to true or false. Here I will go through a detailed explanation on how my PredicateInterpeter object evaluates simple predicate statements with basic Boolean logic - AND '&&', OR '||', parentheses '(', and comparators - '==', '!=', '<=', '>=', '>', '<'!

Evaluating Boolean logic

Here I will explain on how the parsePredicate function is used. parsePredicate is a method within the Predicate Interperter class, which sorts out the Boolean logic of ANDs, ORs and parentheses;

The predicate statement, a string, will be passed through a function called parsePredicate, which firstly picks out any predicates within parentheses, and recursively calls parsePredicate with the contents of the parenthesis as the argument. The evaluated result replaces the parenthesis in the current statement.

// clean up spaces
predicate = predicate.replace(" ", "");
// match furthest brackets
Pattern pattern = Pattern.compile("\\(([^()]|(?R))*\\))");
Matcher matcher = pattern.matcher(predicate);

while (matcher.find()) {
        String match = matcher.group();
        // remove the bracket and trim trailing spaces
        String newPred = match.substring(1, match.length() - 1).trim();
        // check if negative
        boolean rev = matcher.start() != 0 ? new Character(predicate.charAt(matcher.start() - 1)).equals('!')
                        : false;
        //check if the bracket contains comparators OR (|| OR &&) 
        if (isPredicate(newPred)) {
                // evaluate the predicate
                boolean pass = rev ? !parsePredicate(newPred) : parsePredicate(newPred);
                // replace the current predicate statement with result
                predicate = predicate.replaceAll(Pattern.quote(match), pass ? "true" : "false");
        }
}
                
                    

This ensures all parentheses are evaluated first.

Next, we split the statement by ORs(||), generating an array of ‘expressions’.

Each element in this ‘expressions’ array is checked for and split by ANDs(&&), each resulting in an array of ‘ terms’, which is passed individually into the parseTerms function, which evaluates them and returns either true or false.

Each array of ‘terms’ parsed is then iterated to see if any are false. If it is, the ‘parent’ expression would be false, thus the respective element within the ‘expression’ array, is set to false.

                    // sort out OR situations
String[] terms = predicate.split(Pattern.quote("||"));
for (int i = 0; i < terms.length; i++) {
        // sort out AND situations
        String[] exp = terms[i].split(Pattern.quote("&&"));
        for (int i2 = 0; i2 < exp.length; i2++) {
                boolean pass = parseTerms(exp[i2]);
                exp[i2] = pass ? "true" : "false";
        }
        boolean express = true;
        for (String s : exp) {
                if (s.equals("false")) {
                        express = false;
                        continue;
                } else if (!s.equals("true")) {
                        throw new RuntimeException("There are unresolvable expressions");
                }
        }
        terms[i] = express ? "true" : "false";
}
                        

                    

Having evaluated each expression, the ‘expression array’ is then iterated, returning true if any of its members are true, and false otherwise.

                        boolean predi = false;
for (String s : terms) {
        if (s.equals("true")) {
                predi = true;
                break;
        } else if (!s.equals("false")) {
                throw new RuntimeException("There are unresolvable expressions");
        }
}
                            

                    

With this we can evaluate Boolean logic in strings!

Here is the full method:

                        private boolean parsePredicate(String predicate) {

    // clean up spaces
    predicate = predicate.replace(" ", "");
    // match furthest brackets
    Pattern pattern = Pattern.compile("\\(([^()]|(?R))*\\)");
    Matcher matcher = pattern.matcher(predicate);

    while (matcher.find()) {
        String match = matcher.group();
        // remove the bracket and trim trailing spaces
        String newPred = match.substring(1, match.length() - 1).trim();
        // check if negative
        boolean rev = matcher.start() != 0 ? new Character(predicate.charAt(matcher.start() - 1)).equals('!') : false;
        //check if the bracket contains comparators OR (|| OR &&) 
        if (isPredicate(newPred)) {
            // evaluate the predicate
            boolean pass = rev ? !parsePredicate(newPred) : parsePredicate(newPred);
            // replace the current predicate statement with result
            predicate = predicate.replaceAll(Pattern.quote(match), pass ? "true" : "false");
        }
    }
    // sort out OR situations
    String[] terms = predicate.split(Pattern.quote("||"));
    for (int i = 0; i < terms.length; i++) {
        // sort out AND situations
        String[] exp = terms[i].split(Pattern.quote("&&"));
        for (int i2 = 0; i2 < exp.length; i2++) {
            boolean pass = parseTerms(exp[i2]);
            exp[i2] = pass ? "true" : "false";
        }
        boolean express = true;
        for (String s : exp) {
            if (s.equals("false")) {
                express = false;
                continue;
            } else if (!s.equals("true")) {
                throw new RuntimeException("There are unresolvable expressions");
            }
        }
        terms[i] = express ? "true" : "false";
    }
    boolean predi = false;
    for (String s : terms) {
        if (s.equals("true")) {
            predi = true;
            break;
        } else if (!s.equals("false")) {
            throw new RuntimeException("There are unresolvable expressions");
        }
    }
    return predi;
}
                            

                    

Evaluating Comparators

In this section I will explain how I evaluate the different comparators in the predicate. I call each of these singular statement "terms" (i.e "5>3" or "7+2 <= 9"). Each term (As seen from above) would be passed through the parseTerm function. This section is dedicate to explaining how this method works!

parseTerm accepts a string as its argument. Firstly, the first character of the string is compared against the NOT symbol (!), if it is, it recursively calls parseTerm on the remainder of the string, and returns the negated result of this recursive call.

                        if (new Character(term.charAt(0)).equals('!')) {
        return !parseTerms(term.substring(1));
}
                            

                    

Next, if it isn’t a NOT symbol (!), it splits the term by the comparator identified (==, !=, >=, etc), and invokes the MathInterpreter to interpret the value of the left and right expressions.

                        String[] compares = term.split("(==|!=|<=|>=|>|<)");
if (compares.length != 2) {
        throw new RuntimeException(
                        "Syntax error, cannot have more or less than 2 comparing expressions: " + term);
}
Pattern pattern = Pattern.compile("(==|!=|<=|>=|>|<)");
Matcher matcher = pattern.matcher(term);
int xx = 0;
String comparator = null;
while (matcher.find()) {
        xx++;
        comparator = matcher.group();
}
if (xx > 1 || comparator == null) {
        throw new RuntimeException("Syntax error, cannot have more than 1 comparator: " + term);
}
MathInterpreter mi = new MathInterpreter();
double a = mi.parse(compares[0]);
double b = mi.parse(compares[1]);

                    

Now that we obtained the left and right evaluated value (assuming the MathInterpreter works flawlessly), we need to compare the value based on the comparator. This is done by passing the comparator picked out by the regex through a switch statement, which evaluates the comparison between the left and right expressions, returning the respective result.

                        switch (comparator) {
case "==":
        return Math.abs(a - b) < 0.001;
case "!=":
        return Math.abs(a - b) >= 0.001;
case "<=":
        return a <= b || Math.abs(a - b) < 0.001;
case ">=":
        return a >= b || Math.abs(a - b) < 0.001;
case "<":
        return a < b;
case ">":
        return a > b;
default:
        throw new RuntimeException("Unrecognized comparator: " + comparator);
}

                    

That would then return a true of false value, for the parsePredicate method to evaluate!

With this, I would put them all together to form the parseTerm method

                        private boolean parseTerms(String term) {
        if (new Character(term.charAt(0)).equals('!')) {
                return !parseTerms(term.substring(1));
        } else {
                if (term.equals("true")) {
                        return true;
                } else if (term.equals("false")) {
                        return false;
                } else {
                        String[] compares = term.split("(==|!=|<=|>=|>|<)");
                        if (compares.length != 2) {
                                throw new RuntimeException(
                                                "Syntax error, cannot have more or less than 2 comparing expressions: " + term);
                        }
                        Pattern pattern = Pattern.compile("(==|!=|<=|>=|>|<)");
                        Matcher matcher = pattern.matcher(term);
                        int xx = 0;
                        String comparator = null;
                        while (matcher.find()) {
                                xx++;
                                comparator = matcher.group();
                        }
                        if (xx > 1 || comparator == null) {
                                throw new RuntimeException("Syntax error, cannot have more than 1 comparator: " + term);
                        }
                        MathInterpreter mi = new MathInterpreter();
                        double a = mi.parse(compares[0]);
                        double b = mi.parse(compares[1]);
                        switch (comparator) {
                        case "==":
                                return Math.abs(a - b) < 0.001;
                        case "!=":
                                return Math.abs(a - b) >= 0.001;
                        case "<=":
                                return a <= b || Math.abs(a - b) < 0.001;
                        case ">=":
                                return a >= b || Math.abs(a - b) < 0.001;
                        case "<":
                                return a < b;
                        case ">":
                                return a > b;
                        default:
                                throw new RuntimeException("Unrecognized comparator: " + comparator);
                        }
                }
        }
}
                            

                    

Conclusion

It is not very hard to evaluate logic from a string as if it is a interpreter or compiler! Do note that this write up assumes the MathInterpreter object is able to evaluate basic math functions that are in string format. I wrote a MathInterpreter using the concept of a recursive descent parser which I also did a write up on how it is done here!