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.

About these ads

Pages: 1 2

7 Responses to “Infix Expression Evaluation”

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

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

    import Control.Applicative ((<$), (<$>))
    import Text.Parsec
    import Text.Parsec.Expr
    import Text.Parsec.Language
    import Text.Parsec.Token
    
    eval :: String -> Either ParseError Double
    eval = parse expr "" where
        expr  = buildExpressionParser table term
        term  = parens mondrian expr <|> (read <$> many1 (lexeme mondrian digit))
        table = [ [prefix "-" negate]
                , [binary "*" (*), binary "/" (/) ]
                , [binary "+" (+), binary "-" (-) ]
                ]
        prefix name fun = Prefix (fun <$ symbol mondrian name)
        binary name fun = Infix  (fun <$ symbol mondrian name) AssocLeft
    
  3. phil said

    http://pastebin.com/iJKwEbNJ
    a tough one for me, took a good 5 hours to get it bug free.

  4. Mike said

    Python 3.3

    import operator as op
    import re
    
    op = {'+':op.add, '-':op.sub, '*':op.mul, '/':op.floordiv}
    
    def expr(token):
        value = term(token)
        while token and token[0] in ('+', '-'):
            value = op[token.pop(0)](value, term(token))
        return value
    
    def term(token):
        value = factor(token)
        while token and token[0] in ('*', '/'):
            value = op[token.pop(0)](value, factor(token))
        return value
    
    def factor(token):
        if token[0].isdigit():
            value = int(token.pop(0))
    
        elif token[0] == '-':
            token.pop(0)
            value = -factor(token)
            
        elif token[0] == '(':
            token.pop(0)
            value = expr(token)
            
            if token[0] != ')':
                raise SyntaxError("Expected ')', got '%s'" % token[0])
            else:
                token.pop(0)
                
        else:
            SyntaxError("Expected number or '(', got '%s'" % token[0])
            
        return value
    
    
    def calc(expression):
        try:
            token = re.findall(r'(\d+|.)', ''.join(expression.strip().split()))
            value = expr(token)
    
            if token:
                raise SyntaxError("Extra tokens: %s" % token)
    
        except SyntaxError as ex:
            print("Syntax Error:", str(ex))
    
        else:
            return value
    
  5. Pablo said

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

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

Leave a Reply

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

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 598 other followers

%d bloggers like this: