Parenthesis Matching F#

Question

So I am trying to use f# to find if a string has matching parentheses. i.e: (abc) returns true, ((hello) returns false, and )( returns false, etc...

What I (think) am doing is using a stack to push when it sees a '(' and pop when it sees a ')' in the list. Then if the string list is empty, either the stack has an item or it doesn't. If it does, then I say that it is invalid, if I come across a ')' and the stack is empty, it is also invalid. Otherwise it is a valid string.

// Break string
let break_string (str:string) =
    Seq.toList str

let isBalanced (str:string) =
    let lst = break_string str
    let stack = []
    let rec balance str_lst (stk:'a list)= 
        match str_lst with
        | [] -> 
            if stk.Length > 0 then
                false
            else 
                true
        | x::xs -> 
            if x = '(' then
                balance (xs x::stack)
            elif x = ')' then
                if stack.Length = 0 then
                    false
                else
                    stack = stack.tail
    balance (lst, stack)

I am pretty new to f# so I think this might be doing what I want, however I get the error message: "This expression was expected to have type bool but here has type 'a list -> bool"

First, what does that actually mean? Second, since it is returning a bool, why doesn't that work?

last call should be balance lst stack. That's how you call functions with multiple parameters in F#. (a,b) syntax creats a tuple. The same applies to recursive call. — MarcinJuraszek

Søren Debois Søren Debois · Accepted Answer · 2014-03-31T18:02:01

The type-checker thinks you forgot the second argument to balance. When you write this:

balance (xs x::stack)

It means "apply balance to (apply xs to x::stack)". You probably meant this:

balance xs (x::stack)

Your final elif also seems to be missing an else branch, and the line stack = stack.tail looks like you're trying to assign to stack. You can't do that since stack is an immutable variable. Likely you want balance xs (List.tail stack). The principle is that instead of assigning to variables, you call your function with new values.

You have the right idea, of course. It can be much more concise by folding all the matching (what's the letter? what's on the stack?) into one single match statement. The trick is to put all the things you want to look at into a single tuple:

let isBalanced str = 
    let rec loop xs stack = 
        match (xs, stack) with
        | '(' :: ys,  stack -> loop ys ('(' :: stack)
        | ')' :: ys, '(' :: stack -> loop ys stack
        | ')' :: _, _ -> false
        | _ :: ys, stack -> loop ys stack
        | [], [] -> true
        | [], _ -> false
    loop (Seq.toList str) []

Parenthesis Matching F#

1 Answers