# Balanced parenthesis in Ruby

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)$ on the array resulting from the string, as well, but I'm not sure if we can avoid this.

• There's a subtle bug in my code that perhaps isn't work a new answer. At the end, instead of returning true, I should check to see if the stack is empty. – Mohamad Apr 19 '16 at 19:36
• Nice catch! Updated my answer. – Nakilon Apr 20 '16 at 11:58

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

• Having added my comment re ensuring the stack is empty, I'm finding it hard to think of a scenario that this could be possible. Do you have something in mind? I found this out when one test case failed, but the source of the problem doesn't make the test cases public (which is rediculous). – Mohamad Apr 20 '16 at 14:54
• This one was failing:[[ – Nakilon Apr 20 '16 at 19:52
• I'm curious: Why did you use a temp variable stack instead of using each_with_object like I did? – Mohamad Apr 24 '16 at 11:40
• @Mohamad, I guess after .chars do it would be out of the scope and I'll be unable to call .empty? on it. – Nakilon Apr 25 '16 at 10:19
• True, although technically you could do end.empty?--although that's ugly. – Mohamad Apr 25 '16 at 11:13

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