Claudio Cherubino's blog Life of a Googler

22Jul/083

Balanced parenthesis

Checking whether a series of parenthesis is balanced and valid is a classic puzzle in computer science and can be easily met during a job interview.

In my opinion, there is no better solution than using a regular expression and solve the problem with a single (but almost unreadable) line of code, however I'd like to describe an algorithm which can be easily implemented in any functional or imperative programming language.

The idea is simple: start from the first character and check if it is an opening parenthesis. In this case we have to push it on a LIFO data structure such as a stack and continue with the next character.

If the character is a closing parenthesis, we take (pop) the top element from the stack and check if it makes a valid couple of brackets with the examined element.

If this is not the case, the series is not balanced, otherwise we can discard both parenthesis and go on with the next character, until the series is over.

When there are no parenthesis left to examine, if the stack is empty our series is valid; if there are still elements on the stack we can conclude that the series is unbalanced.

Lets give a look at the F# implementation I wrote to answer Dev102's challenge:

#light

let brackets = [('(',')'); ('[',']'); ('{','}'); ('<','>')]

let is_opening bracket =  List.exists ( fun (a,b) -> a = bracket) brackets
let is_closing bracket =  List.exists ( fun (a,b) -> b = bracket) brackets
let is_valid (opening, closing) = List.exists (fun (a,b) -> (a,b) = (opening, closing)) brackets

let rec check_valid stack char_array  =
   match char_array with
   | [] -> stack = List.Empty
   | c::cs when is_opening c -> check_valid (c::stack) cs
   | c::cs ->
      match stack with
      | [] -> false
      | x::xs when is_valid (x, c) -> check_valid xs cs
      | x::xs -> false

At the beginning I defined the list of valid couples and three functions to check respectively if a char is an opening or closing bracket or if a couple is valid.

After that there is a function implementing the algorithm explained above. The stack is just a normal list, where items are always added and removed from the front.

Comments (3) Trackbacks (2)
  1. When does this return true?
    And when do you use is_closing?

  2. The trick to return true is hidden in this line:

    | [] -> stack = List.Empty

    remember that = is the comparison operator, as the == operator in other languages.

    This line says: when char_array is empty, if the stack is empty return true, otherwise return false.

    Actually, I didn’t use the is_closing function and I assumed that every character that is not an opening bracket will be a closing one.

    To be safe, I’d add another line to the first pattern matching and check if the examined character is a closing parenthesis.
    Any other character should warn the user that the input string is not valid.

  3. Just to be theoretical :-) , remember that “pure” regular expressions (I mean: something that can be translated into finite automatons) aren’t expressive enough to solve the balanced-parenthesis problem.
    It is also true that most regular expressions implementations are expanded so to fit also this as a special case.


Leave a comment

(required)