Regex, чтобы найти непревзойденные скобки

Question

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

Здесь существует вопрос о stackoverflow, но я не нашел решения на основе регулярных выражений, которое работает.

Я придумал регулярное выражение, которое находит непревзойденные открытые скобки \((?![^)]+\)), используя отрицательную перспективу, но я не могу понять, какая противоположность требуется для непревзойденных закрывающих скобок.

EDIT : приведенное выше регулярное выражение для поиска несоответствующих открытых фигурных скобок не работает должным образом. Например. он пропустит случаи, когда за несколькими открытыми скобками следует одна закрывающая скобка (см. также комментарии)

Вот моя тестовая строка, с которой я экспериментировал на Rubular:

one) ((two) (three) four) (five)))

Обратите внимание, что строка может содержать символы любого типа, включая кавычки, тире и т. Д.

Answer 1

Короткий ответ: вы не можете найти несоответствующие скобки с регулярными выражениями. Регулярные выражения кодируют обычные языки , в то время как языком всех правильно подобранных скобок является контекстно-свободный язык .

Answer 2

Вот решение на основе регулярных выражений:)

def balanced?( str, open='(', close=')' )
  re = Regexp.new( "[\\#{open}\\#{close}]" )
  str.scan(re).inject(0) do |lv,c|
    break :overclosed if lv < 0
    lv + (c==open ? 1 : -1)
  end == 0
end

s1 = "one) ((two) (three) four) (five)))"
s2 = "((one) ((two) (three) four) (five))"
s3 = "((one) ((two) (three) four) (five)"

puts balanced?(s1), #=> false
     balanced?(s2), #=> true
     balanced?(s3)  #=> false

Answer 3

Библиотека Ruby Oniguruma может анализировать грамматики LALR (n), включая HTML. Ссылаясь на README :

  r = Regexp.compile(<<'__REGEXP__'.strip, Regexp::EXTENDED)
  (?<element> \g<stag> \g<content>* \g<etag> ){0}
  (?<stag> < \g<name> \s* > ){0}
  (?<name> [a-zA-Z_:]+ ){0}
  (?<content> [^<&]+ (\g<element> | [^<&]+)* ){0}
  (?<etag> </ \k<name+1> >){0}
  \g<element>
  __REGEXP__

  p r.match('<foo>f<bar>bbb</bar>f</foo>').captures

Приведенный выше код, конечно, намного проще, чем настоящий анализатор HTML, но он соответствует вложенным тегам. Кроме того, вы должны заметить, что создать регулярное выражение, которое будет очень медленным (в диапазоне минут для анализа строки из 80 символов), невероятно просто.

Для этой задачи лучше использовать настоящий парсер, такой как Treetop .