February 5th, 2012

Регексп делимости на 3

Написать сабж предлагается уважаемым читателям. Чуть более конкретно: он должен матчить любое десятичное целое неотрицательное число, нацело делящееся на 3.

UPD: Поздравления достаются art_mixer! Очевидно, сумма цифр должна быть кратна 3, значит, можно вместо каждой цифры рассматривать ее остаток от деления на 3, а само число состоит из 1 или больше кусков, которые делятся на 3, причем нули несущественны. Рассмотрим дерево префиксов и обнаружим, что оно «заканчивается» на 111, 12, 21, 222, а все остальные «концы» имеют вид 1(12)+2, 1(12)+11, 2(21)+1, 2(21)+22. Объединяем это все вместе и получаем:
(
1(12)*(2|11)|
2(21)*(1|22)
)+

Затем добавляем 0 везде внутри масок и как отдельную сумму:
(
0|
10*(10*20*)*(2|10*1)|
20*(20*10*)*(1|20*2)
)+

Осталось заменить 0 на [0369], 1 на [147], 2 на [258] и мы получим ответ.