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