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
Task
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 as5*(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
, not5x^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 { val operationGroups = Seq(Seq(Exponentiation), Seq(UnaryAddition, UnarySubtraction), Seq(Multiplication, Division), Seq(Addition, Subtraction)) } 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) val highestPower = sortedData.head._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 } trait Additive extends Operation { 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 case object Addition extends Additive { 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) val (ap, av) = a.data.head 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 _ => UnaryAddition }) 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.