You are viewing a single comment's thread. Return to all 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)) } }
Seems like cookies are disabled on this browser, please enable them to open this website
Expressions V2
You are viewing a single comment's thread. Return to all comments →
scala: