ponkin - 3 months ago 11
Scala Question

# How to get rid of braces in boolean expressions with AND and OR

Let`s say I have some simple boolean expression

``````(A || B) && (C || D)
``````

The goal is, to get rid of braces in this expression, for example

``````(A || B) && (C || D) => A && C || A && D || B && C || B && D
``````

We know that
`&&`
evaluates before
`||`
from left to right.
To achieve this I have created the following algebraic data type:

``````sealed trait Predicate
case class Or(left: Predicate, right: Predicate) extends Predicate
case class And(left: Predicate, right: Predicate) extends Predicate
case object True extends Predicate
case object False extends Predicate
``````

Let`s assume that we already have some kind of string parser, which converts string to
`Predicate`
, it builds some kind of Abstract Syntactic Tree.
For example for expression
`(true || true) && (true || true)`
we will have the following tree:
`And(Or(True, True), Or(True, True))`
. Here we get into account the braces. We need to get
`Or(Or(And(A, C), And(A, D)), Or(And(B, C), And(B,D)))`
.
I stuck with the following solution:

``````def extractOr(pred: Predicate): Predicate = pred match {
case And(Or(l, r), Or(ll, rr)) => Or(Or(And(l, ll), And(l, rr)), Or(And(r, ll), And(r, rr)))
case And(Or(l, r), p) => Or(And(l, p), And(r, p))
case And(p, Or(l, r)) => Or(And(p, l), And(p, r))
case p => p
}

def popOrPredicateUp(pred: Predicate): Predicate = pred match {
case And(l, r) => extractOr(And(popOrPredicateUp(l), popOrPredicateUp(r)))
case Or(l, r) => Or(popOrPredicateUp(l), popOrPredicateUp(r))
case p => p
}
``````

But it works incorrect for example for this case:
`And(False, Or(And(Or(True, True), False), True))`

UPD: As @coredump pointed out, I need to get DNF(sum of products)

Finally, with great help @coredump(he pointed out the right direction) and Haskell package `hatt`(particulary that code). I came to the following solution:

``````sealed trait Predicate
case class Or(left: Predicate, right: Predicate) extends Predicate
case class And(left: Predicate, right: Predicate) extends Predicate
case class Not(pred: Predicate) extends Predicate
case object True extends Predicate
case object False extends Predicate

object PredicateOps{

def toNNF(pred: Predicate): Predicate = pred match {
case a @ (True | False) => a
case a @ Not( True | False) => a
case Not(Not(p)) => p
case And(l, r) => And(toNNF(l), toNNF(r))
case Not(And(l, r)) => toNNF( Or(Not(l), Not(r)))
case Or(l, r) => Or(toNNF(l), toNNF(r))
case Not(Or(l,r)) => toNNF( And(Not(l), Not(r)))
}

def dist(predL: Predicate, predR: Predicate): Predicate = (predL, predR) match {
case (Or(l, r), p) => Or(dist(l, p), dist(r, p))
case (p, Or(l, r)) => Or(dist(p, l), dist(p, r))
case (l, r) => And(l, r)
}

def toDNF(pred: Predicate): Predicate = pred match {
case And(l, r) => dist(toDNF(l), toDNF(r))
case Or(l, r) =>  Or(toDNF(l), toDNF(r))
case p => p
}

}
``````

Here is how it works:

``````val expr = And(False, Or(And(Or(True, True), False), True))
val dnf = (PredicateOps.toNNF _ andThen PredicateOps.toDNF _).apply(expr)
println(dnf)
``````

And the output ```Or(Or(And(False,And(True,False)),And(False,And(True,False))),And(False,True)) ``` which is correct DNF.