## Expression Evaluation

### April 16, 2010

The very first exercise at Programming Praxis evaluated expressions given in reverse-polish notation. In today’s exercise, we write a function to evaluate expressions given as strings in the normal infix notation; for instance, given the string “12 * (34 + 56)”, the function returns the number 1080. We do this by writing a parser for the following grammar:

expr |
→ | term |

expr + term |
||

expr – term |
||

term |
→ | fact |

term * fact |
||

term / fact |
||

fact |
→ | numb |

( expr ) |

The grammar specifies the syntax of the language; it is up to the program to provide the semantics. Note that the grammar handles the precedences and associativities of the operators. For example, since *expressions* are made up from *terms*, multiplication and division are processed before addition and subtraction.

The normal algorithm used to parse expressions is called *recursive-descent parsing* because a series of mutually-recursive functions, one per grammar element, call each other, starting from the top-level grammar element (in our case, *expr*) and descending until the beginning of the string being parsed can be identified, whereupon the recursion goes back up the chain of mutually-recursive functions until the next part of the string can be parsed, and so on, up and down the chain until the end of the string is reached, all the time accumulating the value of the expression.

Your task is to write a function that evaluates expressions according to the grammar given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

[…] Praxis – Expression Evaluation By Remco Niemeijer In today’s Programming Praxis exercise our task to write a parser for simple mathematical expressions. […]

My Haskell solution (see http://bonsaicode.wordpress.com/2010/04/16/programming-praxis-expression-evaluation/ for a version with comments):

Python