Think of building an expression evaluator like working at a postal sorting center. When a package arrives, you don't just guess what's inside; you look at the label. If it's labeled "Fragile," you handle it with gloves. If it's labeled "Overnight," it goes to the express lane. If it's a "Large Crate," you call in the forklift. The label tells you exactly which set of rules to apply, and once you've handled that package, you might find another smaller package tucked inside that needs its own sorting process.

In Scala, we do the exact same thing with Algebraic Data Types (ADTs) and pattern matching. The "labels" are our case classes, and the "sorting rules" are our match statements. Because mathematical expressions are naturally recursive—an addition operation contains two other expressions, which could themselves be additions or multiplications—pattern matching is the only sane way to handle this without drowning in a sea of if/else blocks.

Mapping Math to Case Classes

To get this working, we first need to define what an "expression" actually is. I prefer using a sealed trait here. By marking it sealed, I'm telling the compiler, "Look, these are the only types of expressions that will ever exist." This is a lifesaver because if I add a new operation later but forget to update my evaluator, the compiler will yell at me for having an incomplete match.

sealed trait Expr
case class Val(value: Int) extends Expr
case class Add(left: Expr, right: Expr) extends Expr
case class Mul(left: Expr, right: Expr) extends Expr

Notice how Add and Mul don't just take integers; they take other Expr objects. This is the "nesting doll" part of the analogy. A Mul expression could contain two Vals, or it could contain an Add expression and a Val.

The Recursive Evaluation Loop

Now we need the logic to actually crunch the numbers. I like to write this as a single function that calls itself. When the evaluator hits a Val, it's reached the "bottom" of the tree and can just return the number. If it hits an Add or Mul, it pauses, evaluates the left side, evaluates the right side, and then performs the math.

def eval(expr: Expr): Int = expr match {
  case Val(n)       => n
  case Add(l, r)    => eval(l) + eval(r)
  case Mul(l, r)    => eval(l) * eval(r)
}

I've seen some developers try to implement this using an object-oriented approach where each class has an evaluate() method. While that works, it scatters the logic across four different classes. By using pattern matching, the entire "business logic" of how math works lives in one place. It's much easier to maintain when you realize you need to add a Subtract or Divide operation later.

Putting it Together in Practice

If we want to represent (3 + 5) * 2, we don't write a string; we build the tree structure. It looks like this in code:

val expression = Mul(Add(Val(3), Val(5)), Val(2))
println(eval(expression)) // Output: 16

The eval function sees the Mul, dives into the Add, grabs the 3 and 5, sums them to 8, and then finally multiplies that by 2. It's an elegant dance that lets the language handle the stack management for you.

📋 Practical Task

Exercise: Extending the Evaluator for Division and Negative Values

Your goal is to take the basic evaluator we just built and make it more robust. In the real world, math isn't just addition and multiplication.

Requirements:

• Modify the Expr trait and its subclasses to include a Div (Division) operation.
• Add a Neg (Negation) operation that takes a single Expr and flips its sign (e.g., Neg(Val(5)) should result in -5).
• Update the eval function to handle these new cases.
• Bonus: Implement a check in the Div case to throw an ArithmeticException if the right-hand expression evaluates to zero, rather than letting the JVM crash with a raw error.

Test your implementation with this expression:
(10 / (2 + 3)) * -2
(Represented as: Mul(Div(Val(10), Add(Val(2), Val(3))), Neg(Val(2))))
Expected result: -4