mmcs-olimp-2011-task1

-- 1
open2close '(' = ')'
open2close '[' = ']'
open2close '{' = '}'
open2close '<' = '>'

close2open ')' = '('
close2open ']' = '['
close2open '}' = '{'
close2open '>' = '<'

isOpen c = elem c "({[<"

complete str = impl str "" "" where
    -- параметры impl: targetStringTail stack result
    impl "" "" res = res
    impl "" st res = res ++ map open2close st
    impl (c:cs) "" res
        | isOpen c = impl cs [c] (res ++ [c])
        | otherwise = impl cs "" (res ++ [close2open c, c])
    impl (c:cs) st@(d:ds) res
        | isOpen c = impl cs (c:st) (res ++ [c])
        | otherwise =
            if
                close2open c == d
            then
                impl cs ds (res ++ [c])
            else
                uncurry (impl cs) $ fix (close2open c) st res


-- если встретили в строке неожиданную закрывающую скобку,
-- пытаемся исправить это с помощью соовтетствующей
-- открывающей скобки c из стека, если таковая была
fix c st res
    | not $ elem c st = (st, (res ++ [c, open2close c]))
    | otherwise = (st', res ++ a' ++ [open2close c])
        where
            (a, b) = span (/= c) st
            a' = reverse $ map open2close a
            st' = tail b