Дополнительные функции сопоставления строк - PullRequest
Новая
       4

Дополнительные функции сопоставления строк

0 голосов
/ 24 января 2010

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

Как aaaaabbbbb или ababababab или aabbaabbab.

Я полагаю, что для детерминистского механизма потребуется полиномиальное время.

Существуют ли другие подходящие языки, которые позволили бы такое сопоставление?

Обновление

Я хотел использовать тип выражения для поиска, поэтому я поменял одно предназначение на (?=b*ab*){5}(?=a*ba*){5}([ab]{10}), и оно прекрасно работает! :) Я все еще не уверен в отношении такого выражения. Но я полагаю, что могу просто посмотреть на выражения предвкушения.

Мне по-прежнему любопытно, какие существуют другие типы шаблонов, которые легко объяснить, но которые трудно переформулировать?

Ответы [ 2 ]

6 голосов
/ 24 января 2010

У меня есть все эти винты. Чтобы вбить их в этот кусок дерева, я должен использовать коготь или шариковый молоток?

Это (примерно) то, что задает твой вопрос. То, что вы должны сделать, это просто перебирать каждый символ строки. Я могу сделать это на C. Смотреть: 

int validate(char *s)
{
    int a = 0, a = 0;
    while(*s)
      {
        switch(*s++)
        {
        case 'a':
            a++;
            break;
        case 'b':
            b++;
            break;
        }
      }
    return a == 5 && b == 5;
}

Это оставлено вам в качестве упражнения: а) преобразовать это на ваш язык по выбору, б) изменить, чтобы оно соответствовало только последовательным последовательностям «а» и «б» (если вам нравится) или настроить его под ваши другие конкретные требования .

Суть в том, что есть гораздо лучшие инструменты для этой работы, чем регулярное выражение, поэтому, если "a" и "b" не являются заменой для более сложных регулярных выражений, не используйте для этого регулярные выражения. И даже если «a» и «b» действительно более сложные регулярные выражения, вам не нужно решать все проблемы с One Regex To Rule All All. Вы можете смешать несколько полезных регулярных выражений и цикл кода (например, выше), чтобы получить гораздо больший эффект, чем огромный (и не поддерживаемый) Regex-zilla.

5 голосов
/ 24 января 2010

Вы можете использовать прогнозные утверждения : 

^(?=(?:[^a]*a){5}[^a]*$)(?=(?:[^b]*b){5}[^b]*$)
...