How to check validity of brackets in wrong order

I have to write a method that accepts a string and returns true if the brackets aren't empty, parentheses, and curly brackets close correctly It returns false otherwise.

Here is what I've got:

  def empty_brackets?(string)
    %w[ () [] {} ].none?(&string.method(:include?))
  end

  def valid_string?(string)
    match_count = 0

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

I think my valid_string? method is not quite SOLID but most importantly it doesn't pass the test where brackets are in wrong order, like )somebrackets(. Could you please advise how to fix it?

3 answers

  • answered 2018-11-08 00:23 Marcin KoƂodziej

    My attempt, pushing all opening brackets in an array, popping closing ones if they match:

    BRACKET_PAIRS = { '[' => ']', '{' => '}', '(' => ')' }
    
    def valid?(string)
      string.each_char.with_object([]) do |char, bracket_stack|
        if BRACKET_PAIRS.keys.include? char
          bracket_stack << char
        elsif BRACKET_PAIRS.values.include? char
          if char != BRACKET_PAIRS[bracket_stack.last]
            return false
          else
            bracket_stack.pop
          end
        end
      end.empty?
    end
    

  • answered 2018-11-08 01:33 Nate

    Here's a very efficient version. It uses regex, and pulls out all of your braces ({}[]()) into a small array, and then keeps widdling down your pairs until there's nothing left. The second it finds an unmatched pair, it quits and returns false. It also doesn't split the string into a char array, as that will use twice the memory (once for the whole string, and once again for the string split into individual characters).

    BRACKET_PAIRS = { '{' => '}', '[' => ']', '(' => ')' }
    BRACKET_REGEX = /#{BRACKET_PAIRS.to_a.flatten.map { |v| Regexp.escape(v) }.join('|')}/
    
    def valid?(string)
      brackets = string.scan(BRACKET_REGEX)
      while brackets.size > 0
        first = brackets.shift
        last = brackets.pop
        return(false) unless BRACKET_PAIRS[first] == last
      end
    
      return(true)
    end
    

    This code will return true if there are no braces at all.

    If you don't like that, do this:

    BRACKET_PAIRS = { '{' => '}', '[' => ']', '(' => ')' }
    BRACKET_REGEX = /#{BRACKET_PAIRS.to_a.flatten.map { |v| Regexp.escape(v) }.join('|')}/
    
    def valid?(string)
      brackets = string.scan(BRACKET_REGEX)
      return(false) unless brackets.size > 0 # this line is added
    
      while brackets.size > 0
        first = brackets.shift
        last = brackets.pop
        return(false) unless BRACKET_PAIRS[first] == last
      end
    
      return(true)
    end
    

    As a side note, you'll want to avoid making arrays in loops like you did in your example:

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

    This code will create two arrays and 6 strings per character in your string variable. This is very inefficient and you'll use a lot more RAM and CPU than necessary. You want to at the very least make those two arrays outside the loop, since they don't change, and ideally even make them a constant so that you don't even make them every time you call the method. Make them one when your program boots up and use it forever. Little things like this actually make a really big difference, especially when used in a loop.

  • answered 2018-11-08 04:16 Cary Swoveland

    CLOSE_TO_OPEN = { ']'=>'[', '}'=>'{', ')'=>'(' }
    
    def valid?(str)
      str.each_char.with_object([]) do |c,stack|
        case c
        when '[', '{', '('
          stack << c
        when ']', '}', ')'
          return false unless stack.pop == CLOSE_TO_OPEN[c]
        end
      end.empty?
    end
    
    valid? "[a]{b[c{d}e]fg}" #=> true
    valid? "[a]{b[c{d]e}fg}" #=> false
    

    The behaviour of the method can be seen by adding some puts statements.

    def valid?(str)
      str.each_char.with_object([]) do |c,stack|
        puts "c=#{c}, stack=#{stack}"
        case c
        when '[', '{', '('
          stack << c
          puts "  stack after 'stack << #{c}' = #{stack}"
        when ']', '}', ')'
          print "  stack.pop (#{stack.last||'nil'})==CLOSE_TO_OPEN[#{c}] " +
                "(#{CLOSE_TO_OPEN[c]})=>"
          puts stack.last == CLOSE_TO_OPEN[c] ? "true, so continue" :
            "false, so return false"
          return false unless stack.pop == CLOSE_TO_OPEN[c]
        end
      end.tap { |stack| puts "At end, '#{stack}.empty?` (#{stack.empty?})" }.empty?
    end
    

    valid? "[a]{b[c{d}e]fg}"
    c=[, stack=[]
      stack after 'stack << [' = ["["]
    c=a, stack=["["]
    c=], stack=["["]
      stack.pop ([)==CLOSE_TO_OPEN[]] ([)=>true, so continue
    c={, stack=[]
      stack after 'stack << {' = ["{"]
    c=b, stack=["{"]
    c=[, stack=["{"]
      stack after 'stack << [' = ["{", "["]
    c=c, stack=["{", "["]
    c={, stack=["{", "["]
      stack after 'stack << {' = ["{", "[", "{"]
    c=d, stack=["{", "[", "{"]
    c=}, stack=["{", "[", "{"]
      stack.pop ({)==CLOSE_TO_OPEN[}] ({)=>true, so continue
    c=e, stack=["{", "["]
    c=], stack=["{", "["]
      stack.pop ([)==CLOSE_TO_OPEN[]] ([)=>true, so continue
    c=f, stack=["{"]
    c=g, stack=["{"]
    c=}, stack=["{"]
      stack.pop ({)==CLOSE_TO_OPEN[}] ({)=>true, so continue
    At end, '[].empty?` (true)
      #=> true
    

    valid? "[a]{b[c{d]e}fg}"
    c=[, stack=[]
      stack after 'stack << [' = ["["]
    c=a, stack=["["]
    c=], stack=["["]
      stack.pop ([)==CLOSE_TO_OPEN[]] ([)=>true, so continue
    c={, stack=[]
      stack after 'stack << {' = ["{"]
    c=b, stack=["{"]
    c=[, stack=["{"]
      stack after 'stack << [' = ["{", "["]
    c=c, stack=["{", "["]
    c={, stack=["{", "["]
      stack after 'stack << {' = ["{", "[", "{"]
    c=d, stack=["{", "[", "{"]
    c=], stack=["{", "[", "{"]
      stack.pop ({)==CLOSE_TO_OPEN[]] ([)=>false, so return false
      #=> false