# Balanced parenthesis in Ruby

Posted on

Problem

I’m solving the “Balanced Parenthesis” problem in Ruby, and I came up with this solution.

def balanced?(string)
return false if string.length.odd?

pairs = { '{' => '}', '[' => ']', '(' => ')' }

string.chars.each_with_object([]) do |bracket, stack|
if pairs.keys.include?(bracket)
stack << bracket
elsif pairs.values.include?(bracket)
return false unless pairs[stack.pop] == bracket
else
return false
end
end

true
end


The first check is for the length of the string: If it’s odd, the can’t be balanced.

I then iterate over the chars of the string:

1. If I find an opening bracket, I add it to an array.
2. If I find a closing bracket, I remove the last element from the array and check if the brackets are a pair.
3. If I find neither an opening or a closing bracket, the string must be invalid.

Are there any edge cases I’m missing? Also, this doesn’t seem efficient: First, there’s an added dictionary. Second, there is a linear search on each iteration to check either the keys or the values of the dictionary. There’s an O(n)$O\left(n\right)$$O(n)$ on the array resulting from the string, as well, but I’m not sure if we can avoid this.

Solution

To eliminate nested loop you may apply regex checking for invalid symbol from the start — it would be O(n) + O(n) = O(n):

def balanced? string
return false if string.length.odd?
return false if string =~ /[^[](){}]/

pairs = { '{' => '}', '[' => ']', '(' => ')' }

stack = []
string.chars do |bracket|
if expectation = pairs[bracket]
stack << expectation
else
return false unless stack.pop == bracket
end
end

stack.empty?
end


Assuming it’s possible to check each pair separately:

def is_balanced(opener, closer, str)
cnt = 0
adds = {opener => 1, closer => -1}
pars = str.chars.select{|c| [opener, closer].include? c }
pars.each{ |c| cnt += adds[c]; return false if cnt < 0 }
cnt == 0
end

def is_balanced2(str)
[['(', ')'], ['[', ']'], ['{', '}']].map{ |ps| is_balanced(*ps, str) }.all?
end


Constant Time solution, assuming you know the paren chars:

    def is_valid(str)
characters = [
'(', ')',
'{', '}',
'[', ']',
]

if str.count(characters[0]) != str.count(characters[1])
return false
end

if str.count(characters[2]) != str.count(characters[3])
return false
end

if str.count(characters[4]) != str.count(characters[5])
return false
end

true
end


Its beautifully simple.