ReverseParentheses - Codefights

reverseParentheses.fsx

(*
You are given a string s that consists of English letters, punctuation marks,
whitespace characters and brackets.
It is guaranteed that the brackets in s form a regular bracket sequence.

Your task is to reverse the strings in each pair of matching parenthesis,
starting from the innermost one.

Example
For string "s = a(bc)de" the output should be
reverseParentheses(s) = "acbde".
*)

open System

let test f =
    if f "co(de(fight)s)" = "cosfighted" then printfn "success" else printfn "fail"
    if f "a(bcdefghijkl(mno)p)q" = "apmnolkjihgfedcbq" then printfn "success" else printfn "fail"

// Iteration 1. Let's parse it into a tree.

type El =
    | Node of list<El>
    | Leaf of char

let parse (s: string) : list<El> =
    let rec go (s: string) (pos: int) (acc: list<El>) (stack: list<El>) : list<El> =
        let last = s.Length - 1
        if pos > last then
            acc
        elif s.[pos] = '(' then
            let stack' = (Node []) :: stack
            go s (pos + 1) acc stack'
        elif s.[pos] = ')' then
            match stack with
            | Node xs :: Node xss :: t -> go s (pos + 1) acc (Node (Node (List.rev xs) :: xss) :: t)
            | Node xs :: [] -> go s (pos + 1) (Node (List.rev xs) :: acc) []
            | [] -> failwith "Unbalanced parentheses."
            | _ -> failwith "Unexpected element."
        else
            match stack with
            | Node xs :: t -> go s (pos + 1) acc (Node (Leaf (s.[pos]) :: xs) :: t)
            | [] -> go s (pos + 1) (Leaf (s.[pos]) :: acc) stack
            | _ -> failwith "Unexpected element."
    go s 0 [] [] |> List.rev

let printTree (t: list<El>) =
    let rec go (xs: list<El>) =
        seq {
            for i in xs do
                match i with
                | Leaf c -> yield c
                | Node l -> yield! (go l |> Seq.rev)
        }
    go t |> Array.ofSeq |> String

let revInParens = parse >> printTree

test revInParens

// Iteration 2. Get rid of the accumulator in the "go" function,
//              the stack can hold everything we need.

let parse2 (s: string) : El =
    let rec go (s: string) (pos: int) (stack: list<El>) : El =
        let last = s.Length - 1
        if pos > last then
            match List.head stack with
            | Node xs -> Node (List.rev xs)
            | _ -> failwith "Unexpected element."
        elif s.[pos] = '(' then
            let stack' = (Node []) :: stack
            go s (pos + 1) stack'
        elif s.[pos] = ')' then
            match stack with
            | Node xs :: Node xss :: t -> go s (pos + 1) (Node (Node (List.rev xs) :: xss) :: t)
            | [] -> failwith "Unbalanced parentheses."
            | _ -> failwith "Unexpected element."
        else
            match stack with
            | Node xs :: t -> go s (pos + 1) (Node (Leaf (s.[pos]) :: xs) :: t)
            | [] -> failwith "Unexpected end of stack."
            | _ -> failwith "Unexpected element."
    go s 0 [Node []]

let printTree2 (t: El) =
    let rec go (xs: list<El>) =
        seq {
            for i in xs do
                match i with
                | Leaf c -> yield c
                | Node l -> yield! (go l |> Seq.rev)
        }
    match t with
    | Node xs -> go xs |> Array.ofSeq |> String
    | _ -> failwith "Unexpected leaf."

let revInParens2 = parse2 >> printTree2

test revInParens2

// Iteration 3. Get rid of the fancy tree structure,
//              replace it with a list of chars.

let parse3 (s: string) =
    let rec go (s: string) (pos: int) (stack: list<list<char>>) : list<char> =
        if pos > s.Length - 1 then
            List.head stack |> List.rev
        elif s.[pos] = '(' then
            let stack' = [] :: stack
            go s (pos + 1) stack'
        elif s.[pos] = ')' then
            match stack with
            | top :: next :: rest -> go s (pos + 1) ((List.rev top @ next) :: rest)
            | _ -> failwithf "Parse error at pos %d." pos
        else
            match stack with
            | top :: rest -> go s (pos + 1) ((s.[pos] :: top) :: rest)
            | _ -> failwithf "Parse error at pos %d." pos
    go s 0 [[]] |> List.toArray |> String

test parse3


// Iteration 4. Get rid of the explicit recursion,
//              replace it with `fold`.

/// Executes a fold operation within a list passing as parameter of the folder function 
/// the zero based index of each element.
let foldi fold first source =
    source
    |> List.fold (fun (prev,i) c -> (fold i prev c,i + 1)) (first,0)
    |> fst

let parse4 (s: string) =
    let go pos (stack: list<list<char>>) (c: char) : list<list<char>> =
        let fail () = failwithf "Parse error at pos %d, char '%c'." pos c
        if c = '(' then
            [] :: stack
        elif c = ')' then
            match stack with
            | top :: next :: rest -> ((List.rev top @ next) :: rest)
            | _ -> fail ()
        else
            match stack with
            | top :: rest -> ((c :: top) :: rest)
            | _ -> fail ()
    s |> Seq.toList |> foldi go [[]] |> List.head |> List.rev |> List.toArray |> String

test parse4

// Iteration 5. Prettify: replace if/else with pattern matching.

let parse5 (s: string) =
    let go pos (stack: list<list<char>>) (c: char) : list<list<char>> =
        let fail () = failwithf "Parse error at pos %d, char '%c'." pos c
        match c with
        | '(' -> [] :: stack
        | ')' ->
            match stack with
            | top :: next :: rest -> ((List.rev top @ next) :: rest)
            | _ -> fail ()
        | _ ->
            match stack with
            | top :: rest -> ((c :: top) :: rest)
            | _ -> fail ()
    s |> Seq.toList |> foldi go [[]] |> List.head |> List.rev |> List.toArray |> String

test parse5