#### Overview of this book

Scala Functional Programming Patterns
Credits
Aknowledgement
www.PacktPub.com
Preface
Free Chapter
Grokking the Functional Way
Singletons, Factories, and Builders
Recursion and Chasing your Own Tail
Lazy Sequences – Being Lazy, Being Good
Taming Multiple Inheritance with Traits
Of Visitors and Chains of Responsibilities
Traversals – Mapping/Filtering/Folding/Reducing
Higher Order Functions
Actors and Message Passing
Index

## 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.

### Note

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, the grammar is recursively defined. Here is the grammar:

```Expr: Term | Term + Expr
Term: Factor | Factor * Term
Factor: [0-9][0-9]+ | '(' Expr ')'
```

Here is a diagrammatic representation of the flow:

Figure 3.5: The expression tree

Look at the bracketed...