• + 0 comments

    scala:

    object Solution {
      private val mod = (1e9 + 7).toLong
      private type ArithmeticOp = (BigInt, BigInt) => BigInt
    
      private abstract class Token(repr: String) {
        override def toString() = repr
      }
      private final case class Number(s: String) extends Token(s) {
        def toBigInt: BigInt = BigInt(s)
      }
      private final case object LeftParen extends Token("(")
      private final case object RightParen extends Token(")")
      private abstract class Operator(repr: String, val eval: ArithmeticOp) extends Token(repr)
      private abstract class MultiplicativeOperator(repr: String, eval: ArithmeticOp) extends Operator(repr, eval)
      private final case object Multiply extends MultiplicativeOperator("*", _ * _)
      private final case object Divide extends MultiplicativeOperator("/", _ * _.modInverse(mod))
      private abstract class UnaryOperator(repr: String, eval: ArithmeticOp) extends Operator(repr, eval) {
        def eval(num: BigInt): BigInt = eval(0, num)
      }
      private final case object Plus extends UnaryOperator("+", _ + _)
      private final case object Minus extends UnaryOperator("-", _ - _)
    
      private class UnknownToken(t: Char) extends RuntimeException(s"unknown token `$t`")
      private class UnexpectedToken(ts: List[Token]) extends RuntimeException(s"unexpected token `${ts.mkString}`")
      private class UnexpectedEndOfExpression extends RuntimeException("unexpected end of expression")
    
      private def tokenize(expression: String): List[Token] = {
        expression
          .replace(" ", "")
          .foldLeft(List.empty[Token]) {
            case (acc, '+') => Plus :: acc
            case (acc, '-') => Minus :: acc
            case (acc, '*') => Multiply :: acc
            case (acc, '/') => Divide :: acc
            case (acc, '(') => LeftParen :: acc
            case (acc, ')') => RightParen :: acc
            case (acc, c) if c.isDigit || '.' == c =>
              acc match {
                case (Number(s) :: tail) =>
                  Number(s + c) :: tail
                case _ =>
                  Number(c.toString) :: acc
              }
            case (acc, token) => throw new UnknownToken(token)
          }
          .reverse
      }
    
      private def dropRightParen(tokens: List[Token]): List[Token] = {
        tokens match {
          case RightParen :: tail => tail
          case _                  => throw new UnexpectedEndOfExpression
        }
      }
      // Expression ::= Term [+-] Expression
      //              | Term
      private def evaluateExpression(tokens: List[Token]): (BigInt, List[Token]) = {
        evaluateTerm(tokens) match {
          case (term, (op: UnaryOperator) :: tail) =>
            val (expression, remaining) = evaluateExpression(tail)
            op.eval(term, expression) -> remaining
          case (term, remaining) =>
            term -> remaining
        }
      }
    
      // Term ::= Factor [*/] Term
      //        | Factor
      private def evaluateTerm(tokens: List[Token]): (BigInt, List[Token]) = {
        evaluateFactor(tokens) match {
          case (factor, (op: MultiplicativeOperator) :: tail) =>
            val (term, remaining) = evaluateTerm(tail)
            op.eval(factor, term) -> remaining
          case (factor, remaining) =>
            factor -> remaining
        }
      }
    
      // Factor ::= Number
      //          | [+-] Factor
      //          | '(' Expression ')'
      private def evaluateFactor(tokens: List[Token]): (BigInt, List[Token]) = {
        tokens match {
          case (number: Number) :: remaining =>
            number.toBigInt -> remaining
          case (op: UnaryOperator) :: tail =>
            val (factor, remaining) = evaluateFactor(tail)
            op.eval(factor) -> remaining
          case LeftParen :: tail =>
            val (expression, remaining) = evaluateExpression(tail)
            expression -> dropRightParen(remaining)
          case _ =>
            throw new UnexpectedToken(tokens)
        }
      }
    
      def main(args: Array[String]): Unit = {
        val in = Iterator
          .continually(io.StdIn.readLine())
          .takeWhile(null != _)
          .map(_.trim)
        val expression = in.next()
        val tokens = tokenize(expression)
        val (outcome, remaining) = evaluateExpression(tokens)
        if (remaining.nonEmpty)
          throw new UnexpectedToken(remaining)
        println(outcome.mod(mod))
      }
    }