Expressions V2 – HackerRank Solution

In this post, we will solve Expressions V2 HackerRank Solution. This problem (Expressions V2) is a part of HackerRank Functional Programming series.

Task

Once Kazama had written a basic calculator, he read further about other operators and operator precedence. Now he is writing a new calculator with following details:

• Binary addition: x + y.
• Binary subtraction: x – y
• Multiplication: x x y
• Division: x/y
• Unary operators: +x and –x
• Brackets: ( . . . )

Operator precedence

(Unary operators, Brackets) > (Multiplication, Division) > (Binary addition, Binary subtraction)

Associativity

Now all operators are right associative. That is p – q – r = p – (q – r), or p/q/r = p/(q/r)

Formally it has following grammar:

 Expression ::= Term [+-] Expression
              | Term

 Term       ::= Factor [*/] Term
              | Factor

 Factor     ::= Number
              | [+-] Factor
              | '(' Expression ')'

He needs your help to verify it. He wants you to solve some expressions for him using the above grammar and he will cross check the results. Since you are also lazy, you will write another computer program which will solve the expressions. Since the output value can be too large, you have to tell output modulo 1000000007 (= 10⁹ + 7).

Note:

• 10⁹ + 7 is a prime.
• 1/b = b^-1 = b^p-2 (mod p), where p is prime and b < p

Input Format

Input will contain a valid expression.

Constraints

• Length of expression will not exceed 10⁵.
• 1 <= number <= 10⁹
• There can be 0 or more whitespaces between operators/operands.
• Tests are designed such that there will be no divide by zero case.
• Each factor will be accompanied by at-most one unary operator. That is““-+-4” is an invalid case.

Output Format

Print the result of expression modulo (10⁹ + 7)

Sample Input 0

22 * 79 - 21

Sample Output 0

1717

Sample Input 1

4/-2/2 + 8

Sample Output 1

4

Sample Input 2

55+3-45*33-25

Sample Output 2

999998605

Sample Input 3

4/-2/(2 + 8)

Sample Output 3

999999987

Explanation

Sample Case 0:

22 * 79 – 21 = 1738 – 21 = 1717

Sample Case 1:

4/ – 2/2 + 8 = 4

Sample Case 2:

55 + 3 – 45 * 33 – 25 = 999998605 (mod p), where p = 10⁹ + 7

Sample Case 3:

4/ – 2/(2 + 8) = 99999987 (mod p), where p = 10⁹ + 7

Solution – Expressions V2 – HackerRank Solution

Scala

import java.io.{BufferedReader, IOException, InputStreamReader}
import java.util.StringTokenizer

class FastReader() {
  val br: BufferedReader = new BufferedReader(new InputStreamReader(System.in))
  var st: StringTokenizer = _

  def nextInt: Int = next.toInt

  def nextLong: Long = next.toLong

  def nextDouble: Double = next.toDouble

  def next: String = {
    while (st == null || !st.hasMoreElements)
      try
        st = new StringTokenizer(br.readLine)
      catch {
        case e: IOException =>
          e.printStackTrace()
      }
    st.nextToken
  }

  def nextLine: String = {
    var str = ""
    try
      str = br.readLine
    catch {
      case e: IOException =>
        e.printStackTrace()
    }
    str
  }
}

trait Expression

object Expression {
  val modulo = 1000000007
}

case class Number(value: Int) extends Expression

trait Binary extends Expression {
  def eval(a: Int, b: Int): Int
}

trait Additive extends Binary

trait Multiplicative extends Binary

trait Unary extends Expression {
  def eval(v: Int): Int
}

case object UnaryAddition extends Unary {
  override def eval(v: Int): Int = v
}

case object UnarySubtraction extends Unary {
  override def eval(v: Int): Int = -v
}

case object BinaryAddition extends Additive {
  override def eval(a: Int, b: Int): Int = Math.floorMod(a.toLong + b, Expression.modulo).toInt
}

case object BinarySubtraction extends Additive {
  override def eval(a: Int, b: Int): Int = Math.floorMod(a.toLong - b, Expression.modulo).toInt
}

case object Multiplication extends Multiplicative {
  override def eval(a: Int, b: Int): Int = Math.floorMod(a.toLong * b, Expression.modulo).toInt
}

case object Division extends Multiplicative {
  override def eval(a: Int, b: Int): Int = {
    val bb = BigInt(b).modPow(Expression.modulo - 2, Expression.modulo).toLong
    Math.floorMod(a * bb, Expression.modulo).toInt
  }
}

object Solution {
  def main(args: Array[String]): Unit = {
    val sc = new FastReader

    val s = sc.nextLine
    println(solve(s))
  }

  def solve(s: String): Int = {
    case class State(index: Int = 0, expressions: List[Expression] = Nil, subexpressions: List[List[Expression]] = Nil)

    @scala.annotation.tailrec
    def parseNumber(index: Int, number: Int = 0): (Int, Int) = if (index < s.length) {
      val c = s(index)
      if (c.isDigit) parseNumber(index + 1, 10 * number + c - '0') else (index, number)
    } else (index, number)

    @scala.annotation.tailrec
    def eval(expressions: List[Expression]): Int = expressions match {
      case Number(b) :: Nil => b
      case Number(b) :: (op: Binary) :: Number(a) :: exs => eval(Number(op.eval(a, b)) :: exs)
      case _ => throw new Exception("Wrong expression")
    }

    @scala.annotation.tailrec
    def simplify(expressions: List[Expression]): List[Expression] = expressions match {
      case Number(b) :: (op: Unary) :: exs => simplify(Number(op.eval(b)) :: exs)
      case (nextOp: Additive) :: Number(b) :: (op: Multiplicative) :: Number(a) :: exs =>
        simplify(nextOp :: Number(op.eval(a, b)) :: exs)
      case exs@_ => exs
    }

    @scala.annotation.tailrec
    def inner(state: State): State = {
      def withExpression(expression: Expression): State =
        State(state.index + 1, expression :: state.expressions, state.subexpressions)

      if (state.index < s.length) {
        val c = s(state.index)
        val nextState = c match {
          case '(' => State(state.index + 1, Nil, state.expressions :: state.subexpressions)
          case ')' => State(state.index + 1, Number(eval(state.expressions)) :: state.subexpressions.head, state.subexpressions.tail)
          case '+' => withExpression(state.expressions match {
            case (_: Number) :: _ => BinaryAddition
            case _ => UnaryAddition
          })
          case '-' => withExpression(state.expressions match {
            case (_: Number) :: _ => BinarySubtraction
            case _ => UnarySubtraction
          })
          case '*' => withExpression(Multiplication)
          case '/' => withExpression(Division)

          case d: Char if d.isDigit =>
            val (nextIndex, number) = parseNumber(state.index)
            State(nextIndex, Number(number) :: state.expressions, state.subexpressions)
          case _ => state.copy(index = state.index + 1)
        }

        val nextExpressions = simplify(nextState.expressions)

        inner(nextState.copy(expressions = nextExpressions))
      } else state
    }

    eval(inner(State()).expressions)
  }
}

Note: This problem (Expressions V2) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.