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