Create a gist now

Instantly share code, notes, and snippets.

Embed
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
@thisiswei

This comment has been minimized.

Show comment
Hide comment

@5outh awesome!

@thisiswei

This comment has been minimized.

Show comment
Hide comment
@thisiswei

thisiswei Nov 17, 2013

man haskell is cool!

man haskell is cool!

@sandermak

This comment has been minimized.

Show comment
Hide comment
@sandermak

sandermak Feb 13, 2014

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.

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

This comment has been minimized.

Show comment
Hide comment
@alogic0

alogic0 Feb 16, 2016

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

alogic0 commented Feb 16, 2016

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

@quickdudley

This comment has been minimized.

Show comment
Hide comment
@quickdudley

quickdudley Jun 29, 2017

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

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