data AST = C String | Seq AST AST | Star AST | Plus AST AST deriving Show

parse :: String -> AST
parse str = fst (parseRe str)

parseRe :: String -> (AST, String)
parseRe str
   | null rest = (ast, [])
   | head rest == '+' = (Plus ast ast2, rest2)
   | otherwise (ast, rest)
  where  (ast, rest) = parseSq str , (ast2, rest2) = parseRe (tail rest)

parseBa :: String -> (AST, String)
parseBa str = if null rest then (ast, [])
              else if head rest == '*' then (Star ast, tail rest)
              else (ast, rest)
        where
            (ast, rest) = parseEl str

parseSq :: String -> (AST, String)
parseSq str = if null rest then (ast, [])
              else if not (elem (head rest) "*+") then (Seq ast ast2, rest2)
              else (ast, rest)
        where
            (ast, rest) = parseBa str
            (ast2, rest2) = parseSq rest

parseEl :: String -> (AST, String)
parseEl ('(':str) = (ast, rest)
        where
            (ast, rest) = parsePar str
parseEl (x:str) = if isDigit x then ((C [x]), str)
                 else if isLetter x then ((C [x]), str)
                 else error $ "Feil: " ++ [x]

parsePar :: String -> (AST, String)
parsePar (x:str)
    | not (null rest) = (parse token, tail rest)
    | otherwise        = error "Incorrect parentheses"
            where
                token = takeWhile (\e -> (not (elem e ")"))) (x:str)
                rest = dropWhile (\e -> (not (elem e ")"))) (x:str)