## 実装

parsecに投げた。 やる気のない実装だが問題相応だと思われる。

#!/usr/bin/env runhaskell
{-# LANGUAGE FlexibleContexts #-}
module Main where
import Control.Exception (assert)
import Control.Applicative
import Data.Maybe
import Data.Ratio
import qualified Data.Map as M
import Text.Parsec hiding ((<|>))
import Text.Parsec.Expr

data Expr
= Var Integer Integer
| Add Expr Expr
| Sub Expr Expr
| Mul Expr Expr
| Div Expr Expr
| Pow Expr Expr
deriving Show

symbol c = try $spaces >> char c parens = try . between (symbol '(') (symbol ')') natural = (<?> "nat") . try$ do
spaces
n <- many1 digit
return (read n :: Integer)
constant = (<?> "constant") $do n <- natural return$ Var n 0
var = (<?> "var") $do symbol 'x' return$ Var 1 1
table =
let op c f = Infix ( symbol c >> return f ) AssocLeft in
[ [ op '^' Pow
]
, [ op '*' Mul
, op '/' Div
, Infix ( return Mul ) AssocLeft
]
, [ op '+' Add
, op '-' Sub
, Prefix ( symbol '-' >> return (Mul (Var (-1) 0)) )
]
]
expr = try (buildExpressionParser table term <?> "expr")
term = try
(parens expr
<|> var
<|> constant)
<?> "term"
parseExpr :: String -> Expr
parseExpr s = case parse expr s s of
Right e -> e
Left err -> error $show err unsafeRatioToInt :: Integral a => Ratio a -> a unsafeRatioToInt q = assert (denominator q == 1)$ numerator q

calculateExpr :: Expr -> M.Map Integer Rational
calculateExpr (Var a n) = M.singleton n (fromIntegral a)
calculateExpr (Add e e') = M.unionWith (+) (calculateExpr e) (calculateExpr e')
calculateExpr (Sub e e') = M.unionWith (+) (calculateExpr e) (M.map negate $calculateExpr e') calculateExpr (Mul e e') = M.fromListWith (+)$ do
(n, a) <- M.toList $calculateExpr e (m, b) <- M.toList$ calculateExpr e'
[(n + m, a * b)]
calculateExpr (Div e e') =
M.fromListWith (+) $do (n, a) <- M.toList$ calculateExpr e
(m, b) <- M.toList $calculateExpr e' [(n - m, a / b)] calculateExpr (Pow e e') = M.fromListWith (+)$ do
(n, a) <- M.toList $calculateExpr e (0, b) <- M.toList$ calculateExpr e'
let b' = unsafeRatioToInt b -- ???
[(n * b', a ^ b')]

formatTerm :: (Integer, Rational) -> String
formatTerm (n, q) = case (n, unsafeRatioToInt q) of
(_,  0) -> ""
(1,  1) ->  "x"
(n,  1) ->  "x^" ++ show n
(1, -1) -> "-x"
(n, -1) -> "-x^" ++ show n
(0,  q) -> show q
(1,  q) -> show q ++ "x"
(n,  q) -> show q ++ "x^" ++ show n

putPlus :: String -> String
putPlus "" = ""
putPlus ('-' : s) = " - " ++ s
putPlus s = " + " ++ s

formatTerms :: M.Map Integer Rational -> String
formatTerms e =
let ts = map formatTerm $M.toDescList e in concat (head ts : map putPlus (tail ts)) simplify :: String -> String simplify = formatTerms . calculateExpr . parseExpr -- simplify = show . parseExpr main :: IO () main = do t <- readLn replicateM_ t$ do
s <- getLine
putStrLn \$ simplify s