Evaluation V2.scala

object Solution {
  val cong = 1000000007L

  def main(args: Array[String]) {

      val line   = scala.io.StdIn.readLine
      val tokens = tokenize(line.toIterator.buffered)
      //println(s"Tokens:\n$tokens\n")
      val ast    = parse(tokens)
      //println(s"AST:\n$ast\n")
      val res    = eval(ast)
      //println(s"Result: $res")
      println(res)
  }
  
  def tokenize(chars: BufferedIterator[Char]): List[Token] = {
    import scala.collection.mutable.{Buffer, StringBuilder}

    val intLit: StringBuilder = new StringBuilder()

    def parseLongLitTail: Unit =
      while(chars.hasNext && IsDigit.unapply(chars.head)) {
        intLit += chars.next
    }

    object IsDigit {
      def unapply(input: Char) = input.toString.matches("\\d")
    }

    @scala.annotation.tailrec
    def readChar(acc: List[Token]): List[Token] =
      if (chars.hasNext) {
        val token = chars.next match {
          case ' ' => SKIP
          case '+' => PLUS
          case '-' => MINUS
          case '/' => DIV
          case '*' => MUL
          case '(' => LBR
          case ')' => RBR
          case dig @ IsDigit() =>
            intLit += dig
            parseLongLitTail
            val tok = INTLIT(intLit.mkString.toLong)
            intLit.clear()
            tok
          case elem => BAD(s"Wrong Char: $elem")
        }
        readChar(acc :+ token)
      } else {
        acc :+ EOF
      }

    val res = readChar(Nil)
    res.toList.filterNot(_ == SKIP)
  }

  @scala.annotation.tailrec
  def parse(tokens: List[Token],
      res: Tree = Empty): Tree = {

    def push(lRes: Tree,
        current: Tree): Tree = {
        combine(lRes, current)
    }

    def combine(lhs: Tree, rhs: Tree): Tree = (lhs, rhs) match {
      case (Empty, r)                    => r
      case (PlusOp, r)                   => PlusUna(r)
      case (PlusUna(l), r)               => PlusUna(combine(l, r))
      case (MinOp, r)                    => MinUna(r)
      case (MinUna(l), r)                => MinUna(combine(l, r))
      case (LBrace, r)                   => Brace(Empty, r)
      case (Brace(prev, l), RBrace)      => combine(prev, l)
      case (Brace(prev, l), r)           => Brace(prev, combine(l, r))
      case (l, LBrace)                   => Brace(l, Empty)
      case (DivOp, r)                    => Divi(Empty, r)
      case (l, Divi(Empty, r))           => Divi(l, r)
      case (Divi(l, Empty), r)           => Divi(l, r)
      case (Divi(l, r: Unary), MulOp)    => Divi(l, combine(r, MulOp))
      case (Divi(l, r: Unary), DivOp)    => Divi(l, combine(r, DivOp))
      case (l: Divi, r @ Divi(_, Empty)) => Divi(l.l, combine(l.r, r))
      case (l: Divi, r @ Mult(_, Empty)) => Divi(l.l, combine(l.r, r))
      case (l: Divi, r: Literal)         => Divi(l.l, combine(l.r, r))
      case (MulOp, r)                    => Mult(Empty, r)
      case (l, Mult(Empty, r))           => Mult(l, r)
      case (Mult(l, Empty), r)           => Mult(l, r)
      case (Mult(l, r: Unary), MulOp)    => Mult(l, combine(r, MulOp))
      case (Mult(l, r: Unary), DivOp)    => Mult(l, combine(r, DivOp))
      case (l: Mult, r @ Divi(_, Empty)) => Mult(l.l, combine(l.r, r))
      case (l: Mult, r @ Mult(_, Empty)) => Mult(l.l, combine(l.r, r))
      case (l: Mult, r: Literal)         => Mult(l.l, combine(l.r, r))
      case (PlusBin(l, r), rr)           => PlusBin(l, combine(r, rr))
      case (MinBin(l, r), rr)            => MinBin(l, combine(r, rr))
      case (l, DivOp)                    => Divi(l, Empty)
      case (l, MulOp)                    => Mult(l, Empty)
      case (l, PlusOp)                   => PlusBin(l, Empty)
      case (l, MinOp)                    => MinBin(l, Empty)
      case _ =>
        throw new IllegalArgumentException(s"can't combine $lhs and $rhs")
    }

    tokens match {
      case EOF :: Nil =>
        res

      case INTLIT(v) :: tail =>
        parse(tail, push(res, Literal(v)))

      case PLUS :: tail =>
        parse(tail, push(res, PlusOp))

      case MINUS :: tail =>
        parse(tail, push(res, MinOp))

      case DIV :: tail =>
        parse(tail, push(res, DivOp))

      case MUL :: tail =>
        parse(tail, push(res, MulOp))

      case LBR :: body =>
        parse(body, push(res, LBrace))

      case RBR :: tail =>
        parse(tail, push(res, RBrace))

      case Nil =>
        throw new IllegalStateException("invalid expression")

      case _ =>
        throw new IllegalStateException(s"this unexpected token ${tokens.head}")
    }
  }

  def eval(tree: Tree): Long = tree match {
    case Divi(_, r) if eval(r) == 0 =>
      throw new IllegalStateException("can't divide by 0")

    case Divi(l, r)    => mod(eval(l) * powMod(eval(r), cong - 2))
    case Mult(l, r)    => mod(eval(l) * eval(r))
    case PlusBin(l, r) => mod(eval(l) + eval(r))
    case MinBin(l, r)  => mod(eval(l) - eval(r))
    case MinUna(term)      => mod(- eval(term))
    case PlusUna(term)     => eval(term)
    case Literal(value)    => value 
    case _ =>
      throw new IllegalStateException(s"this does not evaluate: $tree")
  }

  def mod(value: Long): Long = (value + cong) % cong

  @scala.annotation.tailrec
  def powMod(value: Long, pow: Long, acc: Long = 1L): Long = {
    if (pow == 0) acc
    else if (pow % 2 == 0) powMod(mod(value * value), pow / 2L, acc)
    else powMod(mod(value * value), pow / 2L, mod(acc * value))
  }
}

abstract sealed trait Tree
abstract class BinaryOp(l: Tree, r: Tree) extends Tree
abstract sealed trait Unary extends Tree
abstract class UnaryOp(term: Tree) extends Unary
abstract sealed trait Operand extends Tree
case object Empty extends Tree
case object LBrace extends Tree
case object RBrace extends Tree
case class Brace(prev: Tree, body: Tree) extends Tree
case class Divi(l: Tree, r: Tree) extends BinaryOp(l, r)
case class Mult(l: Tree, r: Tree) extends BinaryOp(l, r)
case class MinBin(l: Tree, r: Tree) extends BinaryOp(l, r)
case class PlusBin(l: Tree, r: Tree) extends BinaryOp(l, r)
case class Literal(value: Long) extends Unary
case class MinUna(term: Tree) extends UnaryOp(term)
case class PlusUna(term: Tree) extends UnaryOp(term)
case object PlusOp extends Operand
case object MinOp extends Operand
case object DivOp extends Operand
case object MulOp extends Operand


abstract sealed trait Token
case object LBR extends Token
case object RBR extends Token
case class INTLIT(value: Long) extends Token
case object PLUS extends Token
case object MINUS extends Token
case object DIV extends Token
case object MUL extends Token
case object EOF extends Token
case object SKIP extends Token
case class BAD(value: String) extends Token