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

About these ads

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

    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 (/= ' ')
    
  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[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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 635 other followers

%d bloggers like this: