Writing in Ruby, testing for matching parentheses, brackets and curly braces

Question

The question says to write a function that takes a string of braces, and determines if the order of the braces is valid. It should return true if the string is valid, and false if it's invalid.

All input strings will be nonempty, and will only consist of parentheses, brackets and curly braces: ()[]{}.

The tests should give these:

"(){}[]"   =>  True
"([{}])"   =>  True
"(}"       =>  False
"[(])"     =>  False
"[({})](]" =>  False

The code I've written is:

def validBraces(braces)
  revBraces = braces.reverse
  arr = []
  
  i = -1

  loop do
    i += 1

    if braces[i] == "(" && revBraces[i] == ")"
      arr << 1
    else 
      arr << 0
    end

    if braces[i] == ")" && revBraces[i] == "("
      arr << 1
    else 
      arr << 0
    end

    if braces[i] == "{" && revBraces[i] == "}"
      arr << 1
    else 
      arr << 0
    end

    if braces[i] == "}" && revBraces[i] == "{"
      arr << 1
    else 
      arr << 0
    end

    if braces[i] == "[" && revBraces[i] == "]"
      arr << 1
    else 
      arr << 0
    end

    if braces[i] == "]" && revBraces[i] == "["
      arr << 1
    else 
      arr << 0
    end

    break if i <= braces.length 
  end

  if arr.include? 0
    puts false
  else 
    puts true
  end
end

I cant tell where I've gone wrong and why it doesn't work.

Answer 1

The logics is wrong. You take braces and reverseBraces. And you don't think of cases where the braces are nested. But even when not nested the way you go through the string is not right. Better have a dictionary of "(", "{", "[", ")", "}", "]" and count their frequency (make the closing brackets' counts negative) and see whether they cancel themselves out by building a sum - it should be 0.

def freqs(l)
  h = Hash.new(0)
  l.each do |e|
    h[e] += 1
  end
  return h
end

def balanced(braces)
  fr = freqs(braces.split(""))
  return fr["("] - fr[")"] == 0 && fr["{"] - fr["}"] == 0 && fr["["] - fr["]"] == 0 
end

Answer 2

I would use a stack to solve this problem. Add found opening braces to the stack and for closing braces compare them with the brace from the top of the stack.

def validBraces(braces)
  matches = { '(' => ')', '{' => '}', '[' => ']' }
  stack = []

  braces.chars.each do |char|
    case char
    when *matches.keys
      stack.push(char)
    when *matches.values
      return false if matches[stack.pop] != char
    else
      raise ArgumentError, "Unexpected char `#{char}`"
    end
  end

  stack.empty?
end

validBraces("(){}[]")   #=> true       
validBraces("([{}])")   #=> true       
validBraces("(}")       #=> false   
validBraces("[(])")     #=> false        
validBraces("[({})](]") #=> false            
validBraces("[A]")      #=> Unexpected char `A` (ArgumentError)

Or following OOP:

class Balancer
  MATCHES = { '(' => ')', '{' => '}', '[' => ']' }
  OPENING = MATCHES.keys
  CLOSING = MATCHES.values

  def initialize(string)
    @chars = string.chars
  end

  def valid?
    stack = []

    chars.each do |char|
      case char
      when *OPENING
        stack.push(char)
      when *CLOSING
        return false if MATCHES[stack.pop] != char
      else
        raise ArgumentError, "Unexpected char `#{char}`"
      end
    end

    stack.empty?
  end

  private

  attr_reader :chars
end

Balancer.new("(){}[]").valid?    #=> true       
Balancer.new("([{}])").valid?    #=> true       
Balancer.new("(}").valid?        #=> false   
Balancer.new("[(])").valid?      #=> false        
Balancer.new("[({})](]").valid?  #=> false            
Balancer.new("[A]").valid?       #=> Unexpected char `A` (ArgumentError)

Answer 3

One way to do that is to successively remove strings '()', '[]' and '{}' until either the string is empty, in which case the string is found to be balanced, or at some iteration no string '()', '[]' or '{}' is found, in which case the string is found to be unbalanced.

RGX = /\(\)|\[\]|{}/

def valid_braces(str)
  s = str.dup
  until s.empty?
    return false if s.gsub!(RGX, '').nil?
  end
  true
end

valid_braces '(){}[]'          #=> true
valid_braces '([{}])'          #=> true
valid_braces '([[{[]}]{}]())'  #=> true
valid_braces '(}'              #=> false
valid_braces '[(])'            #=> false
valid_braces '[({})](]'        #=> false
valid_braces('[A]')            #=> false

---

The regular expression reads, "match '()' or '[]' or '{}'". Note that String#gsub! returns nil if no substitutions are performed.

---

I can insert a puts statement to illustrate what is happening at each iteration.

def valid_braces(str)
  s = str.dup
  until s.empty?
    puts s
    return false if s.gsub!(RGX, '').nil?
  end
  true
end

valid_braces '([[{[]}]{}]())'
([[{[]}]{}]())  full string
([[{}]])        '[]', '{}' and '()' removed
([[]])          '{}' removed
([])            '[]' removed
()              '[]' removed
                '()' removed 
  #=> true      as `str` is empty

---

This is probably not as efficient as using a stack, as @spickermann has done. I would implement that a little differently.

CLOSE_TO_OPEN = { ')'=>'(', ']'=>'[', '}'=>'{' }
OPENS = CLOSE_TO_OPEN.values
  #=> ["(", "[", "{"]

def valid_braces(str)
  stack = []  
  str.each_char do |c|
    if OPENS.include?(c)
      stack << c
    else
      return false unless CLOSE_TO_OPEN[c] == stack.pop
    end
  end
  return stack.empty?
end

valid_braces '(){}[]'          #=> true
valid_braces '([{}])'          #=> true
valid_braces '([[{[]}]{}]())'  #=> true
valid_braces '(}'              #=> false
valid_braces '[(])'            #=> false
valid_braces '[({})](]'        #=> false
valid_braces('[A]')            #=> false

---

We can add puts statements to see what is happening.

def valid_braces(str)
  stack = []  
  str.each_char do |c|
    print "stack = #{stack}, c = '#{c}', "
    if OPENS.include?(c)
      stack << c
      puts "pushed '#{c}'"
    else
      return false unless CLOSE_TO_OPEN[c] == stack.pop
      puts "popped '#{CLOSE_TO_OPEN[c]}'"
    end
  end
  puts "stack at end = #{stack}"
  return stack.empty?
end

valid_braces '([[{[]}]{}]())'
stack = [], c = '(', pushed '('
stack = ["("], c = '[', pushed '['
stack = ["(", "["], c = '[', pushed '['
stack = ["(", "[", "["], c = '{', pushed '{'
stack = ["(", "[", "[", "{"], c = '[', pushed '['
stack = ["(", "[", "[", "{", "["], c = ']', popped '['
stack = ["(", "[", "[", "{"], c = '}', popped '{'
stack = ["(", "[", "["], c = ']', popped '['
stack = ["(", "["], c = '{', pushed '{'
stack = ["(", "[", "{"], c = '}', popped '{'
stack = ["(", "["], c = ']', popped '['
stack = ["("], c = '(', pushed '('
stack = ["(", "("], c = ')', popped '('
stack = ["("], c = ')', popped '('
stack at end = []
  #=> true