[99p]Multi(Complete)

import Data.List

-- predefines
data Mtree a = Node a [Mtree a] deriving (Eq, Show)
tree1 = Node 'a' []
tree2 = Node 'a' [Node 'b' []]
tree3 = Node 'a' [Node 'b' [Node 'c' []]]
tree4 = Node 'b' [Node 'd' [], Node 'e' []]
tree5 = Node 'a' [
                 Node 'f' [Node 'g' []],
                 Node 'c' [],
                 Node 'b' [Node 'd' [], Node 'e' []]
                 ]

-- problem 70c
mnodecount :: Mtree a -> Int
mnodecount (Node _ []) = 1
mnodecount (Node _ xs) = 1 + (foldr (+) 0 $ map mnodecount xs)

-- problem 70
mtreeStr :: Mtree Char -> String
mtreeStr (Node a []) = [a] ++ "^"
mtreeStr (Node a (x:xs)) = [a] ++ mtreeStr x ++ (concatMap mtreeStr xs) ++ "^"
ctrnoctr :: String -> Int
ctrnoctr "" = 0
ctrnoctr (x:xs) = (if x == '^' then (-1) else 1) + ctrnoctr xs
mspSearch :: String -> [Int]
mspSearch "" = []
mspSearch xs = [-1] ++ (findIndices (==0) $ map ctrnoctr (tail $ inits xs))
diffMsp :: [Int] -> [Int]
diffMsp [] = []
diffMsp [x] = []
diffMsp (x:y:xs) = (y-x) : diffMsp(y:xs)
mspList :: [Int] -> String -> [String]
mspList [] _ = []
mspList ns [] = []
mspList (n:ns) xs = (take n xs) : mspList ns (drop n xs)
strMtree :: String -> Mtree Char
strMtree (x:y:xs)
          | y == '^'   = Node x []
          | y /= '^'   = Node x $map strMtree (mspList ns (y:init xs))
                                  where ns = diffMsp $ mspSearch (y:init xs)

-- problem 71
ipl' :: Int -> Mtree a -> Int
ipl' _ (Node a []) = 0
ipl' n (Node a ts) = n*(length ts) + sum (map (ipl' (n+1)) ts)
iplMtree :: Mtree a -> Int
iplMtree = ipl' 1

-- problem 72
buMtree :: Mtree Char -> String
buMtree (Node a []) = [a]
buMtree (Node a xs) = (concatMap buMtree xs) ++ [a]

-- problem 73
mtreeLtree :: Mtree Char -> String
mtreeLtree (Node a []) = [a]
mtreeLtree (Node a xs) = "(" ++ [a] ++ (concatMap (" "++) $ map mtreeLtree xs) ++ ")"
----- mtreeLtree (Node a xs) = "(" ++ [a] ++ (concatMap mtreeLtree xs) ++ ")"
countparaLeft :: String -> Int
countparaLeft [] = 0
countparaLeft xs = length $ findIndices (=='(') xs
countparaRight :: String -> Int
countparaRight [] = 0
countparaRight xs = length $ findIndices (==')') xs
mdpSearch :: String -> [Int]
mdpSearch xs = [i | i <- findIndices (==' ') xs, countparaLeft (take i xs) == countparaRight (take i xs)]
               ++ [length xs]
diffMdp :: [Int] -> [Int]
diffMdp [] = []
diffMdp [x] = []
diffMdp (x:y:xs) = (y-x) : diffMdp(y:xs)
mdpList :: [Int] -> String -> [String]
mdpList [] _ = []
mdpList ns [] = []
mdpList (n:ns) xs = (tail $take n xs) : mdpList ns (drop n xs)
ltreeMtree :: String -> Mtree Char
ltreeMtree [a] = Node a []
ltreeMtree (x:y:xs)
           |x/='('  = error "dont kidding me"
           |x=='('  = Node y $ map ltreeMtree (mdpList ns $ init xs)
                                   where ns = diffMdp $ mdpSearch (init xs)