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

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.

CodePudding user response：

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.

CodePudding user response：

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)