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

Question

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

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

и т.д.

Answer 1

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

Самый простой шаблон для сопоставления сбалансированных паренов - \((?:[^()]*+|(?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;

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

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

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

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

Answer 2

Если вы застряли на языке, синтаксис которого регулярного выражения не поддерживает рекурсивное сопоставление, я дам вам простую реализацию 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/

Answer 3

Такая вложенная структура не может быть эффективно обработана регулярными выражениями. Что вам нужно, это грамматика и парсер для этой грамматики. В вашем случае грамматика достаточно проста. Если вы используете 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))" )

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

Answer 4

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