Skip to content

Instantly share code, notes, and snippets.

@atomictom
Created May 7, 2015 03:09
Show Gist options
  • Save atomictom/335c4fcffea4100dfc81 to your computer and use it in GitHub Desktop.
Save atomictom/335c4fcffea4100dfc81 to your computer and use it in GitHub Desktop.
import Text.Parsec
import Text.ParserCombinators.Parsec (GenParser)
import Control.Applicative ((<$>), (*>), (<*>), (<*))
type UnaryOp = Integer -> Integer
type BinOp = Integer -> Integer -> Integer
data Expr = Binary BinOp Expr Expr
| Unary UnaryOp Expr
| Num Integer
instance Show Expr where
show (Binary _ e1 e2) = "(" ++ show e1 ++ " op " ++ show e2 ++ ")"
show (Unary _ e1) = "unary " ++ show e1
show (Num n) = show n
main :: IO ()
main = do
input <- getContents
case parse parseExpr "" input of
Left err -> print err
-- Right expr -> print expr *> print (eval expr)
Right expr -> print (eval expr)
parseExpr :: GenParser Char st Expr
parseExpr = parseTerm `chainr1` parseAddSub
parseMultDiv :: GenParser Char st (Expr -> Expr -> Expr)
parseMultDiv = convert <$> oneOf "*/" <* many (char ' ')
where
convert '*' = Binary (*)
convert '/' = Binary (\ a b -> a * modpow b (p-2) p)
p = ((10^9 :: Integer) + 7) :: Integer
parseAddSub :: GenParser Char st (Expr -> Expr -> Expr)
parseAddSub = convert <$> oneOf "+-" <* many (char ' ')
where
convert :: Char -> (Expr -> Expr -> Expr)
convert '+' = Binary (+)
convert '-' = Binary (-)
parseTerm :: GenParser Char st Expr
parseTerm = parseFactor `chainr1` parseMultDiv
parseFactor :: GenParser Char st Expr
parseFactor = number <|> unary <|> parenthetical
where
number = Num . read <$> many1 digit <* many (char ' ')
unary = convert <$> oneOf "+-" <*> parseFactor
parenthetical = between (symbol "(") (symbol ")") parseExpr
symbol s = string s <* many (char ' ')
convert '+' = Unary id
convert '-' = Unary negate
eval :: Expr -> Integer
eval (Num n) = n
eval (Binary op e1 e2) = eval e1 `op` eval e2 `mod` (1000000000+7)
eval (Unary op e1) = op (eval e1)
modpow :: Integer -> Integer -> Integer -> Integer
modpow _ 0 _ = 1
modpow b e m = modpow (b*b `mod` m) (e `div` 2) m * (if e `mod` 2 == 1 then b else 1) `mod` m
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment