Boolean Evaluation

In [1]:

    

import Data.List


    

In [2]:

    

data ExprTree = One | Zero
    | And ExprTree ExprTree 
    | Or ExprTree ExprTree
    | Xor ExprTree ExprTree
    deriving (Show)


    

In [3]:

    

makeTrees :: String -> [ExprTree]
makeTrees "0" = [Zero]
makeTrees "1" = [One]
makeTrees xs =
    let
        makeNodes (op, ls, rs) =
            [action l r | l <- (makeTrees ls), r <- (makeTrees rs)]
                where action = case op of '|' -> Or
                                          '&' -> And
                                          '^' -> Xor
    in
        concatMap makeNodes splits
    where
        splits =
            map (\(ls, op:rs) -> (op, ls, rs)) $
                map (`splitAt` xs) $ takeWhile (< length xs) [1,3..]


    

In [4]:

    

import Data.Bits


    

In [5]:

    

evalTree :: ExprTree -> Bool
evalTree Zero = False
evalTree One = True
evalTree (And left right) = (evalTree left) && (evalTree right)
evalTree (Or left right) = (evalTree left) || (evalTree right)
evalTree (Xor left right) = (evalTree left) `xor` (evalTree right)


    

In [6]:

    

ways :: String -> Bool -> Int
ways expr result =
    length $ filter (== result) $ map evalTree $ makeTrees expr


    

In [7]:

    

ways "1^0|0|1" False
ways "0&0&0&1^1|0" True


    

    






2






    






10