CODEWITHSUNDEEP
rubyregexrubular
goldenpath
goldenpath

Reputation: 137

How to check validity of closed brackets, parentheses or brackets in Ruby

Write a method 'valid_string?' that accepts a string. It returns true if the brackets, parentheses, and curly braces close correctly. It returns false otherwise.

valid_string?("[ ]")                  # returns true
valid_string?("[  ")                  # returns false
valid_string?("[ ( text ) {} ]")      # returns true
valid_string?("[ ( text { ) } ]")     # returns false

My code: Is returning false for everything. Even tried using explicit booleans for individual cases {} || () ||, etc. Did not work. Either returns true or false for everything. Is it my driver code?

def valid_string?(str) 

    if str == ("\[\s+]")
        true
    else
        false
    end
end

UPDATED SOLUTION:------------------------------------------------ Yes! #match definitely worked out better! Although my last line of test code is evaluating to true. When it should be false. . .

def valid_string?(str) 
if str.match "(\\[.+\\])" || "|(\\(\\))" || "|({})"
    return true
else
    return false
    end
end

puts valid_string?("[ ]")                  # returns true
puts valid_string?("[  ")                  # returns false
puts valid_string?("[ ( text ) {} ]")      # returns true
puts valid_string?("[ ( text { ) } ]")     # returns false

Upvotes: 13

Views: 7500

Answers (5)

wontwon
wontwon

Reputation: 241

I found recursion to work really well in this situation. Hope this helps!

def valid_string?(string)
  bracket_string = string.gsub(/[^\[\]\(\)\{\}]/,'').gsub('()','').gsub('[]','').gsub('{}','')
  return true if bracket_string.empty?
  return false if bracket_string.length.odd?
  return false if bracket_string.include?(string)
  valid_string?(bracket_string)
end

Upvotes: 2

Cary Swoveland
Cary Swoveland

Reputation: 110725

Here's a way that doesn't use regex:

def valid_string?(str)
  strim = str.gsub(/[^\[\]\(\)\{\}]/,'')
  return true if strim.empty?
  return false if strim.size.odd?
  loop do  
    s = strim.gsub('()','').gsub('[]','').gsub('{}','')
    return true if s.empty?
    return false if s == strim
    strim = s
  end   
end

p valid_string?("[ ]")               # => true
p valid_string?("[  ")               # => false
p valid_string?("[ ( text ) {} ]")   # => true
p valid_string?("[ ( text { ) } ]")  # => false
p valid_string?("[ ( text { more text { (more text) }} )]")  # => true
  • First remove all characters other than those in "()[]{}".
  • If the remaining string is empty, return true
  • If the remaining string contains an odd number of characters, return false.
  • Continue removing adjacent pairs '()', '[]' and '[]' until either the string is empty, in which case return true, or no more adjacent pairs can be removed and the string is non-empty, in which case return false.

Upvotes: 5

WDan
WDan

Reputation: 573

I think it might be complicated to use regex to solve this problem. Here is a potential solution: You may use a stack to record the left symbol like {, [, ( in the traverse. Each time you met the right symbol, just check whether the symbol on the stack top matches this right symbol. Simply return false if not match.

Below is my code:

def valid_string?(str)
  stack = []
  symbols = { '{' => '}', '[' => ']', '(' => ')' }
  str.each_char do |c|
    stack << c if symbols.key?(c)
    return false if symbols.key(c) && symbols.key(c) != stack.pop
  end
  stack.empty?
end

puts valid_string?('[ ]')                  # returns true
puts valid_string?('[  ')                  # returns false
puts valid_string?('[ ( text ) {} ]')      # returns true
puts valid_string?('[ ( text { ) } ]')     # returns false

Upvotes: 11

Donovan
Donovan

Reputation: 15917

Just because it was fun, I went ahead and solved this The Ruby Way :)

class Brackets
  class Bracket
    def initialize(open, close)
      @open = open
      @close = close
      @match_count = 0
    end
    attr_reader :match_count, :open, :close

    def check(c)
      @match_count += 1 if c == @open
      @match_count -= 1 if c == @close
    end
  end

  def initialize
    @brackets = []
    @stack = []
    @valid = true
  end

  def add(open, close)
    @brackets << Bracket.new(open,close)
  end

  def check(c)
    @brackets.each do |b|
      b.check(c)
      @stack.push(c) if c == b.open
      @valid = false if c == b.close and @stack.pop != b.open
    end
  end

  def valid?
    total = 0
    @brackets.each { |b| total += b.match_count }
    total == 0 && @valid == true
  end
end

def valid_string?(str)
  brackets = Brackets.new
  brackets.add('[', ']')
  brackets.add('{', '}')
  brackets.add('(', ')')

  str.each_char { |c| brackets.check(c) }
  brackets.valid?
end

# Our tests
puts valid_string?("[ ]") ? 'true' : 'false'                 # returns true
puts valid_string?("[  ") ? 'true' : 'false'                 # returns false
puts valid_string?("[ ( text ) {} ]") ? 'true' : 'false'     # returns true
puts valid_string?("[ ( text { ) } ]") ? 'true' : 'false'    # returns false
puts valid_string?("[ ( text { } ) ]") ? 'true' : 'false'    # returns true

Upvotes: 6

Donovan
Donovan

Reputation: 15917

How about a simple counting routine?

def valid_string?(str)
  match_count = 0

  str.each_char do |c|
    match_count += 1 if [ '[', '{', '(' ].include?(c)
    match_count -= 1 if [ ']', '}', ')' ].include?(c)
  end

  return match_count == 0
end

Upvotes: 2

Related Questions