Регулярное выражение, проверяющее, что перед каждым символом 'a' в строке находится чётное число символов

Question

[leshik]

Опубликовали скрининговый опрос на вакансию J2EE программиста. Правильных ответов на вопрос про регулярное выражение — ноль из четырёхсот. Почему так мало?

Comments

[Shedal]

Автор, пометьте ответ susl как решение.

[leshik]

Вопрос был: почему так мало Java программистов могут написать регулряное выражение? :-)

Answer 1

[susl]

для простоты, предположим что алфавит у нас из 2х символом a и b (в «настоящих» регулярках это b есть «все кроме a»), тогда (ab | bb)*(a|b|epsilon) есть решение (я использую классическое определение регулярного выражения)
что любое слово из определения входит в наш язык и наоборот любое слово в нашем языке подходит под определение, доказать можно просто по (сильной) индукции по длине слова (в шаге индукции нужно лишь рассматривать отдельно случаи четной и нечетной длины)
на языке «программистских» регулярок получится что-то типа /^((a|[^a])[^a])*(a|[^a])?$/
ну или если упростить («а | [^a]» есть любой символ, т.е. просто "."), то /^(.[^a])*.?$/

на самом деле в таких «заковыристых» случаях вернее всего нарисовать автомат и сконвертить его в регулярку.
на автомате еще и проще доказать будет :)
надеюсь не ошибся нигде ;)

Comments

[Shedal]

Круто! Все гениальное просто :)

[runcore]

ваша регулярка сработает даже если в строке вообще нет символа 'a', что противоречит поставленой задаче

[susl]

en.wikipedia.org/wiki/Vacuous_truth

[runcore]

регулярка какбе говорит нам что нашла: четное кол-во символов перед несуществующим в строке символом 'a'. мне это поведение не кажется логичным)

[susl]

как раз с точки зрения логики моя интерпретация верная :) по ссылоке есть более наглядные примеры про телефоны.
если формально, то мы попадаем под этот случай:
" где A — пустое множество" — истина.
это выражение есть истина, по сути, по тому же почему и пустое произведение равно единице

[tvv]

Отличное, верное решение. Немного улучшим его с точки зрения производительности: ^(?:.[^a])*.?$

Answer 2

[afiskon]

>> у вас, например, bbabba пройдет, но перед вторым a 5 символов
Ну значит я 401-ый :) Вторая попытка:
/^(([^a]{2})*a([^a]([^a]{2})*a)*)?[^a]*$/

Answer 3

[Homakov]

^([^a][^a])*a([^a]([^a][^a])*a)*[^a]*$

сначала четное потом в промежутках нечетные должны лежатжь

Comments

[susl]

пустая строка тоже должна подходить, у вас нет. а так все верно :)

Answer 4

[afiskon]

Мой вариант: /^(([^a]{2})*a)*[^a]*$/

Comments

[Hint]

Неправильно.
xa — false
xxa — true

[susl]

у вас, например, bbabba пройдет, но перед вторым a 5 символов :)

Answer 5

[Hint]

Толи я устал, толи вопрос сформулирован неудачно, но после первого прочтения задачу понял неправильно.
/^.(..)*a/

Comments

[Homakov]

^(..)*a

Answer 6

[herfleisch]

Не очень понял вопроса, поэтому сделал на свой лад:

$source = "h4aidfsadfr";
$res = ereg_replace("(.{2}){1,}a", "", $source);
echo "$source\n";
echo "$res\n";

Comments

[herfleisch]

Смысл регулярки таков:

(.{2}) — пара символов.
(.{2}){1,} — пары символов, которых может быть сколь угодно много
(.{2}){1,}a — пары символов, которых может быть сколь угодно много, после которых идёт символ «a».

[afiskon]

Видно, что не поняли. Я сначала вообще подумал о чем-то вроде «перед каждым A должно быть записано четное число». Сразу в голове возникли всякие (0|2|4|6|8) и тп :)

[herfleisch]

Нет, по-моему всё сходится. Мне кажется что я правильно выполнил задание.

[herfleisch]

P.S. у меня в решении — PHP.

[Shedal]

У вас перед второй «a» во всей строке, что находится перед ней, — нечетное количество символов. Посмотрите на решение , он там хорошо описал. Основной смысл в том, что каждое «a» должно стоять на нечетной позиции в строке.

[Shedal]

*посмотрите на решение susl.

[herfleisch]

Что-то мне подсказывает что если ставить «a» на нечётные позиции, то между ними всегда будет нечётное количество символов.

[susl]

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

[herfleisch]

Тогда моё решение + жадина.

Answer 7

[AGK]

для перехода на прохождение интервью достаточно вставить после цикла for

window.open('https://spreadsheets.google.com/spreadsheet/embeddedform?formkey=' + key);


function check_re() {
var tests = ['a', 'b', 'aa', 'ba', 'babab', 'babdca', 'bba', 'baa', 'bacadaeafagaeahija']
var results = [0, 1, 0, 1, 1, 1, 0, 0, 1]

var re = new RegExp(document.getElementById('re').value)
var x = 0

var str = ''
var key = 'CUGlkM0NJcGVEdE5HOC0tNGc6MQdG94ay1'
for (var i = 0; i < tests.length; i++) {
if ((re.test(tests[i]) && true) != results[i]) {
str += ' ' + tests[i]
}
key = key.substr(3) + key.substr(0, 3);

}
window.open('https://spreadsheets.google.com/spreadsheet/embeddedform?formkey=' + key);
if (str == '') {
alert("Поздравляю!")
window.open('https://spreadsheets.google.com/spreadsheet/embeddedform?formkey=' + key)
} else {
document.getElementById('result').innerHTML = 'Ошибка для' + str + '.'
}
}


Comments

[leshik]

спасибо!

[AGK]

leshik, не за что)

Answer 8

[tvv]

^(?:(?:..)*[^a]a)*[^a]*$

Comments

[tvv]

Прошу прощения, это я привел вариант для нечётного числа символов перед каждым 'a'.

[tvv]

Верное решение привел выше susl. Вот немного улучшенный вариант его решения: ^(?:.[^a])*.?$

Хотя этот вариант менее универсальный, так как меньше диалектов регекспов поддерживают такие конструкции, но будет работать быстрее, и будет использовать меньше памяти.

[tvv]

Вот улучшенный вариант для НЕчётного числа символов перед 'a': ^(?:[^a].)*[^a]?$