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

Question

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

`==` is used to compare `regex == regex`, NOT `regex == string`. You want to use `~=` or `match`. Take a look at the [docs](http://www.ruby-doc.org/core-2.0.0/Regexp.html#method-i-3D-3D) — , Dec 23 '13 at 16:49
You can't use regex to check the order of brackets and pretheses you have to use a LIFO structure of data. — rullof, Dec 23 '13 at 16:51
That's not the kind of check you want to perform with regular expressions. — Simone Carletti, Dec 23 '13 at 16:52
@rullof You are wrong. Common confusion between "regular expression" and "regular grammar" seen in beginners. — sawa, Dec 23 '13 at 17:19

WDan · Answer 1 · 2013-12-24T03:33:50.510

11

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

edited Dec 24 '13 at 03:33

answered Dec 23 '13 at 16:29

WDan

533
1
4
13

That is only a necessary condition. – sawa Dec 23 '13 at 16:31
So, you mean there might be some cases that one string could pass the algorithm I mentioned but it's still an invalid string? Could you show me any examples? – WDan Dec 23 '13 at 16:37
Look at the OP's second example. – sawa Dec 23 '13 at 16:39
I just omitted the detailed handling description. Of course it is necessary to check whether the stack is empty after the traverse. And yes, we should pop the stack once each time we met a right symbol if the stack is not empty. I just rise an overview about this method since I'm not sure whether there is a `regex` restriction in OP's problem:) – WDan Dec 23 '13 at 16:39
Very nice, Dan. I prefer it to my solution. A possible refinement: 1. `left_symbols = {'{' => '}', '[' => ']', '(' => ')'}`; 2. remove `right_symbols`; 3. replace the contents of the block with ' left_symbols.key?(c) ? stack << c : (return false if (left_symbols.values.include?(c) && left_symbols[stack.pop] != c))'. – Cary Swoveland Dec 23 '13 at 20:42
@CarySwoveland Your suggestion is great. I've modified my solution. Thanks a lot! – WDan Dec 24 '13 at 03:34

Donovan · Answer 2 · 2013-12-23T22:41:46.427

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

Cary Swoveland · Answer 3 · 2013-12-25T21:40:11.793

5

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.

edited Dec 25 '13 at 21:40

answered Dec 23 '13 at 18:13

Cary Swoveland

106,649
6
63
100

I like this, very elegant. – Donovan Dec 23 '13 at 18:59
You make me blush, @Donovan. – Cary Swoveland Dec 23 '13 at 19:01
@Cary Swoveland Oh wow! How beautiful! I think this one is a really good solution. For some reason I was looking at this problem too simply. But it seems as if it will require a little more creativity than I originally assumed. Thank you! – goldenpath Dec 23 '13 at 21:31

score 2 · Answer 4 · answered Dec 23 '13 at 18:39

2

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

answered Dec 23 '13 at 18:39

Donovan

15,917
4
22
34

1

I just realized this won't match the last test condition, but I'll leave the answer for others who may not need something that complex. – Donovan Dec 23 '13 at 18:42
This answer can be adapted. (although you have to check that `match_point` remains strictly positive at all times, i.e. inside the loop). The issue with this answer currently is that it treats all bracket characters as the same. But you can fix that by creating an auxiliary method that takes as parameters, the start and end bracket characters, and then in `valid_string?` calls `valid_for('(',')',str) && valid_for('{','}', str) && valid_for('[',']',str)` (where `valid_for` is that auxiliary method). – amnn Dec 23 '13 at 20:46
@Donovan Thanks! I think I'll definitely give this a try with asQuirrel's auxiliary method. – goldenpath Dec 23 '13 at 21:38
I just added another answer, inspired by @asQuirreL :) – Donovan Dec 23 '13 at 22:10

score 2 · Answer 5 · answered Mar 26 '14 at 17:58

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

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

5 Answers5