import scala.annotation.tailrec
import scala.collection.mutable.ListBuffer

object Main {

  // _.+
  // syntax(x)(y) = result
  type OperationSyntax = Int => Int => Int

  sealed trait Calculation {
    val calculations: Seq[Calculation]

    protected val functor: OperationSyntax

    def calclate(after: Calculation): Calculation = Number(after.functor(value)(after.value))

    def value: Int = {
      val xxx = calculations.reduce[Calculation](_ calclate _).value
      xxx
    }

    def blocking(after: Calculation): Calculation
  }

  case class Number(_value: Int) extends Calculation {
    override def value: Int = _value

    val calculations: Seq[Calculation] = Nil

    val functor: OperationSyntax = x => _ => x

    def blocking(after: Calculation): Calculation = CalculationBlock(this, after)
  }

  case class Plus(calculations: Calculation*) extends Calculation {
    val functor: OperationSyntax = _.+

    def blocking(after: Calculation): Calculation = Plus(calculations.:+(after): _*)
  }

  case class Minus(calculations: Calculation*) extends Calculation {
    val functor: OperationSyntax = _.-

    def blocking(after: Calculation): Calculation = Minus(calculations.:+(after): _*)
  }

  case class Multiply(calculations: Calculation*) extends Calculation {
    val functor: OperationSyntax = _.*

    def blocking(after: Calculation): Calculation = Multiply(calculations.:+(after): _*)
  }

  case class Devide(calculations: Calculation*) extends Calculation {
    val functor: OperationSyntax = _./

    def blocking(after: Calculation): Calculation = Devide(calculations.:+(after): _*)
  }

  case class CalculationBlock(calculations: Calculation*) extends Calculation {
    val functor: OperationSyntax = x => _ => x

    def blocking(after: Calculation): Calculation = CalculationBlock(this, after)
  }

  def main(args: Array[String]): Unit = {

    val limit: Int = io.StdIn.readLine().toInt
    val buffer: ListBuffer[String] = ListBuffer.empty
    (1 to limit).map { _ =>
      buffer += io.StdIn.readLine()
    }
    buffer.map(Tokenizer.tokenize).map(_.value).foreach(println)
  }

  val operationLiterals = Vector("+", "-", "*", "/", "(", ")")

  def operationLiteralMatcher(syntax: String): String = "(?<=\\%s)|(?=\\%s)".format(syntax, syntax)

  object Tokenizer {

    trait TypedConstruction[T <: Calculation] {
      val construction: Seq[Calculation] => T
      val joinConstruction: (Seq[Calculation], Calculation) => Seq[Calculation]
    }

    implicit object NumberValueConstruction extends TypedConstruction[Number] {
      val construction: Seq[Calculation] => Number = x => Number.apply(x.reduce[Calculation]((a, b) => a.calclate(b)).value)
      val joinConstruction: (Seq[Calculation], Calculation) => Seq[Calculation] = _ :+ _
    }

    implicit object PlusValueConstruction extends TypedConstruction[Plus] {
      val construction: Seq[Calculation] => Plus = Plus.apply
      val joinConstruction: (Seq[Calculation], Calculation) => Seq[Calculation] = _ :+ Plus(_)
    }

    implicit object MinusValueConstruction extends TypedConstruction[Minus] {
      val construction: Seq[Calculation] => Minus = Minus.apply
      val joinConstruction: (Seq[Calculation], Calculation) => Seq[Calculation] = _ :+ Minus(_)
    }

    implicit object MultiplyValueConstruction extends TypedConstruction[Multiply] {
      val construction: Seq[Calculation] => Multiply = Multiply.apply
      val joinConstruction: (Seq[Calculation], Calculation) => Seq[Calculation] = (e, n) => e.init :+ e.last.blocking(Multiply(n))
    }

    implicit object DevideValueConstruction extends TypedConstruction[Devide] {
      val construction: Seq[Calculation] => Devide = Devide.apply
      val joinConstruction: (Seq[Calculation], Calculation) => Seq[Calculation] = (e, n) => e.init :+ e.last.blocking(Devide(n))
    }

    implicit object BlockValueConstruction extends TypedConstruction[CalculationBlock] {
      val construction: Seq[Calculation] => CalculationBlock = CalculationBlock.apply
      val joinConstruction: (Seq[Calculation], Calculation) => Seq[Calculation] = _ :+ _
    }

    def tokenize(v: String): Calculation = {
      inlineExpansion[Number](
        v.replaceAll("=", "").split(s"(${operationLiterals.map(operationLiteralMatcher).mkString("|")})")
      )._2
    }

    def inlineExpansion[T <: Calculation : TypedConstruction](v: Seq[String],
                                                              buffer: Seq[Calculation] = Nil): (Seq[String], Calculation) = {
      v.headOption match {
        case None => Nil -> CalculationBlock(buffer: _*)
        case Some(head) => head match {
          case x if x.matches("\\d+") => inlineExpansion[Number](v.tail, implicitly[TypedConstruction[T]].joinConstruction(buffer, Number(x.toInt)))
          case "+" => inlineExpansion[Plus](v.tail, buffer)
          case "-" => inlineExpansion[Minus](v.tail, buffer)
          case "*" => inlineExpansion[Multiply](v.tail, buffer)
          case "/" => inlineExpansion[Devide](v.tail, buffer)
          case "(" => block[T](v.tail) match {
            case (tail, r) =>
              inlineExpansion[Number](tail, implicitly[TypedConstruction[T]].joinConstruction(buffer, r))
          }
          case ")" => v.tail -> CalculationBlock(buffer: _*)
        }
      }

    }

    def block[T <: Calculation : TypedConstruction](v: Seq[String]): (Seq[String], Calculation) = {
      inlineExpansion[Number](v) match {
        case (a, b) => a -> implicitly[TypedConstruction[T]].construction(b.calculations)
      }
    }
  }

}



Measured memory_bytes: 47364