Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
DeMorgan
{-# 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.

alogic0 commented Feb 16, 2016

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment