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

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

```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.isdigit():
value = int( source.pop(0) )

elif source == "(":
del source
value = expression( source )
if source != ')':
raise SyntaxError("Expected ')', got '%s'" % source)
del source

else:
raise SyntaxError("Number or '(' expected, got '%s'" % source)

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

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 in opmap.keys():
val = opmap[src.pop(0)](val,arg(src))
return val
return op

term = binoplist(factor, {'*':mul,'/':div})