An expression parser

We will look at an instructive example of how recursion and immutability go hand in hand. We will look at an infix expression parser.


An infix notation is where the operator comes in between two operands, for example, 3+4+5-6 is the infix notation.

We will look at the iterative Java version and then at the recursive Scala version. We support only operators + and * and also provide bracketed sub-expressions.

Evaluating (1+2)*3*(2+4) expression should give us the output as 54 and evaluating (1+2)*3+4 expression should give us the output as 13. The grammar for our expression parser looks as shown in the following code. Note how each sub-expression is an expression composed of other sub-expressions, terms, and factors. In short, ...

Get Scala Functional Programming Patterns now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.