Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 37 ยท Projects and Practice

Project: Expression Evaluator in Scala

Build a calculator in Scala 3: tokenizer, recursive-descent parser, an enum AST, an evaluator with Either errors, and tests. A runnable Java version shows the same design.

This project builds a small calculator that understands expressions like 2 + 3 * (4 - 1) and -(5 + 5) / 4. It is a compact tour of the features that make Scala good at language processing: enums as algebraic data types, pattern matching, recursion, and Either for errors. The same structure is used in real compilers, query engines and configuration languages.

The Scala code is read-only here (no Scala compiler on this site), and a Java version (not Scala) at the end runs the same design so you can try inputs.

The pipeline

flowchart LR
    S["'2 + 3 * 4'"] --> T["tokenize"]
    T --> P["parse"]
    P --> E["eval"]
    E --> R["Right(14.0)"]
    T -.->|"bad character"| X["Left(error)"]
    P -.->|"syntax error"| X
    E -.->|"divide by zero"| X

Three stages, each a pure function that returns Either[String, ...], so a failure in any stage becomes the final result without exceptions. The stages are chained with a for-comprehension.

Three stages

Tokenize Characters become tokens.
Parse Tokens become a tree.
Evaluate The tree becomes a number.
1 / 2

The data types

Tokens and the syntax tree are both closed families, so they are enums (Enums and Sealed ADTs):

SCALA
import scala.annotation.tailrec

enum Token:
  case Num(value: Double)
  case Op(symbol: Char)
  case LParen
  case RParen

enum Expr:
  case Num(value: Double)
  case Neg(inner: Expr)
  case Bin(op: Char, left: Expr, right: Expr)

2 + 3 * 4 becomes Bin('+', Num(2), Bin('*', Num(3), Num(4))). The multiplication sits below the addition in the tree, which is how precedence is encoded.

Stage 1: the tokenizer

It walks the characters with a tail-recursive loop (Immutability and Pure Functions) and pattern matches on the head of the list:

SCALA
def tokenize(input: String): Either[String, List[Token]] =
  @tailrec
  def loop(chars: List[Char], acc: List[Token]): Either[String, List[Token]] =
    chars match
      case Nil => Right(acc.reverse)
      case c :: rest if c.isWhitespace => loop(rest, acc)
      case c :: rest if "+-*/".contains(c) => loop(rest, Token.Op(c) :: acc)
      case '(' :: rest => loop(rest, Token.LParen :: acc)
      case ')' :: rest => loop(rest, Token.RParen :: acc)
      case c :: _ if c.isDigit || c == '.' =>
        val (numberChars, rest) = chars.span(ch => ch.isDigit || ch == '.')
        val text = numberChars.mkString
        text.toDoubleOption match
          case Some(n) => loop(rest, Token.Num(n) :: acc)
          case None => Left(s"bad number: $text")
      case c :: _ => Left(s"unexpected character: '$c'")
  loop(input.toList, Nil)

span splits off the longest prefix that satisfies a condition, so "12.5+1" yields the number 12.5 and the rest +1. Tokens are prepended to acc (cheap on a List) and reversed once at the end.

Stage 2: the recursive-descent parser

A grammar describes the language:

TEXT
expr   := term   (('+' | '-') term)*
term   := factor (('*' | '/') factor)*
factor := NUMBER | '-' factor | '(' expr ')'

Each rule becomes one function. A parser takes the remaining tokens and returns the expression it recognized plus the tokens still unused, or an error message:

SCALA
type Parsed = Either[String, (Expr, List[Token])]

def parseExpr(tokens: List[Token]): Parsed =
  parseTerm(tokens).flatMap((left, rest) => exprTail(left, rest))

def exprTail(left: Expr, tokens: List[Token]): Parsed =
  tokens match
    case Token.Op(c @ ('+' | '-')) :: rest =>
      parseTerm(rest).flatMap((right, rest2) => exprTail(Expr.Bin(c, left, right), rest2))
    case _ => Right((left, tokens))

def parseTerm(tokens: List[Token]): Parsed =
  parseFactor(tokens).flatMap((left, rest) => termTail(left, rest))

def termTail(left: Expr, tokens: List[Token]): Parsed =
  tokens match
    case Token.Op(c @ ('*' | '/')) :: rest =>
      parseFactor(rest).flatMap((right, rest2) => termTail(Expr.Bin(c, left, right), rest2))
    case _ => Right((left, tokens))

def parseFactor(tokens: List[Token]): Parsed =
  tokens match
    case Token.Num(v) :: rest => Right((Expr.Num(v), rest))
    case Token.Op('-') :: rest => parseFactor(rest).map((e, r) => (Expr.Neg(e), r))
    case Token.LParen :: rest =>
      parseExpr(rest).flatMap {
        case (e, Token.RParen :: after) => Right((e, after))
        case _ => Left("expected ')'")
      }
    case t :: _ => Left(s"unexpected token: $t")
    case Nil => Left("unexpected end of input")

The Tail functions loop over repeated operators, building the tree left to right, so 10 - 4 - 3 is (10 - 4) - 3 = 3, not 10 - (4 - 3). The mutual recursion between parseFactor and parseExpr is how parentheses restart the whole grammar inside.

The pattern c @ ('+' | '-') matches either character and names it c: an alternative pattern (Pattern Matching Basics) combined with a binder.

Stage 3: the evaluator

Evaluation is a function over the tree with one case per node type, exactly like the eval from the ADT lesson, plus a check for division by zero:

SCALA
def eval(e: Expr): Either[String, Double] =
  e match
    case Expr.Num(v) => Right(v)
    case Expr.Neg(x) => eval(x).map(v => -v)
    case Expr.Bin(op, l, r) =>
      for
        a <- eval(l)
        b <- eval(r)
        result <- applyOp(op, a, b)
      yield result

def applyOp(op: Char, a: Double, b: Double): Either[String, Double] =
  op match
    case '+' => Right(a + b)
    case '-' => Right(a - b)
    case '*' => Right(a * b)
    case '/' => if b == 0 then Left("division by zero") else Right(a / b)
    case other => Left(s"unknown operator: $other")

Putting it together

SCALA
def calculate(input: String): Either[String, Double] =
  for
    tokens <- tokenize(input)
    parsed <- parseExpr(tokens)
    (expr, rest) = parsed
    _ <- if rest.isEmpty then Right(()) else Left(s"unexpected leftover: ${rest.head}")
    value <- eval(expr)
  yield value

@main def repl(): Unit =
  Iterator.continually(scala.io.StdIn.readLine("> "))
    .takeWhile(line => line != null && line != "quit")
    .foreach { line =>
      calculate(line) match
        case Right(v) => println(v)
        case Left(err) => println(s"error: $err")
    }

The leftover check catches input like 1 2 or 3 ), where parsing succeeds for a prefix and tokens remain. Expected results:

Input Result
2 + 3 * 4 Right(14.0)
(2 + 3) * 4 Right(20.0)
10 - 4 - 3 Right(3.0)
-(5 + 5) / 4 Right(-2.5)
1 / 0 Left("division by zero")
2 + Left("unexpected end of input")
2 $ 3 Left("unexpected character: '$'")

Tests

SCALA
class CalculatorSuite extends munit.FunSuite:
  test("precedence") { assertEquals(calculate("2 + 3 * 4"), Right(14.0)) }
  test("parentheses") { assertEquals(calculate("(2 + 3) * 4"), Right(20.0)) }
  test("left associativity") { assertEquals(calculate("10 - 4 - 3"), Right(3.0)) }
  test("unary minus") { assertEquals(calculate("-(5 + 5) / 4"), Right(-2.5)) }
  test("division by zero") { assertEquals(calculate("1 / 0"), Left("division by zero")) }
  test("missing operand") { assert(calculate("2 +").isLeft) }
  test("leftover tokens") { assert(calculate("1 2").isLeft) }

This is the payoff of pure functions and Either: every behavior, including each failure, is a one-line test. See Testing in Scala.

The same design in Java

The Java program below is not Scala; it mirrors the design with a sealed interface and records instead of enums, and an exception in place of Either to keep the code short. Try changing the inputs.

Java Java: tokenizer, parser and evaluator (Java, not Scala)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Extensions to try

  1. Exponent operator ^, right-associative and binding tighter than *: a new rule between term and factor.
  2. Variables and assignment: carry an immutable Map[String, Double] through eval and add Expr.Var(name).
  3. Functions such as sqrt(16) and max(1, 2): a new Expr.Call(name, args) node and a lookup table of functions.
  4. Better errors with positions: store the index in each Token, and report "column 5".
  5. Pretty printer: a function show(e: Expr): String that prints the tree with only the necessary parentheses.
  6. Simplifier: rewrite x * 1, x + 0 and constant subexpressions with pattern matching over the tree.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does 2 + 3 * 4 evaluate to 14 and not 20?

    expr consists of terms. The product 3 * 4 is parsed inside a term, so it becomes a subtree evaluated before the addition.
  2. 2. What does the Tail helper (such as exprTail) accomplish?

    It loops while it sees + or -, folding each new operand into the left subtree, which gives left associativity.
  3. 3. Why is Either[String, ...] a good return type for each stage?

    A Left from any stage short-circuits the rest, with no try/catch.
  4. 4. What does the leftover-token check catch?

    After parseExpr succeeds, any remaining tokens mean the input contains something the grammar does not allow.

Summary

  • A language processor is a pipeline: tokenize, parse into an AST, evaluate.
  • Enums model tokens and tree nodes; pattern matching handles each case, and sealed types let the compiler check completeness.
  • A recursive-descent parser has one function per grammar rule; layering rules encodes operator precedence, and tail loops give left associativity.
  • Either and for-comprehensions make error handling automatic and easy to test.

Next: Scala Practice Problems