How to approach the simplification of expression(and, or, not) in Scala?

Question

I am at a loss with how to solve my problem. I have a homework in which I need to simplify expressions using the rules the professor set out. I need to take strings of expressions:

"(and(x x))"
"(or (and x z) y)"
"(and (or z (not x))(or e a))"

and simplify them using rules:

(or x nil) => x; 
(or nil x) => x;
(or 1 x) => 1;
(or x 1) => 1;
(and x nil) => nil; 
(and nil x) => nil;
(and x 1) => x; 
(and 1 x) => x;
(not nil) => 1;
(not 1) => nil;
(not (and x y)) => (or (not x) (not y));
(not (or x y)) => (and (not x) (not y));

I decided to take the expressions in the exact form that it is above (can't be any other way), and parse it into an array, so in each index for example, it would look like this:

and or x y z //ArrayBuffer[String]

I then use a recursive function which checks the left and right expressions, until it gets the simplified expression. My problem is not with the rules, as I have figured that out. I essentially have 3 cases done, which are:

"(and z (or x y)" // the case when the left symbol is simple but the right side must be recursed
"(and (or x y) z)" // case when the right symbol is simple but the right side must be recursed
"(and x y)" // simple case where no recursion is necessary

I am missing the case when both the left and right symbols must be recursed in order to obtain those simplified symbols. I don't have a way to know when they end or begin, and there could be many cases in which it must be recursed even within those inner expressions:

"(and (or (and x y) z)(or x a))"
"(and (or (and x y) z)(or (and y z) a))"

I have thought about how this can be done in an efficient manner with the current implementation I have, but haven't gotten anything yet. I am asking for some advice on how to go about it. I am providing no code as I would like to get it done on my own, just need a nudge in the right direction. If clarification is needed, please ask and I will do so. Thanks again advance!

Answer 1

I think this is covered in the Scala by Example book available as a PDF from the scala lang website (see Chapter 7). My suggestion would be to use case classes to represent your expressions and then use pattern matching to simplify the expressions:

To start with lets define an expression trait that will be used to represent all kinds of expressions.

scala> trait Expr { def simplify:Expr = this }
defined trait Expr

Here I have let the Expr trait implement a default simplify method that just returns the object that extends the trait. So lets add a few simple Expressions:

scala> case object True extends Expr
defined module True

scala> case object False extends Expr
defined module False

scala> case class Var(name:String) extends Expr { override def toString = name }
defined class Var

True and False would represent 1 and nil in your example. Var will be used to represent a variable that does not have a truth value yet, e.g. x, y, a and b in your example. Var also overides the toString method to make the printout a little prettier :)

Now to the a bit trickier situation with and/or. Lets define these like:

scala> case class And(a:Expr, b:Expr) extends Expr {
     | override def simplify = (a.simplify, b.simplify) match {
     | case (True,x) => x
     | case (x,True) => x
     | case (False,x) => False
     | case (x,False) => False
     | case (x,y) => And(x,y)
     | }
     | }
defined class And

scala> case class Or(a:Expr, b:Expr) extends Expr {
     | override def simplify = (a.simplify, b.simplify) match {
     | case (True,x) => True
     | case (x,True) => True
     | case (False,x) => x
     | case (x,False) => x
     | case (x,y) => Or(x,y)
     | }
     | }
defined class Or

And and Or both override the simplify method in the Expr trait and return simplified versions of themselves and their subexressions. Now these can be used to build expressions along with the simpler True, False and Var expressions:

scala> val X = Var("X"); val Y = Var("Y"); val A = Var("A"); val B = Var("B")
X: Var = X
Y: Var = Y
A: Var = A
B: Var = B

scala> And(X, True).simplify
res10: Expr = X

scala> And(X, And(Y, False)).simplify
res11: Expr = False

scala> And(X, Or(Y, False)).simplify
res12: Expr = And(X,Y)

scala> Or(True, And(X, Or(Y, False))).simplify
res13: Expr = True

Finally we add the an expression for not:

scala> case class Not(a:Expr) extends Expr {
     | override def simplify = a.simplify match {
     | case True => False
     | case False => True
     | case And(x,y) => Or(Not(x),Not(y))
     | case Or(x,y) => And(Not(x),Not(y))
     | case Not(x) => x
     | case x => Not(x)
     | }
     | }
defined class Not

Now we can represent the expressions in your example. However for some expression this Not case class would not do a complete simplification, e.g.

scala> Not(Or(Not(X),Y)).simplify
res41: Expr = And(Not(Not(X)),Not(Y))

So we could define a recursive function in Not that tries to simplify the expression until it can't simplify it any more:

scala> case class Not(a:Expr) extends Expr {
     | override def simplify = recursiveSimplify(a, a)
     | private def recursiveSimplify(curExpr:Expr, lastExpr:Expr):Expr = if(curExpr != lastExpr) {
     | val newExpr = curExpr.simplify match {
     | case True => False
     | case False => True
     | case Var(x) => Not(Var(x))
     | case Not(x) => x
     | case And(x,y) => Or(Not(x), Not(y))
     | case Or(x,y) => And(Not(x), Not(y))
     | }
     | recursiveSimplify(newExpr, curExpr)
     | } else {
     | lastExpr
     | }
     | }
defined class Not

Now the earlier expression simplifies to:

scala> Not(Or(Not(X),Y)).simplify
res42: Expr = Or(Not(X),Y)

Answer 2

Here's a simple implementation for dhg's solution:

package solve

sealed trait Expr
case class Not(e:Expr) extends Expr
case class And(e1:Expr, e2:Expr) extends Expr
case class Or(e1:Expr, e2:Expr) extends Expr
case class Idn(v:String) extends Expr
object Solve extends App {
  def prep(s:String):List[String] =
    s.replaceAll("[()]+"," ").split(" ").filter(_.size > 0).toList
  def parse(l:List[String]):Expr =
    parseI(l) match {
      case (e,Nil) => e
      case _ => throw new Exception("malformed exception")
    }
  def parseI(l:List[String]):(Expr,List[String]) =
    l match {
      case "not" :: rest =>
        val (e, rem) = parseI(rest)
        (Not(e), rem)
      case "and" :: rest =>
        val (e1, rem) = parseI(rest)
        val (e2, rem2) = parseI(rem)
        (And(e1,e2), rem2)
      case "or" :: rest =>
        val (e1, rem) = parseI(rest)
        val (e2, rem2) = parseI(rem)
        (Or(e1,e2), rem2)
      case i :: rest =>
        (Idn(i), rest)
      case Nil => throw new Exception
    }
  def simplify(e:Expr):Expr = {
    e match {
      case Or(x,Idn("nil")) => simplify(x)
      case Or(Idn("1"),x) => Idn("1")
      case Or(x,y) => Or(simplify(x),simplify(y))
      case x => x
    }
  }  
}

And a test case for it:

import org.scalatest.FunSuite
import org.scalatest.matchers.ShouldMatchers
import solve._
import Solve._

class SolveTest extends FunSuite with ShouldMatchers {
  test ("prepare expression") {
    prep("(and(x x))") should equal (List("and","x","x"))
  }
  test ("parse expressions") {
    parse(prep("(and(x x))")) should equal (And(Idn("x"), Idn("x")))
    parse(prep("(or (and x z) y)")) should equal (Or(And(Idn("x"), Idn("z")), Idn("y")))
    parse(prep("(and (or z (not x))(or e a))")) should equal (And(Or(Idn("z"),Not(Idn("x"))),Or(Idn("e"),Idn("a"))))
  }
  test ("simplification") {
    simplify(parse(prep("(or (and x z) nil)"))) should equal (And(Idn("x"),Idn("z")))
  }
}

Answer 3

and or x y z //ArrayBuffer[String]

I would avoid representing an expression like this. While is is possible to unambiguously get the structure of the expression in prefix notion, it's not quite as easy as when you have a recursive structure.

You should instead represent the expression with a recursively-defined class hierarchy. Without giving too many details, you will probably have an interface (a Trait or abstract Class), and implementers of that interface that depend on the number of arguments: one for expressions with three parts (like ((or, x, y), or (and, (or x y), z))), one for expressions with two parts (like (not, x)), and one for expressions with one part (like x, y, z, nil, etc).

Then your simplification procedure becomes one big pattern-matching method that can call itself recursively to traverse the expression's parse tree:

def simplify(expression: ExpressionIterface) = 
    expression match {
        case /* pattern */ => /* result, possibly with a recursive call to simplify */
        ...
    }

EDIT: Converting the ArrayBuffer[String] into your classes could be done with a simple recursive parsing function since you know how many arguments should be associated with each operator. You could traverse the buffer, and every time you see an and or or, you start creating a 3-part expression, every time you see a not, you start creating a 2-part expression, and you create a 1-part expression for anything else.