Is there a data structure for storing boolean expressions?

Question

I need to store Boolean expressions like this:

x1 AND x2 AND x3 OR (x4 AND x5) AND (NOT x6)

Each x variable is a Boolean expression like == or != with values. The problem is to store nested AND and OR clauses (inside themselves and/or inside each other) and wrap them with NOT. The wrapping depth can be very deep.

Does the Java SDK have data structure for these expressions?

Boolean expressions are, after all, mathematical expressions, and to deal with them properly I would think you would need a symbolic manipulation library, as Java (and most programming languages) are only going to handle numeric manipulation out of the box. Google suggests: https://github.com/yuemingl/SymJava — chiliNUT, Feb 21 '17 at 04:21

score 2 · Answer 1 · edited Feb 21 '17 at 04:09

In Java 8 the functional interface Predicate<T> is the way to go.

Here are the Java docs.

And here are various examples.

So in your use case it will be something as follows:

public static Predicate<Integer> equals(Integer compare) {
    return i -> i.equals(compare);
}

public static Predicate<Integer> complex() {
    return equals(1).and(equals(2)).and(equals(3)).or(equals(4).and(equals(5))).and(equals(6).negate());
}

Remember — only Java 8 onwards!

score 0 · Answer 2 · edited May 23 '17 at 10:29

You can try to use jexl (http://commons.apache.org/jexl/)

JexlEngine jexl = new JexlEngine();
    jexl.setSilent(true);
    jexl.setLenient(true);

    Expression expression = jexl.createExpression("(a || b && (c && d))");
    JexlContext jexlContext = new MapContext();

    //b and c and d should pass
    jexlContext.set("b",true);
    jexlContext.set("c",true);
    jexlContext.set("d",true);

    assertTrue((Boolean)expression.evaluate(jexlContext));

    jexlContext = new MapContext();

    //b and c and NOT d should be false
    jexlContext.set("b",true);
    jexlContext.set("c",true);

    //note this works without setting d to false on the context
    //because null evaluates to false

    assertFalse((Boolean)expression.evaluate(jexlContext));

Example from this question

ps: It is not included in standard sdk but quite easy to use.

score 0 · Answer 3 · edited Feb 21 '17 at 04:10

0

abstract class Predicate {...}
class AndPredicate extends Predicate {
  private Predicate[] conjuncts;
  ...
}
class OrPredicate extends Predicate {
  private Predicate[] disjuncts;
  ...
}
class NotPredicate extends Predicate {
  Predicate negated;
  ...
}

What is the problem?

edited Feb 21 '17 at 04:10

Jonathan Leffler

730,956
141
904
1,278

answered Jun 29 '16 at 10:26

Erwin Smout

18,113
4
33
52

The promlems is - not to reinvent the wheel and support it. There is a lot data structures likr Maps, Lists, Sets, and no one for boolean expressions? – Cherry Jun 29 '16 at 10:29
Such data structures will typically be found in compiler technology. You could search for a compiler that exposes its internal data structures as a public library. Good luck with that. – Erwin Smout Jun 29 '16 at 10:38

Is there a data structure for storing boolean expressions?

3 Answers3