An algebra on regular expressions.

RegExpAlgebra.scala

package core.misc

/**
 * Created by mishael on 12/11/14.
 *
 */
object RegExpAlgebra {
  case class Singleton(regExp: String) extends RegExpAlgebra
  case class ~!(inner: RegExpAlgebra) extends RegExpAlgebra
  case class And(l: RegExpAlgebra, r: RegExpAlgebra) extends RegExpAlgebra
  case class Or(l: RegExpAlgebra, r: RegExpAlgebra) extends RegExpAlgebra

  implicit class RichString(val regExp: String) extends AnyVal {
    def rEA = Singleton(regExp)
  }

  def matches(wrapper: RegExpAlgebra, str: String): Boolean =
    wrapper match {
      case Singleton(regExp) => str.matches(regExp)
      case ~!(inner) => !matches(inner, str)
      case And(l, r) => matches(l, str) && matches(r, str)
      case Or(l, r) => matches(l, str) || matches(r, str)
    }
}

sealed trait RegExpAlgebra {
  import RegExpAlgebra._
  def &&(r: RegExpAlgebra) = And(this, r)
  def ||(r: RegExpAlgebra) = Or(this, r)

  override def toString: String = {
    def helper(algebra: RegExpAlgebra): String = {
      algebra match {
        case Singleton(regExp) => s""""$regExp".rEA"""
        case ~!(inner) => s"~!(${helper(inner)})"
        case And(l, r) => s"(${helper(l)} && ${helper(r)})"
        case Or(l, r) => s"(${helper(l)} || ${helper(r)})"
      }
    }

    def stripBrackets(str: String) =
      if(str.startsWith("(") && str.endsWith(")")) str.substring(1, str.length-1) else str

    stripBrackets(helper(this))
  }
}

RegExpAlgebraExamples.scala

package core.misc

/**
 * Created by mishael on 12/16/14.
 *
 */

object RegExpAlgebraExamples extends App {
  import core.misc.RegExpAlgebra._

  val strings = List(
    "men are all equal",
    "Dogs are loyal",
    "Japaneses are loyal"
  )

  val algebra = ".*loyal.*".rEA && ~!(".*Dogs.*".rEA)

  println(s"regular expression algebra is $algebra")

  strings.foreach{str =>
    println(
      s"""The string:
       |$str
       |Matches the algebra: ${matches(algebra, str)}
     """.stripMargin)
  }

  println("Done !!!")
}