Stacked Solution

I love when I get exposed to new ideas and concepts that enhance my work or expand my intellectual acumen. That is one of the reasons why I picked software development as a career: each day I learn something in the job. It is never boring.

Especially people like me that did not acquire a traditional Computer Science degree (I actually learned programming through this public-private initiative.), chance upon concepts of CS that both better our overall programming understanding and explain the theory behind our coding practices.

I had the opportunity to work on a computer science problem with Tim Mansfield, a very knowledgeable programmer and, as it could be noticed from the short interaction we had, a great guy.

The problem we worked together is called Balanced parenthesis. Later I learned that balanced parenthesis is one of the tasks done by a compiler. It verifies if parentheses in a source code have their counterpart or not. For example you would want that each opening ‘{‘ or ‘(‘ in a source code must have a corresponding closure ‘}’ or ‘)’. So if the code is not put properly, i.e. if they are not balanced ‘{(})’, the compiler should throw an error.

Here is the problem at length:

Write a function to determine if a string is
‘balanced’. Balanced means that opening and closing
brackets match each other in the proper order. Other
characters are possible and should be handled. The
possible characters for balancing are {}, (), and []

Example Input:

‘{}’ -> True
‘{[]}’ -> True
‘{5}’ -> True
‘{[}’ -> False
‘[A]{}d()’ -> True
‘a’ -> True
‘a}’ -> False
‘([)]’ -> False
‘([])’ -> True
‘{‘ -> False
‘{{{{}}}’ -> False

The best way to solve this is to break down the problem at hand by writing in plain English.

  #split the string into an array of characters
  #loop through the array
  #if open symbol i.e. '{','[','(' then store them in a list
  #if closing symbol then remove last opening symbol in list
  # if everything matches then the remaining list should be empty, otherwise there is unbalanced symbol.

Therefore delving now into the code we have:

def is_balanced(input)
 #split the string into an array of characters
  array_chars = input.chars

  open_brackets = []
 #loop through the array
  array_chars.each do |char|
    #if open symbol i.e. '{','[','(' then store them in a list
    if char =~ /[\[|\{|\(]/
      open_brackets << char
    elsif char =~ /[\]|\}|\)]/
      #if closing symbol matches an its opening symbol then remove last opening symbol in list
      bracket_matching = { ']' => '[', '}' => '{', ')' => '('}
      bracket = bracket_matching[char]
      return false unless open_brackets.include?(bracket)
      open_brackets.pop
    end
  end
  # if everything matches then the remaining list should be empty, otherwise there is unbalanced parenthesis.
  open_brackets.empty?
end

is_balanced('{{}}’) #=> true
is_balance('[(])') #=> false

We notice in this code that there is always inserting and removing one element from the end of the array. What is entering last, it is actually coming out first.

The implemented solution to this problem is called a Stack data structure. Thinking again, I remember implemented something similar when I worked on a linked-list problem months ago. There you go. I learned something that has already an impacted on my programming skills and for that it made my day.

Advertisements

2 thoughts on “Stacked Solution

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s