## 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 […]

(I’ve heard rumors of lenders charging higher rates).

Before you fix and flip a property for profit, you should determine

if you have enough funds to see a rehabbing project

through. The tuition of my seminars ranges from $395 to $695 depending on the venue.

Such programs at Spanish schools are a solution for health care workers who

are looking to learn the language quickly. In essence, there can be

no better way of learning English than learning some other language, because the act of learning will cause

you to analyze the origin and construction of

your own language. The more you do it, the more quickly your mind will be able to convert words into the new

language.