trait RegExp {

  def nullable: Boolean

  def derive(c: Char): RegExp

}

case object Empty extends RegExp {

  def nullable = false

  def derive(c: Char) = Empty

}

case object Eps extends RegExp {

  def nullable = true

  def derive(c: Char) = Empty

}

case class Str(s: String) extends RegExp {

  def nullable = s.isEmpty

  def derive(c: Char) =

    if (s.isEmpty || s.head != c) Empty

    else Str(s.tail)

}

case class Cat(r: RegExp, s: RegExp) extends RegExp {

  def nullable = r.nullable && s.nullable

  def derive(c: Char) =

    if (r.nullable) Or(Cat(r.derive(c), s), s.derive(c)) 

    else Cat(r.derive(c), s)

}

case class Star(r: RegExp) extends RegExp {

  def nullable = true

  def derive(c: Char) = Cat(r.derive(c), this)

}

case class Or(r: RegExp, s: RegExp) extends RegExp {

  def nullable = r.nullable || s.nullable

  def derive(c: Char) = Or(r.derive(c), s.derive(c))

}

case class And(r: RegExp, s: RegExp) extends RegExp {

  def nullable = r.nullable && s.nullable

  def derive(c: Char) = And(r.derive(c), s.derive(c))

}

case class Not(r: RegExp) extends RegExp {

  def nullable = !r.nullable

  def derive(c: Char) = Not(r.derive(c))

}

object Matcher {

  def matches(r: RegExp, s: String): Boolean = {

    if (s.isEmpty) r.nullable

    else matches(r.derive(s.head), s.tail)

  }

}

object Pimps {

  implicit def string2RegExp(s: String) = Str(s)

  implicit def regExpOps(r: RegExp) = new {

    def | (s: RegExp) = Or(r, s)

    def & (s: RegExp) = And(r, s)

    def % = Star(r)

    def %(n: Int) = rep(r, n)

    def ? = Or(Eps, r)

    def ! = Not(r)

    def ++ (s: RegExp) = Cat(r, s)

    def ~ (s: String) = Matcher.matches(r, s)

  }

  implicit def stringOps(s: String) = new {

    def | (r: RegExp) = Or(s, r)

    def | (r: String) = Or(s, r)

    def & (r: RegExp) = And(s, r)

    def & (r: String) = And(s, r)

    def % = Star(s)

    def % (n: Int) = rep(Str(s), n)

    def ? = Or(Eps, s)

    def ! = Not(s)

    def ++ (r: RegExp) = Cat(s, r)

    def ++ (r: String) = Cat(s, r)

    def ~ (t: String) = Matcher.matches(s, t)

  }

  def rep(r: RegExp, n: Int): RegExp =

    if (n <= 0) Star(r)

    else Cat(r, rep(r, n - 1))

}

object Test {

  import Pimps._

  val digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

  val int = ("+" | "-").? ++ digit.%(1)

  val real = ("+" | "-").? ++ digit.%(1) ++ ("." ++ digit.%(1)).? ++ (("e" | "E") ++ ("+" | "-").? ++ digit.%(1)).?

  def main(args: Array[String]) {

    val ints = List("0", "-4534", "+049", "99")

    val reals = List("0.9", "-12.8", "+91.0", "9e12", "+9.21E-12", "-512E+01")

    val errs = List("", "-", "+", "+-1", "-+2", "2-")

    ints.foreach(s => assert(int ~ s))

    reals.foreach(s => assert(!(int ~ s)))

    errs.foreach(s => assert(!(int ~ s)))

    ints.foreach(s => assert(real ~ s))

    reals.foreach(s => assert(real ~ s))

    errs.foreach(s => assert(!(real ~ s)))

  }

}