Соответствие регулярному выражению

Я хочу написать регулярное выражение, которое соответствует чему-либо между

()
(())
(()())
((()))
()()()

и т.п.

Источник

4 ответа

Решение

Все эти ответы, утверждающие, что вы не можете использовать шаблоны для сопоставления строки со сбалансированными вложенными паренами, совершенно неверны. Не практично делать вид, что шаблоны, соответствующие современным языкам программирования, ограничены "обычными языками" в смысле патологического учебника. Как только вы разрешите обратные ссылки, это не так. Это позволяет реальным шаблонам соответствовать гораздо больше, чем версиям учебников, делая их гораздо более практичными.

Самый простой шаблон для сопоставления сбалансированных паренов \((?:[^()]*+|(?0))*\), Но вы никогда не должны писать это, потому что это слишком компактно, чтобы его можно было легко прочитать. Вы всегда должны писать это с/xрежим, чтобы учесть пробелы и комментарии. Так напишите это так:

m{
  \(              # literal open paren
     (?:          # begin alternation group
         [^()]*+  #  match nonparens possessively
       |          # or else
         (?0)     #  recursively match entire pattern
     )*           # repeat alternation group
  \)              # literal close paren
}x

Также есть, что сказать по именам ваших абстракций и отделению их определения и упорядочения от их исполнения. Это приводит к такой вещи:

my $nested_paren_rx = qr{

    (?&nested_parens)

    (?(DEFINE)

        (?<open>       \(       )
        (?<close>       \)      )
        (?<nonparens> [^()]     )

        (?<nested_parens>
            (?&open)
            (?:
                (?&nonparens) *+
              |
                (?&nested_parens)
            ) *
            (?&close)
        )

    )
}x;

Вторая форма теперь поддается включению в более крупные шаблоны.

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

Пока вы занимаетесь этим, убедитесь, что никогда не пишете шаблоны линейного шума. Вам не нужно, и вы не должны. Нельзя поддерживать язык программирования, который запрещает пробелы, комментарии, подпрограммы или буквенно-цифровые идентификаторы. Так что используйте все эти вещи в своих шаблонах.

Конечно, это помогает выбрать правильный язык для такой работы. ☺

Источник

Если вы застряли на языке, синтаксис которого регулярного выражения не поддерживает рекурсивное сопоставление, я дам вам простую реализацию Javascript, из которой вы сможете создать свой собственный на выбранном вами языке:

function testBraces(s) {
    for (var i=0, j=0; i<s.length && j>=0; i++)
        switch(s.charAt(i)) {
            case '(': { j++ ; break; }
            case ')': { j-- ; break; }
        }

    return j == 0;
}

И здесь вы можете поиграть с ним: http://jsfiddle.net/BFsn2/

Источник

Такая вложенная структура не может быть эффективно обработана регулярными выражениями. Что вам нужно, это грамматика и парсер для этой грамматики. В вашем случае грамматика достаточно проста. Если вы используете python, попробуйте pyparsing или funcparserlib.

С pyparsing вы можете сделать следующее:

from pyparsing import nestedExpr
nestedExpr().parseString( "(some (string you) (want) (to) test)" ).asList()

Это вернет список, содержащий проанализированные компоненты вложенной строки. Разделителем по умолчанию для nestedExpr является скобка, поэтому вам не нужно делать ничего лишнего. Если вы хотите использовать funcpasrerlib, вы можете попробовать следующее

from funcparserlib.parser import forward_decl, many, a
bracketed = forward_decl()
bracketed.define(a('(') + many(bracketed) + a(')'))

После этого вы можете позвонить

bracketed.parse( "( (some) ((test) (string) (you) (want)) (to test))" )

и он вернет проанализированные элементы в кортеже.

Источник

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

Источник
Другие вопросы по тегам