## 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 + ExprTerm: Factor | Factor * TermFactor: [0-9][0-9]+ | '(' Expr ')'

Here is a diagrammatic representation of the flow:

Look at the bracketed...