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.
Programming Praxis 
[…] 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):
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 (/= ' ')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[0].isdigit(): value = int( source.pop(0) ) elif source[0] == "(": del source[0] value = expression( source ) if source[0] != ')': raise SyntaxError("Expected ')', got '%s'" % source[0]) del source[0] else: raise SyntaxError("Number or '(' expected, got '%s'" % source[0]) 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 (e.g., add, div). 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[0] in opmap.keys(): val = opmap[src.pop(0)](val,arg(src)) return val return op term = binoplist(factor, {'*':mul,'/':div}) expression = binoplist(term, {'+':add,'-':sub}) #test source = "12 * ( 34 + 56 )" print "{0} = {1}".format(source, expression( tokenize( source ) ) ) #output #12 * ( 34 + 56 ) = 1080