DeMorgan

DeMorgan.hs

{-# LANGUAGE NoMonomorphismRestriction #-}

import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Token hiding (parens)
import Text.ParserCombinators.Parsec.Expr
import Control.Applicative hiding ((<|>))
import Control.Monad
import Prelude hiding (not)

data Expr = Not Expr | And Expr Expr | Or Expr Expr | Var Char | SubExpr Expr deriving Eq

not :: Expr -> Expr
not (Not e)     = e
not (And e1 e2) = Or (not e1) (not e2)
not (Or e1 e2)  = And (not e1) (not e2)
not (Var c)     = Not (Var c)
not (SubExpr e) = not e

instance Show Expr where
  show (Not e)     = "NOT " ++ show e
  show (And e1 e2) = show e1 ++ " AND " ++ show e2
  show (Or e1 e2)  = show e1 ++ " OR "  ++ show e2
  show (Var c)     = [c]
  show (SubExpr e) = "(" ++ show e ++ ")"

parseExpr :: String -> Either ParseError Expr
parseExpr = parse expr ""
  where expr      = buildExpressionParser operators term <?> "compound expression"
        term      =  parens expr <|> variable <?> "full expression"
        operators = [ [Prefix (string "NOT" >> spaces >> return Not)]
                    , [binary "AND" And]
                    , [binary "OR" Or] ]
          where binary n c = Infix (string n *> spaces *> pure c) AssocLeft
        variable = Var     <$> (letter <* spaces)                              <?> "variable"
        parens p = SubExpr <$> (char '(' *> spaces *> p <* char ')' <* spaces) <?> "parens"

main = mapM_ printNotExpr . lines =<< readFile "inputs.txt"
  where printNotExpr e = case parseExpr e of
                          Right x -> print $ not x
                          Left  e -> error $ show e

@5outh awesome!

man haskell is cool!

Shouldn't line 17 be:

not (SubExpr e) = SubExpr $ not e

otherwise invalid trees may arise, e.g. try

(a AND b) OR (c AND d)

as input.

To compile with GHC 7.10.2, I just added the next line at the beginning:
{-# LANGUAGE FlexibleContexts #-}

The problem pointed out by sandermak could be fixed either by his suggestion or by changing the Show instance to define showsPrec instead of show as done in my fork