trait Expression {
  def substitute(numbers: Map[Char, Int]): Expression

  def eval: Int
}

trait Operation extends Expression {
  def operator: Char

  def priority: Int

  def rightPriority: Int

  def apply(l: Expression, r: Expression): Operation

  def left: Expression

  def right: Expression

  def variables: List[String] = (left, right) match {
    case (Variable(name), Variable(name2)) =>
      List(name, name2).distinct
    case (Variable(name), o: Operation) =>
      (name :: o.variables).distinct
    case (o: Operation, Variable(name)) =>
      (name :: o.variables).distinct
    case (o1: Operation, o2: Operation) =>
      (o1.variables ::: o2.variables).distinct
    case _ =>
      Nil
  }

  def substitute(numbers: Map[Char, Int]) = apply(left.substitute(numbers), right.substitute(numbers))
}

case class Addition(left: Expression, right: Expression) extends Operation {
  override def operator: Char = '+'

  override def priority: Int = 1

  override def rightPriority: Int = 1

  override def apply(l: Expression, r: Expression): Operation = Addition(l, r)

  override def eval: Int = left.eval + right.eval

  override def toString: String = s"$left $right +"
}

case class Subtraction(left: Expression, right: Expression) extends Operation {
  override def operator: Char = '-'

  override def priority: Int = 1

  override def rightPriority: Int = 2

  override def apply(l: Expression, r: Expression): Operation = Subtraction(l, r)

  override def eval: Int = left.eval - right.eval

  override def toString: String = s"$left $right -"
}

case class Multiplication(left: Expression, right: Expression) extends Operation {
  override def operator: Char = '*'

  override def priority: Int = 2

  override def rightPriority: Int = 3

  override def apply(l: Expression, r: Expression): Operation = Multiplication(l, r)

  override def eval: Int = left.eval * right.eval

  override def toString: String = s"$left $right *"
}

case class Division(left: Expression, right: Expression) extends Operation {
  override def operator: Char = '/'

  override def priority: Int = 2

  override def rightPriority: Int = 4

  override def apply(l: Expression, r: Expression): Operation = Division(l, r)

  override def eval: Int = left.eval / right.eval

  override def toString: String = s"$left $right /"
}

case class Number(value: Int) extends Expression {
  override def substitute(numbers: Map[Char, Int]): Expression = this

  override def eval: Int = value

  override def toString: String = value.toString
}

case class Variable(name: String) extends Expression {
  override def substitute(numbers: Map[Char, Int]): Expression = {
    val subs = Number((name map {
      c =>
        numbers(c).toString.head
    }).toInt)
    subs
  }

  override def eval: Int = 0

  override def toString: String = name
}

case class Equation(left: Expression, right: Expression) {
  def variables: List[String] = (left, right) match {
    case (Variable(name), Variable(name2)) =>
      List(name, name2).distinct
    case (Variable(name), o: Operation) =>
      (name :: o.variables).distinct
    case (o: Operation, Variable(name)) =>
      (name :: o.variables).distinct
    case (o1: Operation, o2: Operation) =>
      (o1.variables ::: o2.variables).distinct
    case _ =>
      Nil
  }

  def valid = {
    left.eval == right.eval
  }

  def substitute(numbers: Map[Char, Int]): Equation = {
    Equation(left.substitute(numbers), right.substitute(numbers))
  }

  private def toInfix(expr: Expression): String = {
    expr match {
      case o: Operation =>
        val l = o.left match {
          case o1: Operation =>
            val str = toInfix(o1)
            if (o1.priority < o.priority) "(" + str + ")" else str
          case Number(v) => v.toString
          case Variable(v) => v
        }
        val r = o.right match {
          case o1: Operation =>
            val str = toInfix(o1)
            if (o1.priority < o.priority) "(" + str + ")" else str
          case Number(v) => v.toString
          case Variable(v) => v
        }
        l + " " + o.operator + " " + r
      case Number(v) => v.toString
      case Variable(v) => v
      case _ => ""
    }
  }

  override def equals(obj: scala.Any): Boolean = {
    obj match {
      case e: Equation =>
        e.left match {
          case o: Operation =>
        }
      case _ => false
    }
  }

  override def toString: String = s"${toInfix(left)} = ${toInfix(right)}"
}