{-
?????????: Molecular Formula
URL: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1244
?????°:
19:54 Encryption System??????????§£???????????§??????????????£????????????Haskell???
19:55 ??????TLE????????????????????§???????????????
19:55 ?????????AOJ??£???Parsec??\??£???????????§??????????????\??£??????????????????????????????
19:56 ?????£????????????????????????????????¨???????????¨???Parsec??\??£??¨?????????
19:56 ??????????????????????????????????????\??£?????????????????????????????????
19:57 ??¨???????????¨??§???????????????????????????
20:06 ?????????????§??????????????????£??¨??´??£??????
20:17 ??\??????????????????????????????????????????????????????????????????Parsec???????????§???????????????
20:19 ??¨??????????????????Parsec???????????°??????

7/4
13:26 ??§??????
13:28 AC????????????Haskell
13:29 ?????£??????????????§?????¢?????????????????§???????£?????????£?????????????????????????????????????????????AOJ?????¨??????????????????
-}
import Control.Applicative hiding(many)
import Control.Monad
import Data.List
import Control.Monad.Reader
import Control.Monad.State

type Table = [Atom] 

----------------------------
newtype Parse2 a = Parse2{unParse2 :: Table -> StateT String Maybe a}
newtype Parse a = Parse( Table -> String -> Maybe(String,a))

ask' :: Parse2 Table
ask' = Parse2 $ \t -> StateT $ \s -> return (t,s)

st :: (String -> Maybe(String,a)) -> StateT String Maybe a
st f = StateT $ \s -> do{ (a,b) <- f s;return (b,a)}

unSt :: StateT String Maybe a -> (String -> Maybe(String,a))
unSt (StateT f) = \s -> do{(a,b) <- f s;return (b,a)}

to2 :: Parse a -> Parse2 a
to2 (Parse f) = Parse2 $ st . f

to1 :: Parse2 a -> Parse a
to1 (Parse2 f) = Parse $ unSt . f

to2p :: (Table -> String -> Maybe (String, a)) -> Parse2 a
to2p f = Parse2 $ \x -> StateT $ \s -> do{ (a,b) <- f x s;return (b,a)}

to2p2 :: (Table -> String -> Maybe (a, String)) -> Parse2 a
to2p2 f = Parse2 $ StateT . f


instance Functor Parse2 where
 fmap f m = to2 ( fmap f ( to1 m))

joindre2 :: Parse2(Parse2 a) -> Parse2 a
joindre2 g = to2 $ joindre(fmap to1 (to1 g))

instance Monad Parse2 where
 return a = Parse2 $ return $ return a
 fail _ = to2p2 $ \_ _ -> Nothing
 m >>= f = joindre2(fmap f m)

instance Applicative Parse2 where
 pure = return
 (<*>) = ap  

instance Functor Parse where
 fmap f (Parse g) = Parse $ \a b -> fmap f `fmap` (g a b)

joindre :: Parse(Parse a) -> Parse a
joindre (Parse f) = Parse $ \a b -> do{ (str,Parse g) <- f a b; g a str}


skip :: String -> Parse2 ()
skip str = to2p2 f where
 f _ input
  | str `isPrefixOf` input = Just((),length str `drop` input)
  | otherwise = Nothing

oneOf :: String -> Parse2 Char
oneOf str = to2p2 f where
 f _ input
  | null input = Nothing
  | head input `elem` str = Just(head input,tail input)
  | otherwise = Nothing

(?|) :: Parse2 a -> Parse2 a -> Parse2 a
f ?| g = merge <$> (f ??| g) where
 merge (Left a) = a
 merge (Right a) = a



(??|) :: Parse2 a -> Parse2 b -> Parse2 (Either b a)
h ??| i = to2p $ \t input -> case f t input of
 Nothing -> fmap Left `fmap` (g t input)
 j -> fmap Right `fmap` j
 where
  f = unSt . unParse2 h 
  g = unSt . unParse2 i


many :: Parse2 a -> Parse2 [a]
many p = do
 a' <- p ??| return ()
 case a' of
  Left () -> return []
  Right a -> (a:) `fmap` many p


-------------------------------------



type Atom = (String,Int)

atom :: Parse2 Atom
atom = do
 name <- (:) <$> oneOf ['A'..'Z'] <*> many (oneOf ['a'..'z'])
 table <- ask'
 Just weight <- return $ name `lookup` table -- Nothing calls fail
 return (name,weight)

molecule :: Parse2 Int
molecule = sum <$> many m2

m2 :: Parse2 Int
m2 = p1 ?| p2 where
 p1 = do
  weight <- skip "(" *> molecule <* skip ")"
  num <- number
  return (weight*num)
 p2 = do
  weight <- snd <$> atom
  num <- number ?| return 1
  return (weight*num)


number :: Parse2 Int
number = do
 n <- many (oneOf "0123456789")
 if null n then fail "" else return $ read n

main :: IO ()
main = do
 table <- read_first_part
 latter table

latter :: [(String,Int)] -> IO ()
latter table = do
 dat <- getLine
 unless (dat == "0") $ do
  putStrLn $ case analyze table dat of
   Nothing -> "UNKNOWN"
   Just a -> show a
  latter table

read_first_part :: IO [(String,Int)]
read_first_part = do
 info <- getLine
 if (info == "END_OF_FIRST_PART") then return [] else do
  let [atm, num'] = words info
  let num = read num'
  arr <- read_first_part
  return $ (atm,num) : arr

analyze :: [(String,Int)] -> String -> Maybe Int
analyze table str = do
 (ans,"") <- unParse2 molecule table `runStateT` str
 return ans

Measured memory_bytes: 4064