Expression Evaluation

April 16, 2010

All of our functions will follow the convention of passing two values to their caller, the accumulating value of the expression and the portion of the string remaining to be processed, represented as a list of characters.

We begin at the end with a function that gets a number from the input string; our definition of a number is simplistic, recognizing only positive integers:

(define (numb xs)
  (let loop ((n (- (char->integer (car xs)) 48)) (xs (cdr xs)))
    (cond ((null? xs) (values n xs))
          ((member (car xs) (string->list "0123456789"))
            (loop (+ (* 10 n) (- (char->integer (car xs)) 48)) (cdr xs)))
          (else (values n xs)))))

A factor is either a number or a parenthesized expression. These are the third and fourth clauses of the cond. The first and last clauses look for errors in the input string, and the second clause ignores space characters:

(define (fact xs)
  (cond ((null? xs) (error 'fact "missing factor"))
        ((char=? (car xs) #\space) (fact (cdr xs)))
        ((member (car xs) (string->list "0123456789"))
          (let-values (((n rest) (numb xs)))
            (values n rest)))
        ((char=? (car xs) #\()
          (let-values (((n rest) (expr (cdr xs))))
            (if (or (null? rest) (not (char=? (car rest) #\))))
                (error 'fact "missing right parenthesis")
                (values n (cdr rest)))))
        (else (error 'fact "expected number or left parenthesis"))))

Next up is the term function, which handles multiplication and division:

(define (term xs)
  (let-values (((f rest) (fact xs)))
    (let loop ((n f) (xs rest))
      (cond ((null? xs) (values n xs))
            ((char=? (car xs) #\space)
              (loop n (cdr xs)))
            ((char=? (car xs) #\*)
              (let-values (((f rest) (fact (cdr xs))))
                (loop (* n f) rest)))
            ((char=? (car xs) #\/)
              (let-values (((f rest) (fact (cdr xs))))
                (loop (/ n f) rest)))
            (else (values n xs))))))

The last parsing function is expr, which handles addition and subtraction; it’s form is identical to term:

(define (expr xs)
  (let-values (((t rest) (term xs)))
    (let loop ((n t) (xs rest))
      (cond ((null? xs) (values n xs))
            ((char=? (car xs) #\space)
              (loop n (cdr xs)))
            ((char=? (car xs) #\+)
              (let-values (((t rest) (term (cdr xs))))
                (loop (+ n t) rest)))
            ((char=? (car xs) #\-)
              (let-values (((t rest) (term (cdr xs))))
                (loop (- n t) rest)))
            (else (values n xs))))))

Finally, here is evaluate, which converts the input string to a list of characters and checks for proper termination of the input string:

(define (evaluate str)
  (let-values (((x xs) (expr (string->list str))))
    (if (null? xs) x
      (error 'evaluate "extra characters at end"))))

Here’s an example:

> (evaluate "12 * (34 + 56)")
1080

A function this complicated deserves a proper test suite; calling (test-evaluate) should produce no output, on the theory that no news is good news:

(define (test-evaluate)
  (assert (evaluate "6+2") 8)
  (assert (evaluate "6-2") 4)
  (assert (evaluate "6*2") 12)
  (assert (evaluate "6/2") 3)
  (assert (evaluate "6 * 2") 12)
  (assert (evaluate "2+3*4") 14)
  (assert (evaluate "2*3+4") 10)
  (assert (evaluate "2+3+4") 9)
  (assert (evaluate "2-3-4") -5)
  (assert (evaluate "2*3*4") 24)
  (assert (evaluate "(2+3)*4") 20)
  (assert (evaluate "(2*3)+4") 10)
  (assert (evaluate "2+(3*4)") 14)
  (assert (evaluate "2*(3+4)") 14)
)

Assert comes from the Standard Prelude. We also perform the following tests, noting the error messages that result; this can’t be done by assert because error halts execution:

> (evaluate "1+")

Error in fact: missing factor.
Type (debug) to enter the debugger.
> (evaluate "6 - -2")

Error in fact: expected number or left parenthesis.
Type (debug) to enter the debugger.
> (evaluate "(1+2")

Error in fact: missing right parenthesis.
Type (debug) to enter the debugger.
> (evaluate "sqrt(4)")

Error in fact: expected number or left parenthesis.
Type (debug) to enter the debugger.
> (evaluate "1+2hello")

Error in evaluate: extra characters at end.
Type (debug) to enter the debugger.

You can run the program at http://programmingpraxis.codepad.org/tAAtFW6d.

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 575 other followers

%d bloggers like this: