Simplify the Algebraic Expressions – HackerRank Solution

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

Contents

Problem

A simplified algebraic expression is an expression which has been reduced to a simpler, more compact form without changing the expression’s value. To a great extent, this largely involves collecting and combining ‘like’ terms.

For example:

• Â x2 + 2x + 2x2 + 2 + 4x + 6 can be simplified toÂ 3x2 + 6x + 8.
• Â 5x + 2(x – 4) can be simplified toÂ 7x – 8
• Â 5x x (2 + 32) + 51 x (x – 4)/(5 + 6 x 2) reduces toÂ 5x x 11 + 3 x (x – 4), which reduces toÂ 58x – 12

Given an algebraic expression, reduce the expression to a simplified form meeting the following criteria:

• All terms are inÂ descendingÂ order of the power of variableÂ x.
• Coefficients should be concatenated immediately to the left of your variable (e.g.:Â 5 x xÂ should be printed asÂ `5x`).
• There are exactlyÂ 3Â characters between anyÂ 2Â consecutive terms of the expression: a space, followed by aÂ +Â orÂ Â sign, followed by another space.
• In case there is no operator between expressions, assume that it implies multiplication. e.g.Â `(5x+2)(x+2)`Â should be treated asÂ `(5x+2)*(x+2)`,Â `5(x+1)`Â should be treated asÂ `5*(x+1)`.
• The simplified expression must not contain any parentheses.
• 1-coefficients andÂ 1-powers are implied; if the coefficient or power of a certainÂ xÂ term isÂ 1, do not outputÂ 1Â (e.g.:Â 1xÂ orÂ 1 x xÂ simplifies toÂ x, andÂ x1Â simplifies toÂ x).
• Do not print the powers ofÂ xÂ having a coefficient ofÂ 0Â (e.g.: outputÂ `5x^2 - 3`,Â notÂ `5x^2 + 0x - 3`).

Input Format

The first line contains an integer,Â T, denoting the number of test cases.
TheÂ TÂ subsequent lines of test cases each contain an expression that you must reduce.

Constraints

• 1 <= T <= 10
• Each expression will only use a single variable,Â x, and may contain parentheses (`(`,`)`), addition (`+`), subtraction (`-`), multiplication (`*`), division (`/`), and exponentiation (`^`) symbols. The role of exponentation symbols will be limited to representing powers ofÂ xÂ or integers. You will not encounter terms such asÂ (x – 5)2. You may encounter terms like 3^(1+4) and so on.
• There may be one or more spaces between any consecutive terms, operators, or operands (so you must account for and remove these in your code).
• No divisor will contain a term involvingÂ x, and all divisors are integers.
• All coefficients in the final expression are integers (e.g.:Â 5x2, 4x, x). You will not encounter something likeÂ 2.5xÂ orÂ 1.25x2.
• There may be multiple levels of nested parentheses.
• The original expression will not contain more thanÂ 100Â characters (including spaces).
• The expression will not evaluate to a polynomial of an order higher thanÂ 5.
• You will not encounter an integer exceedingÂ 1000Â either while parsing the original expression or in the final coefficients of your simplified expressions.
• Expressions not containing a variable (x) simply require you to calculate the expression’s result.

Output Format

For each test case, print the simplified expression on a new line. Your reduced expression should meet the criteria set forth in theÂ Problem StatementÂ above.

Sample Input

``````6
10x + 2x - (3x + 6)/3
18*(2x+2) - 5
((9x + 81)/3 + 27)/3  - 2x
18x + (12x + 10)*(2x+4)/2 - 5x
(2x+5) * (x*(9x + 81)/3 + 27)/(1+1+1)  - 2x
(2x+5) * (x*(9x^3 + 81)/3 + 27)/(1+1+1)  - 2x  ``````

Sample Output

``````11x - 2
36x + 31
-x + 18
12x^2 + 47x + 20
2x^3 + 23x^2 + 61x + 45
2x^5 + 5x^4 + 18x^2 + 61x + 45 ``````

Explanation

Observe that the original expressions have been expanded and their like terms collected, thus resulting in the printed simplified expressions.

Solution – Simplify the Algebraic Expressions – HackerRank Solution

Scala

```import java.util.Scanner

trait Expression

trait Operand extends Expression {
def toPolynomial: Polynomial
}

case class Number(value: Int) extends Operand {
override def toPolynomial: Polynomial = Polynomial(Map(0 -> value))
}

case object X extends Operand {
override def toPolynomial: Polynomial = Polynomial(Map(1 -> 1))
}

case class Parentheses(expressions: List[Expression]) extends Operand {
override def toPolynomial: Polynomial = {
val res = Parentheses.operationGroups.foldLeft(expressions.reverse)((acc, ops) => {
def simplify(expressions: List[Expression]): List[Expression] = expressions match {
case Nil => Nil
case (op: Unary) :: (a: Operand) :: exs if ops.contains(op) =>
simplify(op.eval(a.toPolynomial) :: exs)
case (a: Operand) :: (op: Operation) :: (b: Operand) :: exs if ops.contains(op) =>
simplify(op.eval(a.toPolynomial, b.toPolynomial) :: exs)
case ex :: exs => ex :: simplify(exs)
}

simplify(acc)
})

res match {
case (p: Operand) :: Nil => p.toPolynomial
case _ => throw new Exception("Wrong expression")
}
}
}

object Parentheses {
}

case class Polynomial(data: Map[Int, Int]) extends Operand {
override def toPolynomial: Polynomial = this

override def toString: String = if (data.isEmpty) "0" else {
val sortedData = data.toSeq.sortBy(-_._1)
sortedData
.map { case (p, v) =>
val isNegative = v < 0
val sign = if (p == highestPower) {
if (isNegative) "-" else ""
}
else {
if (isNegative) " - " else " + "
}

val x = if (p < 2) {
if (p == 1) "x" else ""
} else "x^"

val absValue = math.abs(v)
val strValue = if (absValue == 1 && p != 0) "" else absValue.toString
val power = if (p < 2) "" else p.toString

s"\$sign\$strValue\$x\$power"
}
.mkString("")
}
}

trait Unary extends Expression {
def eval(a: Polynomial): Polynomial
}

case object UnarySubtraction extends Unary {
override def eval(a: Polynomial): Polynomial = Polynomial(a.data.map { case (k, v) => k -> -v })
}

case object UnaryAddition extends Unary {
override def eval(a: Polynomial): Polynomial = a
}

trait Operation extends Expression {
def eval(a: Polynomial, b: Polynomial): Polynomial
}

def eval(a: Polynomial, b: Polynomial, f: (Int, Int) => Int): Polynomial = {
val allKeys = a.data.keys.toSet ++ b.data.keys.toSet

Polynomial(allKeys.map(k => {
val av = a.data.getOrElse(k, 0)
val bv = b.data.getOrElse(k, 0)
k -> f(av, bv)
})
.filter { case (_, v) => v != 0 }
.toMap)
}
}

trait Multiplicative extends Operation

override def eval(a: Polynomial, b: Polynomial): Polynomial = eval(a, b, _ + _)
}

case object Subtraction extends Additive {
override def eval(a: Polynomial, b: Polynomial): Polynomial = eval(a, b, _ - _)
}

case object Multiplication extends Multiplicative {
override def eval(a: Polynomial, b: Polynomial): Polynomial = {
Polynomial(a.data.keys.flatMap(ak => b.data.keys.map(bk => {
(ak + bk) -> a.data(ak) * b.data(bk)
}))
.groupBy { case (k, _) => k }
.map { case (k, list) => k -> list.map(_._2).sum }
.filter { case (_, v) => v != 0 })
}
}

case object Division extends Multiplicative {
override def eval(a: Polynomial, b: Polynomial): Polynomial = {
val bv = b.data.getOrElse(0, 0)

Polynomial(a.data.keys.map(k => {
val av = a.data.getOrElse(k, 0)
k -> av / bv
}).toMap)
}
}

case object Exponentiation extends Operation {
override def eval(a: Polynomial, b: Polynomial): Polynomial = {
if (a.data.isEmpty) {
Polynomial(Map(0 -> 1))
} else {
val bp = b.data.getOrElse(0, 0)
if (ap == 0) Polynomial(Map(0 -> BigInt(av).pow(bp).toInt))
Polynomial(Map(bp -> 1))
}
}
}

object Solution {
def main(args: Array[String]): Unit = {
val sc = new Scanner(System.in)

val t = sc.nextInt
sc.nextLine

(0 until t).foreach(_ => {
val s = sc.nextLine
println(solve(s))
})

sc.close()
}

def solve(s: String): String = {
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 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, Parentheses(state.expressions) :: state.subexpressions.head, state.subexpressions.tail)
case '+' => withExpression(state.expressions match {
case (_: Number) :: _ | (_: Parentheses) :: _ | X :: _ => Addition
})
case '-' => withExpression(state.expressions match {
case (_: Number) :: _ | (_: Parentheses) :: _ | X :: _ => Subtraction
case _ => UnarySubtraction
})
case '*' => withExpression(Multiplication)
case '/' => withExpression(Division)
case '^' => withExpression(Exponentiation)
case 'x' => withExpression(X)

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 = nextState.expressions match {
case (a: Operand) :: (b: Operand) :: exs => a :: Multiplication :: b :: exs
case exs => exs
}

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

Parentheses(inner(State()).expressions).toPolynomial.toString
}
}
```

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