4
\$\begingroup\$

So I have this code that is my attempt at a coding test from Codility. While my code produces correct results according to the requirements, (which unfortunately are copyrighted so I don't think I can reproduce them here), but I feel like it could be better organized, and in some places use a more functional approach to solving the problem.

So the basic idea is that it tests if the string if its properly nested parenthesis, or can be split into 2 halves which are properly nested.

let rec isNested (s : System.String) = 
    let s = s.ToCharArray()
    let s = List.ofArray s
    match s with
    | [] -> true //if its empty then its properly nested
    | _ -> 
        match s.Length % 2 with
        //if its even split the list in to 2 halves and test them
        | 0 -> //test form VW

            let len = s.Length
            let half = len / 2
            let mutable firsthalf = []
            let mutable secondhalf = []
            for i in 0..half - 1 do
                firsthalf <- s.[i] :: firsthalf
            for i in half..len - 1 do
                secondhalf <- s.[i] :: secondhalf
            firsthalf <- List.rev firsthalf 
            secondhalf <- List.rev secondhalf
            let VWtest = 
                isNested (new string(Array.ofList (firsthalf))) && isNested (new string(Array.ofList (secondhalf)))
            match VWtest with
            | true -> true
            | false -> 
                match (s.[0], s.[s.Length - 1]) with
                | ('(', ')') -> 
                  //remove the first and last elements  
                    let sublist = 
                        s.Tail
                        |> List.rev
                        |> List.tail
                        |> List.rev 
                    isNested (new string(Array.ofList (sublist)))
                | _ -> false
        | _ -> false //not a string with an even number of chars therefore can't be properly nested

let test = isNested >> Console.WriteLine
//let expect (b : bool) = Console.WriteLine(" expected ", b)
test "()"     // expect true
test ")("     // expect false
test "(())"   // expect true
test "()()"   // expect true
test "()(()"  // expect false
test "(()())" // expect true
\$\endgroup\$
0

2 Answers 2

11
\$\begingroup\$

The algorithm is overly complicated, and incorrect: for example, it will fail on the input (())().

I feel like it could ... use a more functional approach to solving the problem.

There is a more functional approach, maintaining a count of how many parentheses are open.

Let's start with the function signature

let rec isNested' (parens : char list) (openParens : int) : bool =

And fill in the cases. If there are no parentheses left to process, and no open parentheses, they are properly nested.

    match parens, openParens with
    | [], 0 -> true

If we are processing a (, we increase the open parentheses count

    | '(' :: rest, _ -> isNested' rest (openParens + 1)

I'll leave the other two cases up to you.

For convenience, we add a wrapper for this function

let isNested (parens : string) = isNested' (List.ofSeq parens) 0
\$\endgroup\$
4
  • \$\begingroup\$ ah, I learn something new everyday. That is a much more efficient way of viewing the problem. I had a hard time understanding what the pattern ')' :: rest meant in the past. So I get now that you are matching the ')' as being the head of the list and giving the tail of the list an alias called rest that you can use later. I have a few books on F# but never has it been so illustrated so clearly. Thanks. \$\endgroup\$ Sep 2, 2014 at 1:08
  • 2
    \$\begingroup\$ @AlexanderRyanBaggett thank you :) a good follow-up exercise is to determine if a string consisting of the characters (, ), [, ], {, and } is properly nested. \$\endgroup\$
    – mjolka
    Sep 2, 2014 at 1:12
  • \$\begingroup\$ I have posted an update, I am very close, but still not quite there. \$\endgroup\$ Sep 2, 2014 at 1:26
  • \$\begingroup\$ You can simplify that wrapper slightly by using List.ofSeq parens. \$\endgroup\$
    – svick
    Sep 2, 2014 at 8:52
2
\$\begingroup\$

Another approach...
Map the characters in the string as having a value of 1 for '(' and -1 for ')'.
Scan to get cumulative sums of the mapped values.
If all the cumulative sums are >= 0 and the last sum is = 0, the nesting is correct.

let isNested (chs : string) = 

    let scores = 
        (chs.ToCharArray())
        |> Seq.map (fun ch -> 
                        match ch with
                        |   '(' -> 1
                        |   ')' -> -1
                        |   _   -> 0)
        |>  Seq.scan (fun counter value -> counter + value) 0 // or |>  Seq.scan (+) 0
        |>  Seq.cache

    scores 
    |> Seq.forall (fun counter -> counter >= 0)
    && 
    scores 
    |> Seq.last = 0
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.