Регулярное выражение

Ответ 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;

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

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

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

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

Ответ 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/

Ответ 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))" )

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

Ответ 4

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