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

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 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 - 3not 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 {
  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.

Leave a Comment

Your email address will not be published. Required fields are marked *