Displaying nested arithmetic expressions as a string using Scala pattern matching

Question

I am learning the concepts of pattern matching in Scala. Following is an exercise for the same. The task is to define a show function that outputs an expression as a String. Following are the definitions involved:

object Test {
  trait Expr
  case class Number(n: Int) extends Expr
  case class Sum(e1: Expr, e2: Expr) extends Expr
  case class Prod(e1: Expr, e2: Expr) extends Expr
  case class Var(name: String) extends Expr

  def nestOperations(e1: Expr, e2: Expr): String = {
    val l = e1 match {
      case Number(n) => n.toString
      case Prod(x, y) => nestOperations(x, y)
      case Var(s) => s
      case Sum(x, y) => "(" + show(x) + " + " + show(y) + ")"
    }
    val r = e2 match {
      case Number(n) => n.toString
      case Prod(x, y) => nestOperations(x, y)
      case Var(s) => s
      case Sum(x, y) => "(" + show(x) + " + " + show(y) + ")"
    }
    l + " * " + r
  }

  def show(e: Expr): String = e match {
    case Number(n) => n.toString
    case Sum(e1, e2) => show(e1) + " + " + show(e2)`
    case Prod(e1, e2) => nestOperations(e1, e2)
    case Var(s) => s
  }
  show(Sum(Number(1), Number(2)))
  show(Sum(Prod(Number(2), Var("x")), Var("y")))
  show(Prod(Sum(Number(2), Var("x")), Var("y")))
}

The expectation is that:
show(Sum(Number(1), Number(2))) outputs 1 + 2
show(Sum(Prod(Number(2), Var("x")), Var("y"))) outputs 2 * x + y
show(Prod(Sum(Number(2), Var("x")), Var("y"))) outputs (2 + x) * y

The program achieves all of the above. I want to know if the nestOperations method can be simplified? Looks like a lot of repetitive code in there.

Answer 1

You're right. That repeated code in nestOperations() can be eliminated.

def nestOperations(es: Expr*): String =
  es.map {
    case Number(n) => n.toString
    case Prod(x, y) => nestOperations(x, y)
    case Var(s) => s
    case Sum(x, y) => "(" + show(x) + " + " + show(y) + ")"
  }.mkString(" * ")

But why stop there? You can pull much the same stunt with show() and eliminate nestOperations() altogether.

def show(es: Expr*): String = es.map{
  case Number(n) => n.toString
  case Sum(e1, e2) => if (es.length > 1) "(" + show(e1) + " + " + show(e2) + ")"
                      else show(e1) + " + " + show(e2)
  case Prod(e1, e2) => show(e1, e2)
  case Var(s) => s
}.mkString(" * ")

Answer 2

The only difference is the sumExpression. So you can move the matching to a shared function and pass in the sumExpression.

def render(e: Expr)(sum: (Expr, Expr) => String): String = e match {
  case Number(n) => n.toString
  case Prod(x, y) => nestOperations(x, y)
  case Var(s) => s
  case Sum(x, y) => sum(x, y)
}

def nestOperations(e1: Expr, e2: Expr): String = {
  def inner(e: Expr) = render(e)((x, y) => "(" + show(x) + " + " + show(y) + ")")
  inner(e1) + " * " + inner(e2)
}

def show(e: Expr): String = render(e)((x, y) => show(x) + " + " + show(y))

The result is as expected:

1 + 2
2 * x + y
(2 + x) * y

This can be further simplified if you allow all sum and prod expression to have brackets:

def show(exp: Expr): String = exp match {
  case Number(x) => x.toString
  case Var(x) => x
  case Sum(e0, e1) => "(" + show(e0) + " + " + show(e1) + ")"
  case Prod(e0, e1) => "(" + show(e0) + " * " + show(e1) + ")"
}

The result here looks like:

(1 + 2)
((2 * x) + y)
((2 + x) * y)

Answer 3

Removing Duplication

The duplicated matchers can be extracted easily here:

private def parseExpression(e: Expr): String = {
  e match {
    case Number(n) => n.toString
    case Prod(x, y) => nestOperations(x, y)
    case Var(s) => s
    case Sum(x, y) => "(" + show(x) + " + " + show(y) + ")"
  }
}

def nestOperations(e1: Expr, e2: Expr): String = {
  parseExpression(e1) + " * " + parseExpression(e2)
}

BUT!

Indeed, there is no need to keep the nestOperations function. The calls between it and show introduce too much of complexity.

The problem here are the parenthesis for Sum and it can be solved by making a distinction between the root level of the expression (where they are not necessary) and all levels below it (where they are to insert). So an ordinary recursion and an additional boolean parameter to check for the root level will do the job:

private def exprToString(e: Expr, 
                         isRoot: Boolean = false): String = e match {
  case Number(n) => n.toString
  case Sum(e1, e2) => {
    val converted = exprToString(e1) + " + " + exprToString(e2)
    if (isRoot) converted
    else s"($converted)"
  }
  case Prod(e1, e2) => exprToString(e1) + " * " + exprToString(e2)
  case Var(s) => s
}

def show(e: Expr): String = exprToString(e, true)

Answer 4

A method to produce a String representation of something… that method is conventionally toString.

If you start adding more types of expressions, your solution won't scale well. A giant match statement is considered a code smell. The typical remedy is to apply the "Replace Conditional with Polymorphism" refactoring. The problem is that your case classes are underdeveloped. It would be better to make a system to handle the idea of precedence.

trait Expr {
  def precedence: Int
}

private def parenthesizeIf(paren:Boolean): (Expr => String) = {
  paren match {
    case true  => expr => "(" + expr + ")"
    case false => expr => expr.toString
  }
}

case class Number(n:Int) extends Expr {
  def precedence = 0
  override def toString: String = n.toString
}

case class Sum(e1:Expr, e2:Expr) extends Expr {
  def precedence = 6
  override def toString: String = {
    parenthesizeIf(e1.precedence > precedence)(e1) +
    " + " +
    parenthesizeIf(e2.precedence > precedence)(e2)
  }
}

case class Prod(e1:Expr, e2:Expr) extends Expr {
  def precedence = 5
  override def toString: String = {
    parenthesizeIf(e1.precedence > precedence)(e1) +
    " * " +
    parenthesizeIf(e2.precedence > precedence)(e2)
  }
}

case class Var(name:String) extends Expr {
  def precedence = 0
  override def toString: String = name
}

With that, you can do

println(Sum(Number(1), Number(2)))
println(Sum(Prod(Number(2), Var("x")), Var("y")))
println(Prod(Sum(Number(2), Var("x")), Var("y")))

Note that there is a lot of similarity between the toString implementations of Sum and Product, so you could go further and make them subclasses of InfixOperation.