Writing an equation parser in Scala
Tags: scala, parser, tokenizer
Published: 2022-04-27 09:19:48

I recently started diving into Scala and as a first learning project, I decided to build a functional mathematical expression tokenizer, parser and evaluator. In this post I will walk through the implementation and some of the core algorithms. Feel free to reach out with any questions!

You can find the final project [here](https://github.com/leo-pfeiffer/equation-parser).

## Overview

The goal of the project is to be able to pass a mathematical expression (e.g. `1 + 2 * 3 - 4`) to the program and get the value of the expression back (i.e. `3`).

Internally, this involves three steps. First, the raw string expression needs to be tokenized into a well-defined format as preparation for further processing. Second, a parser reads the tokens and parses them into a mathematical expression following the usual precedence rules. Lastly, the expression is evaluated by combining its components.

## Allowed operations

Let's quickly define what the final program should be able to do.

Numbers should be specified as integers (e.g. `42`) or decimals (e.g. `1.23`) and should evaluated as doubles.

Negative numbers should be evaluated correctly, but should always be wrapped in parentheses (i.e. write `(-42)+2` instead of `-42+2`).

The following operations should be allowed:

```
+    Addition
-    Difference
*    Multiplication
/    Division
^    Power
```

Left `(` and right `)` parentheses should also be allowed and the resulting precedence should be taken into account.

## Defining Expressions

We start by defining the expressions. In total, we will need to define the expressions `Number`, `Difference`, `Product`, `Division`, and `Power`.

In fact, each component of an expression is itself an expression. For example, `1 + 2` consists of two expressions of type `Number`, namely `Number(1)` and `Number(2)`, as well as a `Sum` operator.

Moreover, every expression is either of type `Number` (which wraps a double) or `Operator` (which has a left and a right expression). Continuing with the example from above, the `Sum` operator has the left expression `Number(1)` and the right expression `Number(2)`.

Lastly, we differentiate between regular operators and `Commutative` operators. A commutative operator does not differentiate between left and right, as the order doesn't matter. For example, `x+y` always equals `y+x` (commutative) but `x-y` does not necessarily equal `y-x`.

With that in mind, we can define the `Expression` trait and the `Operator` trait, which extends `Expression`.

```scala
/** Represents arithmetic expression. */
trait Expression

/** Arithmetic operator */
trait Operator extends Expression {
    val left: Expression
    val right: Expression
}
```

As laid out, a `Commutative` expression is simply an `Operator` that doesn't differentiate between left and right. We can achieve this behavior by extending `Operator` and overriding the `equals` def and `hashCode` def accordingly.

```scala
/** 
 * Represents operators whose left and right side are commutative,
 * i.e. the order of the LHS and RHS expression does not matter.
 * */
trait Commutative extends Operator {
    def canEqual(a: Any) = a.isInstanceOf[Commutative]

    override def equals(that: Any): Boolean =
        that match {
            case that: Commutative => {
                that.canEqual(this) &&
                ((this.left == that.left && this.right == that.right) ||
                    (this.left == that.right && this.right == that.left))
            }
            case _ => false
        }

    override def hashCode: Int = {
        val prime = 31
        prime + left.hashCode * right.hashCode
    }
}
```

The actual expression types can now be implemented as case classes that extend any of the `Expression` traits.

```scala
case class Number(n: Double) extends Expression {
    def value = n
}

case class Sum(left: Expression, right: Expression) extends Commutative
case class Difference(left: Expression, right: Expression) extends Operator
case class Product(left: Expression, right: Expression) extends Commutative
case class Division(left: Expression, right: Expression) extends Operator
case class Power(left: Expression, right: Expression) extends Operator
```

Evaluating these expressions is now almost trivial. Any operator can be evaluated by simply applying the underlying mathematical operation to the left and right sides (which in turn need to be evaluated). For `Number` expressions, we simply return the underlying value. Scala's pattern matching comes in handy here.

```scala
/**
 * Evaluate an expression.
 * @param expression: expression to evaluate
 * @return value of the expression
 * */
def evaluate(expression: Expression): Double = expression match
    case Number(n) => n
    case Sum(left, right) => evaluate(left) + evaluate(right)
    case Difference(left, right) => evaluate(left) - evaluate(right)
    case Product(left, right) => evaluate(left) * evaluate(right)
    case Division(left, right) => evaluate(left) / evaluate(right)
    case Power(left, right) => scala.math.pow(evaluate(left), evaluate(right))
```

That's the expression implementation done. If we wanted to represent the example `1 + 2 * 3 - 4` from earlier using our implementation, it would give us 

`Difference(Sum(Number(1), Product(Number(2), Number(3))), Number(4))`

We can also express these expressions as a syntax tree. For example, parsing the equation `3+4*2/(1-5)^2^3` creates the following syntax tree.

![Syntax Tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3jw1u2dm2w1cplsov92e.png)

The final version of `Expression.scala` can be found [here](https://github.com/leo-pfeiffer/equation-parser/blob/main/src/main/scala/Expression.scala).

## Tokenizer

Next, we will take care of tokenizing the raw string expression. 

The tokenizer splits the raw expression into its components and encodes each component as a token. The token closely follow the `Expression` classes defined earlier, however, we will also have to handle parentheses here.

We start by defining a simple abstract class `Token` and an abstract subclass `OperatorToken`, which represents operators. Each operator has a `precedence` (lower precedence operators are evaluated first).

```scala
/** Token of an expression */
abstract class Token()

/** Token representing an operator */
abstract class OperatorToken() extends Token {
    /** Precedence value of the operator */
    def precedence: Int
}
```

Next, we have to handle how the different operators associate. A left associative operator evaluates from left to right, while a right associative takes the opposite direction.

This is implemented using the following three traits.

```scala
trait Associates

/** Associates left */
trait Left extends Associates

/** Associates right */
trait Right extends Associates
```

This gives us all the components to define our actual tokens. `NumberToken`, `LeftParensToken`, and `RightParensToken` extend `Token` directly. All others are `OperatorToken` subclasses an also extend an `Associates` trait. Only the power token (`^`) associates right, all others associate left.

```scala
/** Token representing sum */
case class SumToken() extends OperatorToken, Left {
    def precedence = 2
}

/** Token representing difference */
case class DifferenceToken() extends OperatorToken, Left {
    def precedence = 2
}

/** Token representing product */
case class ProductToken() extends OperatorToken, Left {
    def precedence = 3
}

/** Token representing division */
case class DivisionToken() extends OperatorToken, Left {
    def precedence = 3
}

/** Token representing power */
case class PowerToken() extends OperatorToken, Right {
    def precedence = 4
}

/** Token representing number */
case class NumberToken(n: Double) extends Token

/** Token representing left parenthesis */
case class LeftParensToken() extends Token

/** Token representing right parenthesis */
case class RightParensToken() extends Token
```

What remains is the function to actually convert a raw string expression into a list of tokens.

The function will have the following signature (we will fill in the body step by step).

```scala
/** 
 * Tokenize string expression.
 * 
 * Tokenize a string representation of an arithmentic expression. 
 * 
 * @param rawExpression: String representation of expression.
 * @return List of tokens of the expression.
 * */
def tokenize(rawExpression: String): List[Token] = ???
```

In the method body, we will have to add the following.

### Splitting the raw string expression

```scala
    val splitted = rawExpression
        .filterNot(_.isWhitespace)
        .split("(?=[)(+/*-])|(?<=[)(+/*-])|(?=[\\^])|(?<=[\\^])")
        .map(_.trim)
```

This takes the raw string, splits it into its parts using a regular expression, and removes any whitespace.

### Tokenizing string components

The val `splitted` now contains a list of strings that can be converted into tokens. For that, we define the `tokenizeOne` function and map it to each element of `splitted`.

```scala
// Regex representing a double.
val numPattern = "(\\-?\\d*\\.?\\d+)".r

/**
 * Tokenize a single string.
 * 
 * @param x: String to tokenize
 * @returns Corresponding token
 * */
def tokenizeOne(x: String) = x match {
    case "+" => SumToken()
    case "-" => DifferenceToken()
    case "*" => ProductToken()
    case "/" => DivisionToken()
    case "^" => PowerToken()
    case "(" => LeftParensToken()
    case ")" => RightParensToken()
    case numPattern(c: String) => NumberToken(c.toDouble)
    case _ => throw RuntimeException(s""""$x is not legal""")
}

// tokenize each element
val tokenized = splitted.map(tokenizeOne).toList
```

### Handling negative numbers

At this stage, the tokenizer can handle all (valid) input and convert it into a list of tokens. However, we would run into problems later, if we parsed negative numbers (e.g. `1+(-1)`) since the `-` is converted into a `DifferenceToken`, yet there is not `NumberToken` to its left.

To handle this, we will walk through the list of tokens, and if we find a `(-` sequence in the list, we insert a `NumberToken(0)` between the `(` and the `-`, producing a valid negative number.

The algorithm could be implemented more concisely with a loop, however, I wanted to find a functional implementation. Thus, I came up with the following:

```scala
/**
 * Handle negative numbers.
 * 
 * Negative numbers are prefixed with a zero
 * e.g. (-1) -> (0-1)
 * to maintian both a left and right expression of the Difference operator.
 * 
 * @param tokens: list of tokens to handle
 * @returns tokens with inserted zeros
 * */
def handleNegative(tokens: List[Token]): List[Token] = 
    
    /**
     * Insert prefix zero.
     * 
     * If the token list starts with "(, -" insert a zero.
     * 
     * @param tokens: list of params to check
     * @return token list with inserted zero
     * */
    def insert(tokens: List[Token]): List[Token] = tokens match {
        case a :: b :: rest => {
            a match {
                case _a: LeftParensToken => {
                    b match {
                        case _b: DifferenceToken => _a :: NumberToken(0) :: Nil
                        case _ => _a :: Nil
                    }
                }
                case _ => a :: Nil
            }
        }
        case a :: Nil => a :: Nil
        case _ => Nil
    }

    /** Recursively insert zeros where necessary */ 
    def recur(tokens: List[Token]): List[Token] =
        if tokens.isEmpty then Nil
        else if tokens.tail.isEmpty then tokens
        else insert(tokens) ++ recur(tokens.tail)

    recur(tokens)
```

The algorithm recursively explores the list. If the list starts with the defined pattern of `(-`, it returns `(0-` plus the tail of the list. Else, it simply returns the tail of the list.

In the body of `tokenize` we now simply call

```scala
// handle negative numbers
handleNegative(tokenized)
```

as the last line.

The final `Tokenizer.scala` file can be found [here](https://github.com/leo-pfeiffer/equation-parser/blob/main/src/main/scala/Tokenizer.scala)

## Parser

In this last step, we can finally write the actual parser, that converts the token list into an expression that can be evaluated.

The parser will work in two steps.

1. Convert the token list from infix to postfix notation
2. Parse the postfix token list into an expression

### Converting infix to postfix

When we input the expression as a raw string, we use what is called _infix notation_. While this makes sense for human readability, the parsing algorithm of the implementation requires _postfix notation_.

To given an example, the infix expression `(5-6) * 7` expressed in postfix notation is `* -5 6 7`.

The algorithm to do this conversion used here is called _Shunting Yard algorithm_. My implementation is based on the pseudo code provided on [Wikipedia](https://en.wikipedia.org/wiki/Shunting_yard_algorithm), but implemented recursively. I won't go into much detail as to how the algorithm works as I think the Wikipedia article does a pretty good job at explaining that.

Let's start by defining the core recursive procedure of the function.

```scala
/**
 * Shunting Yard algorithm.
 * 
 * Converts a list of tokens from infix to postfix notation.
 * https://en.wikipedia.org/wiki/Shunting_yard_algorithm
 * 
 * @param tokens: List of tokens in infix notation
 * @return list of tokens in postfix notation
 * */
def shuntingYard(tokens: List[Token]): List[Token] =

    // todo: we will fill in the helper functions later

    /**
     * Recursive method of shunting yard.
     * 
     * @param stack: Stack of tokens left to place
     * @param postfix: Tokens converted to postfix notation
     * @param tokens: Tokens in infix notation
     * @return tokens in postfix notation
     * */
    @tailrec
    def recur(stack: Stack[Token], postfix: List[Token], tokens: List[Token]): List[Token] = 
        tokens match {
            case Nil => postfix ++ stack
            case t :: rest => {
                t match {
                    case n: NumberToken => recur(stack, postfix :+ n, rest)
                    case o: OperatorToken => {
                        if (stack.isEmpty) then recur(stack.push(o), postfix, rest)
                        else {
                            val updated = operatorUpdate(postfix, stack, o)
                            recur(updated._1, updated._2, rest)
                        }
                    }
                    case l: LeftParensToken => recur(stack.push(l), postfix, rest)
                    case r: RightParensToken => {
                        val updated = rightParensUpdate(postfix, stack)
                        recur(updated._1, updated._2, rest)
                    }
                }
            }
        }

    recur(new Stack[Token], List(), tokens)
```

Essentially, this procedure recursively walks over the token list and depending on the token it encounters, it either places the token on a stack or combines the token with the last token from the step.

Notice that we're still missing some helper functions that were crated to make the core procedure more readable. Insert the following helper functions into `shuntingYard` before the `recur` function.

```scala
/** Helper method to determine if token if left associative. */
def isLeftAssoc(t: Token): Boolean = t match {
    case a: Left => true
    case _ => false
}

/** Helper method to determine if token if right associative. */
def isRightAssoc(t: Token): Boolean = t match {
    case a: Right => true
    case _ => false
}

/** Helper method to determine if token if left parenthesis. */
def isLeftParens(t: Token): Boolean = t match {
    case a: LeftParensToken => true
    case _ => false
}

/** Helper method to update postfix and stack during operator parsing. */
@tailrec
def operatorUpdate(postfix: List[Token], stack: Stack[Token], o: OperatorToken): (Stack[Token], List[Token]) =
    def matchCond(o: OperatorToken, stack: Stack[Token]): Boolean = stack.head match {
        case o2: OperatorToken => {
            (isLeftAssoc(o) && (o.precedence <= o2.precedence)) ||
            (isRightAssoc(o) && (o.precedence < o2.precedence))
        }
        case _ => false
    }
    if (stack.isEmpty || !matchCond(o, stack)) (stack.push(o), postfix)
    else operatorUpdate(postfix :+ stack.pop, stack, o)

/** Helper method to update postfix and stack during right parens parsing. */
@tailrec
def rightParensUpdate(postfix: List[Token], stack: Stack[Token]): (Stack[Token], List[Token]) =
    if (isLeftParens(stack.head)) {stack.pop; (stack, postfix)}
    else rightParensUpdate(postfix :+ stack.pop, stack)
```

The `shuntingYard` function returns a new token list in postfix notation.

### Parsing postfix token list into an expression

Given the postfix token list, the second step of the parser converts it into a full expression.

The algorithm is quite simple. It recursively walks through the token lists. If a number token is encountered, it is placed on a stack. If an operator is encountered, the last two elements from the stack are combined accordingly and the resulting expression is put on the stack. Eventually, the stack only contains one expression, which is the final one.

```scala
/**
 * Parses RPN to expression.
 * 
 * Takes a list of tokens in RPN and parses the expression representation.
 * https://en.wikipedia.org/wiki/Reverse_Polish_notation
 * 
 * @param tokens: List of tokens in postfix notation
 * @return parsed expression
 * */
def parsePostfix(tokens: List[Token]): Expression = 

    /** Helper method to determine if token is operator. */
    def isOperator(t: Token): Boolean = t match {
        case a: OperatorToken => true
        case _ => false
    }

    /**
     * Recursive method of the algorithm.
     * 
     * @param stack: Stack of expressions to parse
     * @param tokens: Tokens to parse.
     * @return parsed expression
     * */
    @tailrec
    def recur(stack: Stack[Expression], tokens: List[Token]): Expression = tokens match {
        case Nil => stack.pop
        case t :: rest => {
            if (isOperator(t)) t match {
                case t: SumToken => stack.push(Sum(stack.pop, stack.pop))
                case t: DifferenceToken => val x = stack.pop; stack.push(Difference(stack.pop, x))
                case t: ProductToken => stack.push(Product(stack.pop, stack.pop))
                case t: DivisionToken => val x = stack.pop; stack.push(Division(stack.pop, x))
                case t: PowerToken => val x = stack.pop; stack.push(Power(stack.pop, x))
                case _ => throw new RuntimeException(s""""$t" is not an operator""")
            }
            else t match {
                case t: NumberToken => stack.push(Number(t.n))
                case _ => throw new RuntimeException(s""""$t" is not valid here""")   
            }
            recur(stack, rest)
        }
    }

    recur(new Stack[Expression], tokens)
```

### Putting it together

With the `shuntingYard` and `parsePostfix` functions in place, we can define the `parse` function, which we can call to actually perform the parsing.

```scala
/**
 * Run the parser.
 * 
 * Converts the tokens to postfix notation and then reverses it to RPN.
 *
 * @param tokens: List of tokens in infix notation
 * @return Parsed expression
 * */
def parse(tokens: List[Token]): Expression =
    val postfix = shuntingYard(tokens)
    parsePostfix(postfix)
```

And that is the parser done. You can find the final version of `Parser.scala` [here](https://github.com/leo-pfeiffer/equation-parser/blob/main/src/main/scala/Parser.scala).

## Main.scala

To make the project runnable, we need a main method in `Main.scala`. This is just a few lines:

```scala
object Main {
    def main(args: Array[String]) = args match
        case Array(x: String) => printResult(getResult(x))
        case Array() => throw new java.lang.IllegalArgumentException("Too few arguments!")
        case _ => throw new java.lang.IllegalArgumentException("Too many arguments!")

    /** Tokenize and parse expression. */
    def getResult(rawExpr: String): Expression = tokenize(rawExpr).parser
    /** Print the result of the evaluation. */
    def printResult(expr: Expression): Unit = println(expr.eval)
}
```

## Testing the parser

Let's try out the parser on some expressions. Fire up your `sbt` server and run some examples.

```
sbt:equation-parser> run "1+2"
3.0
```

```
sbt:equation-parser> run "3 * (1 + 2) ^ 7"
6561.0
```

```
sbt:equation-parser> run "100 / 8 - (2 * 3) + 4 ^ 3"
70.5
```

```
sbt:equation-parser> run "((3 + 2) * (2 + 1)) ^ 2"
225.0
```

```
sbt:equation-parser> run "(-42)^3+(-42)"
-74130.0
```

Seems to work!

(We should probably write some more thorough tests to make sure it _actually_ works, which I did [here](https://github.com/leo-pfeiffer/equation-parser/tree/main/src/test/scala))

## Conclusion

Implementing this Tokenizer/Parser/Evaluator in a functional way in Scala proved to be a very insightful and fun learning project. Maybe it will inspire anyone to build their own parser or improve upon mine. 

Feel free to reach out with any comments or feedback!