interpreter.hs

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