Как проверить правильность скобок в неправильном порядке

Question

Мне нужно написать метод, который принимает строку и возвращает true, если скобки не пусты, скобки и фигурные скобки закрываются правильно. В противном случае возвращается false.

Вот что у меня есть:

  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

Я думаю, что мой valid_string? метод не совсем SOLID, но самое главное, он не проходит тест, когда скобки расположены в неправильном порядке, как )somebrackets(. Не могли бы вы посоветовать, как это исправить?

Answer 1

Вот очень эффективная версия. Он использует регулярные выражения и вытягивает все ваши фигурные скобки ({}[]()) в небольшой массив, а затем продолжает перебирать пары, пока ничего не останется. Когда он находит несопоставленную пару, он завершает работу и возвращает false. Он также не разбивает строку на массив символов, так как он будет использовать в два раза больше памяти (один раз для всей строки и еще раз для строки, разделенной на отдельные символы).

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

Этот код вернет true, если фигурных скобок нет вообще.

Если вам это не нравится, сделайте следующее:

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

В качестве дополнительного примечания вы должны избегать создания массивов в циклах, как вы делали в своем примере:

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

Этот код создаст два массива и 6 строк на символ в вашей переменной string. Это очень неэффективно, и вы будете использовать гораздо больше оперативной памяти и процессора, чем необходимо. Вы хотите, по крайней мере, сделать эти два массива вне цикла, поскольку они не меняются, и в идеале даже сделать их константами, чтобы вы даже не делали их каждый раз, когда вызываете метод. Сделайте их едиными, когда ваша программа загрузится, и используйте их навсегда. Такие мелочи действительно имеют большое значение, особенно при использовании в цикле.

Answer 2

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

Поведение метода можно увидеть, добавив несколько puts операторов.

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

Answer 3

Моя попытка, выдвинув все открывающие скобки в массиве, выдвигая закрывающие, если они совпадают:

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