{- |
Description: A string representation of binary trees
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P67" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P67 (treeToString, stringToTree) where

import           Problems.BinaryTrees

{- |
Somebody represents binary trees as strings of the following form:

> a(b(d,e),c(,f(g,)))

Write a function to generate this string representation from a binary tree.
-}
treeToString :: Tree Char -> String
treeToString :: Tree Char -> String
treeToString Tree Char
Empty = String
""
treeToString (Branch Char
c Tree Char
Empty Tree Char
Empty) = [Char
c]
treeToString (Branch Char
c Tree Char
l Tree Char
r) = [Char
c] String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
"(" String -> String -> String
forall a. [a] -> [a] -> [a]
++ Tree Char -> String
treeToString Tree Char
l String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
"," String -> String -> String
forall a. [a] -> [a] -> [a]
++ Tree Char -> String
treeToString Tree Char
r String -> String -> String
forall a. [a] -> [a] -> [a]
++ String
")"

-- | Write a function to construct a tree from the string representation.
stringToTree :: String -> Maybe (Tree Char)
stringToTree :: String -> Maybe (Tree Char)
stringToTree String
""  = Tree Char -> Maybe (Tree Char)
forall a. a -> Maybe a
Just Tree Char
forall a. Tree a
Empty
stringToTree [Char
c] = Tree Char -> Maybe (Tree Char)
forall a. a -> Maybe a
Just (Tree Char -> Maybe (Tree Char)) -> Tree Char -> Maybe (Tree Char)
forall a b. (a -> b) -> a -> b
$ Char -> Tree Char -> Tree Char -> Tree Char
forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
c Tree Char
forall a. Tree a
Empty Tree Char
forall a. Tree a
Empty
stringToTree String
s | Just (String
"", Tree Char
t) <- Maybe (String, Tree Char)
p = Tree Char -> Maybe (Tree Char)
forall a. a -> Maybe a
Just Tree Char
t
               | Bool
otherwise = Maybe (Tree Char)
forall a. Maybe a
Nothing
  where p :: Maybe (String, Tree Char)
p = String -> Maybe (String, Tree Char)
parseTree String
s

parseTree :: String -> Maybe (String, Tree Char)
parseTree :: String -> Maybe (String, Tree Char)
parseTree String
""             = (String, Tree Char) -> Maybe (String, Tree Char)
forall a. a -> Maybe a
Just (String
"", Tree Char
forall a. Tree a
Empty)
parseTree cs :: String
cs@(Char
',':String
_)     = (String, Tree Char) -> Maybe (String, Tree Char)
forall a. a -> Maybe a
Just (String
cs, Tree Char
forall a. Tree a
Empty)
parseTree cs :: String
cs@(Char
')':String
_)     = (String, Tree Char) -> Maybe (String, Tree Char)
forall a. a -> Maybe a
Just (String
cs, Tree Char
forall a. Tree a
Empty)
parseTree [Char
c]            = (String, Tree Char) -> Maybe (String, Tree Char)
forall a. a -> Maybe a
Just (String
"", Char -> Tree Char -> Tree Char -> Tree Char
forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
c Tree Char
forall a. Tree a
Empty Tree Char
forall a. Tree a
Empty)
parseTree (Char
c:cs :: String
cs@(Char
',':String
_)) = (String, Tree Char) -> Maybe (String, Tree Char)
forall a. a -> Maybe a
Just (String
cs, Char -> Tree Char -> Tree Char -> Tree Char
forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
c Tree Char
forall a. Tree a
Empty Tree Char
forall a. Tree a
Empty)
parseTree (Char
c:cs :: String
cs@(Char
')':String
_)) = (String, Tree Char) -> Maybe (String, Tree Char)
forall a. a -> Maybe a
Just (String
cs, Char -> Tree Char -> Tree Char -> Tree Char
forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
c Tree Char
forall a. Tree a
Empty Tree Char
forall a. Tree a
Empty)
parseTree (Char
c:Char
'(':String
cs) = do
  (Char
',':String
cs',Tree Char
l) <- String -> Maybe (String, Tree Char)
parseTree String
cs
  (Char
')':String
cs'',Tree Char
r) <- String -> Maybe (String, Tree Char)
parseTree String
cs'
  (String, Tree Char) -> Maybe (String, Tree Char)
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (String
cs'', Char -> Tree Char -> Tree Char -> Tree Char
forall a. a -> Tree a -> Tree a -> Tree a
Branch Char
c Tree Char
l Tree Char
r)
parseTree String
_ = Maybe (String, Tree Char)
forall a. Maybe a
Nothing