Programming Praxis – Infix Expression Evaluation

In today’s Programming Praxis exercise, our goal is to write a function to evaluate mathematical expressions. Let’s get started, shall we?

Basically this exercise boils down to writing a small parser. As always, Parsec is my go-to library for this task.

import Control.Applicative ((<$), (<$>))
import Text.Parsec
import Text.Parsec.Expr
import Text.Parsec.Language
import Text.Parsec.Token

Since parsing mathematical expressions is such a common task, Parsec has some built-in functionality for it. Also, I’m using lexeme parsers so I don’t have to manually deal with whitespace. The reason for choosing the mondrian token parser rather than haskell is that — in Haskell signifies a comment, whereas in this case it means subtracting a negative number. Obviously I could just use the haskell definition and modify the commentLine string, but this was shorter. The reason for using a custom number parser instead of the default one for natural numbers is that we must also deal with numbers in which the digits are separated by whitespace.

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

To see if everything is working properly, we have a decent-sized test suite:

main :: IO ()
main = mapM_ (print . (\(a,b) -> either (const False) (== b) $ eval a))
           [ ("123",         123)
           , ("-123",        -123)
           , ("(123)",       123)
           , ("(((123)))",   123)
           , ("1 2 3",       123)
           , ("1+2",         1 + 2)
           , ("1+-2",        1 + (-2))
           , ("1-2",         1 - 2)
           , ("1--2",        1 - (-2))
           , ("2*3",         2 * 3)
           , ("2*-3",        2 * (-3))
           , ("2/3",         2 / 3)
           , ("2/-3",        2 / (-3))
           , ("2*3+4",       2 * 3 + 4)
           , ("2-3*4",       2 - 3 * 4)
           , ("2/3+4",       2 / 3 + 4)
           , ("2-3/4",       2 - 3 / 4)
           , ("2*(3+4)",     2 * (3 + 4))
           , ("(2-3)*4",     (2 - 3) * 4)
           , ("2/(3+4)",     2 / (3 + 4))
           , ("(2-3)/4",     (2 - 3) / 4)
           , ("1+2+3+4",     1 + 2 + 3 + 4)
           , ("1-2-3",       1 - 2 - 3)
           , ("1*2*3*4",     1 * 2 * 3 * 4)
           , ("1/2/3",       1 / 2 / 3)
           , ("123+456*789", 123 + 456 * 789)
           ]
About these ads

Tags: , , , , , , , , , ,

One Response to “Programming Praxis – Infix Expression Evaluation”

  1. programmingpraxis Says:

    Whitespace between the digits of a number is a bug, not a feature. I left it the way I did because I didn’t want to be bothered with skipping blanks everywhere — I’m primarily interested in illustrating a recursive descent parser. It’s neat that you so carefully preserved my bug!

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 35 other followers

%d bloggers like this: