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

### 3 Responses to “Expression Evaluation”

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

2. Remco Niemeijer said

```import Control.Applicative
import Text.Parsec hiding ((<|>))

expr = chainl1 term ((+) <\$ char '+' <|> (-) <\$ char '-')

term = chainl1 fact ((*) <\$ char '*' <|> div <\$ char '/')

fact = read <\$> many1 digit <|> char '(' *> expr <* char ')'

eval :: String -> Int
eval = either (error . show) id . parse expr "" . filter (/= ' ')
```
3. Mike said

Python

```from operator import add, div, mul, sub
import re

#regex function that splits input into a list of tokens
tokenize = re.compile(r"\d+|[-*/+()]").findall

def factor( source ):
try:
if source.isdigit():
value = int( source.pop(0) )

elif source == "(":
del source
value = expression( source )
if source != ')':
raise SyntaxError("Expected ')', got '%s'" % source)
del source

else:
raise SyntaxError("Number or '(' expected, got '%s'" % source)

return value

except IndexError:
raise SyntaxError("Unexpected end of input.")

def binoplist(arg,opmap):
'''returns a function to evaluate a list of 'args' separated by
binary operators.

arg   : function to parse the arguments to the operator
opmap : dictionary operators (e.g., '+','/') to functions

example: binoplist( term, {'+':add, '-':sub} )  returns a function
to evaluate a list of "term"s separated by '+' or '-'
'''

def op( src ):
val = arg( src )
while src and src in opmap.keys():
val = opmap[src.pop(0)](val,arg(src))
return val
return op

term = binoplist(factor, {'*':mul,'/':div})