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)")

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


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


    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 ):
            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]
                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})
    source = "12 * ( 34 + 56 )"
    print "{0} = {1}".format(source, expression( tokenize( source ) ) )
    #12 * ( 34 + 56 ) = 1080

Leave a Reply

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

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

Facebook photo

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

Connecting to %s

%d bloggers like this: