Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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
share|improve this question
    
    
Jamal, if I were to open up a new question with the updated info would it not be flagged as a duplicate since the question is essentially the same? And on the other hand, would I have the option unaccepting his answer until the problem is resolved? –  Alexander Ryan Baggett Sep 2 at 1:33
    
Regarding the incorrect result, you should ask about it on SO if you'd like it fixed. –  Jamal Sep 2 at 1:35
    
While I appreciate the response Jamal, you have not answered either of the questions I just asked. –  Alexander Ryan Baggett Sep 2 at 1:36
1  
So, if my code is ready to go, i.e. no bugs then I post to Code Review where the effeciency and design decisions could be examined, but if it is getting the code to do as it is intended, then I should take it to stackoverflow. Okay I feel I understand now. I was not aware of the need stop updates to questions. I will create a stackoverflow question and link to it from here if that's okay. –  Alexander Ryan Baggett Sep 2 at 1:44

2 Answers 2

up vote 8 down vote accepted

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
share|improve this answer
    
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. –  Alexander Ryan Baggett Sep 2 at 1:08
2  
@AlexanderRyanBaggett thank you :) a good follow-up exercise is to determine if a string consisting of the characters (, ), [, ], {, and } is properly nested. –  mjolka Sep 2 at 1:12
    
I have posted an update, I am very close, but still not quite there. –  Alexander Ryan Baggett Sep 2 at 1:26
    
You can simplify that wrapper slightly by using List.ofSeq parens. –  svick Sep 2 at 8:52
    
@svick thank you, I'll update the post :) –  mjolka Sep 2 at 11:12

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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