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.

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:Â xy
• 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Â pqr = p – (qr), 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 (= 109 + 7).

Note:

• 109 + 7Â is a prime.
• 1/b = b-1 = bp-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Â 105.
• 1 <= number <= 109
• 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Â (109 + 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 = 109 + 7

Sample Case 3:

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

Solution – Expressions V2 – HackerRank Solution

Scala

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

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
catch {
case e: IOException =>
e.printStackTrace()
}
st.nextToken
}

def nextLine: String = {
var str = ""
try
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 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
}

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 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 '-' => 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.