# 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.

## 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.