## Infix Expression Evaluation

### July 20, 2012

Our expression evaluator consists of four functions: the driver function `calc`

, and three functions `expr`

, `term`

and `factor`

that each recognize a single metastatement of the grammar. The three grammar functions all take a single argument, a list representing the rest of the input expression, and extract and evaluate a portion of the input expression, returning the result of the evaluation and the rest of the input expression after the part it has evaluated.

`(define (calc str)`

(let ((xs (filter (lambda (c) (not (char-whitespace? c)))

(string->list str))))

(let-values (((c xs) (expr xs)))

(if (null? xs) c

(error 'calc (string-append

"extra input at " (list->string xs)))))))

The `calc`

function converts the input string to a list of characters, calls `expr`

to evaluate the expression, and either returns the value of the expression or raises an error if the expression is complete before the end of the input. Here’s `expr`

:

`(define (expr xs)`

(let-values (((y ys) (term xs)))

(let loop ((e y) (ys ys))

(cond ((null? ys)(values e ys))

((char=? (car ys) #\+)

(let-values (((z zs) (term (cdr ys))))

(loop (+ e z) zs)))

((char=? (car ys) #\-)

(let-values (((z zs) (term (cdr ys))))

(loop (- e z) zs)))

(else (values e ys))))))

The `expr`

evaluator extracts a term, then loops as long as it sees a `+`

or `-`

as the next input character. The `term`

evaluator is similar, looping over `*`

and `/`

operators:

`(define (term xs)`

(let-values (((y ys) (factor xs)))

(let loop ((t y) (ys ys))

(cond ((null? ys) (values t ys))

((char=? (car ys) #\*)

(let-values (((z zs) (factor (cdr ys))))

(loop (* t z) zs)))

((char=? (car ys) #\/)

(let-values (((z zs) (factor (cdr ys))))

(loop (/ t z) zs)))

(else (values t ys))))))

The `factor`

function is the most complicated of the four functions, mostly because it has to assemble numbers as well as recognize the metastatement; an alternate program structure might include a function `number`

that recognizes numbers. The other complication of the `factor`

function is error-checking; the function complains if it runs out of input, or if a closing parenthesis is not in the expected place, or if it sees something other than a number or an opening parenthesis when it is expecting one or the other.

`(define (factor xs)`

(define (digit x)

(- (char->integer x) 48))

(cond ((null? xs) (error 'factor "unexpected end of input"))

((char-numeric? (car xs))

(let loop ((n (digit (car xs))) (ys (cdr xs)))

(cond ((null? ys) (values n ys))

((char-numeric? (car ys))

(loop (+ (* n 10) (digit (car ys))) (cdr ys)))

(else (values n ys)))))

((and (pair? (cdr xs)) (char=? (car xs) #\-)

(char-numeric? (cadr xs)))

(let loop ((n (digit (cadr xs))) (ys (cddr xs)))

(cond ((null? ys) (values (- n) ys))

((char-numeric? (car ys))

(loop (+ (* n 10) (digit (car ys))) (cdr ys)))

(else (values (- n) ys)))))

((char=? (car xs) #\()

(let-values (((y ys) (expr (cdr xs))))

(cond ((null? ys) (error 'factor (string-append

"expected ) at " (list->string ys))))

((char=? (car ys) #\))(values y (cdr ys)))

(else (error 'factor (string-append

"unexpected character at " (list->string ys)))))))

(else (error 'factor (string-append

"unexpected character at " (list->string xs))))))

Here’s an example:

`> (calc "123 + 456 * 789")`

359907

Something as complicated as the four tightly-coupled functions demands a test suite, which we show below; the first time this code was run, it produced two errors, but investigation showed that both were in the checking code, not in the expression evaluator:

`(define (test-calc)`

(assert (calc "123") 123)

(assert (calc "-123") -123)

(assert (calc "(123)") 123)

(assert (calc "(((123)))") 123)

(assert (calc "1 2 3") 123)

(assert (calc "1+2") (+ 1 2))

(assert (calc "1+-2") (+ 1 -2))

(assert (calc "1-2") (- 1 2))

(assert (calc "1--2") (- 1 -2))

(assert (calc "2*3") (* 2 3))

(assert (calc "2*-3") (* 2 -3))

(assert (calc "2/3") (/ 2 3))

(assert (calc "2/-3") (/ 2 -3))

(assert (calc "2*3+4") (+ (* 2 3) 4))

(assert (calc "2-3*4") (- 2 (* 3 4)))

(assert (calc "2/3+4") (+ (/ 2 3) 4))

(assert (calc "2-3/4") (- 2 (/ 3 4)))

(assert (calc "2*(3+4)") (* 2 (+ 3 4)))

(assert (calc "(2-3)*4") (* (- 2 3) 4))

(assert (calc "2/(3+4)") (/ 2 (+ 3 4)))

(assert (calc "(2-3)/4") (/ (- 2 3) 4))

(assert (calc "1+2+3+4") (+ 1 2 3 4))

(assert (calc "1-2-3") (- (- 1 2) 3))

(assert (calc "1*2*3*4") (* 1 2 3 4))

(assert (calc "1/2/3") (/ (/ 1 2) 3))

(assert (calc "123+456*789") (+ 123 (* 456 789))))

Running the test program should produce no output, on the theory that “no news is good news.”

`> (test-calc)`

We used filter and assert from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/c4SNAfMw.

Pages: 1 2

[...] today’s Programming Praxis exercise, our goal is to write a function to evaluate mathematical expressions. [...]

My Haskell solution (see http://bonsaicode.wordpress.com/2012/07/20/programming-praxis-infix-expression-evaluation/ for a version with comments):

http://pastebin.com/iJKwEbNJ

a tough one for me, took a good 5 hours to get it bug free.

Python 3.3

[...] Pages: 1 2 [...]