Страницы

Поиск по вопросам

среда, 17 октября 2018 г.

Алгоритм для преобразования диапазона номеров в регулярное выражение

Не знаю, насколько правильно выглядит сам заголовок, но подробнее опишу здесь.
Итак, суть такова: есть, к примеру, некий диапазон и пара условий:
$start и $end всегда имеют одинаковую символьную длину (хотя это и не столь важно); И если есть диапазон, включающий в себя элемент 555123456 (длина 9 символов), то нет никакого другого диапазона, который включал бы в себя номер, превосходящий по длине уже имеющийся и начинающийся с 555 - т.е. номер 5551234567 (длина - 10 символов) не существует по определению. Последние цифры в $start и $end равняются 0 и 9 соответственно, что тоже облегчает задачу.
Т.е. (здесь и далее пишу условно, без привязки к каким-либо языку программирования или стандарту regexp)
555000000 - 555999999 // Т.е. 555* 666000000 - 666999999 // Т.е. 666*
5550000000 - 5559999999 // Не существует в списке диапазонов по определению задачи, игнорируем. 6660000000 - 6669999999 // Не существует в списке диапазонов по определению задачи, игнорируем.

Иными словами: если задан 555000000 - 555999999, то нет 5550000000 - 5559999999
Возьмем, например
555000000 - 555999999
Задача: преобразовать в 555*. С указанным примером разобраться несложно - необходимо отнять $start от $end, чтобы получить некую переменную $result, которая равна 999999. Затем использовать значение результата операции $result.length() по отношению к, скажем, $start, чтобы получить строку 555*
$shortrec = substr($start,0,-strlen($result)) . "*";
Но если диапазон выглядит как
777120000 - 777259999
то разница будет иметь значение 139999. Здесь сложнее, но тоже понятно - помимо отчасти указанного выше, сравниваем позиции 0 и 9 в обеих переменных, "выходим" на 12 и дополнительно обрабатываем 12, наращивая его 13 раз и получая в цикле следующую последовательность:
77712* 77713* 77714* ... 77725*
Но как быть, если есть диапазон,
888125120 - 888959599
(здесь вспомним облегчающее логику условие номер 3, чтобы не оперировать выражением типа [5-9], если бы $start равнялся бы 888125125) для которого необходимо получить
88812512* 8882* 8883* ... 8888*
88890* 88891* 88892* ... 88894*
888950* 888951* 888952* ... 888958*
8889590* 8889591* 8889592* ... 8889595*

Прошу рассудить - следую ли я с самого начала правильной логике или нет? И есть ли некоторое универсальное решение (алгоритм) для подобных задач? Как поступили бы вы?
P.S. Язык программирования не важен - важен сам подход и алгоритм. Надеюсь, не сломал читающему мозг, но задача не из учебных, а самая что ни на есть настоящая. Так что если есть идеи, буду весьма признателен.


Ответ

Писать алгоритм генерации будем для частного случая - когда число знаков у нижней и верхней границы одинаковы. Если же число знаков разное, то исходный диапазон будет разбит на 3 диапазона:
от минимальной границы до максимального числа с таким же числом цифр все полные диапазоны чисел, которые не были затронуты границами от минимального числа с таким же числом цифр, как у максимальной границы, до максимальной границы
На примере понятнее, что все это обозначает. Исходный диапазон 14-123456 разбиваем на три диапазона 14-99, 100-99999, 100000-123456 Если присутствует второй диапазон, то он задается простым выражением \d{n,m}, первый и второй диапазон нужно генерировать отдельно и в границах этих диапазонов всегда одинаковое количество знаков, а значит применим основной алгоритм генерации, а затем объединим эти 3 диапазона альтернативой.
Основной алгоритм для диапазонов с одинаковым количеством цифр
Попытаемся найти общую часть для верхней и нижней границы. Например в диапазоне 1234-1278 можно вынести 12 как обычные символы. Начнем просмотр границ слева-направо. Для примера диапазон 1234-5678 Первые цифры нижней и верхней границ 1 и 5, поэтому разделим на 3 диапазона: 1234-1999, 2000-4999, 5000-5678, то есть как бы выделим середину, которую можно представить как [2-4]\d{3} Оставшиеся два диапазона обработаем по тому же самому алгоритму. Например для 1234-1999 сперва вынесем цифру 1 как общую. Диапазон 234-999 разобьем на 2 диапазона 234-299, 300-999 И так далее для всех диапазонов, которые появятся в ходе разбиения на составные диапазоны.
Кода безумно много, но зато можно запустить и потестировать.
$( document ).ready( function() { $( "#rangeLeft, #rangeRight" ).keydown( function() { clearDisplay(); } ); $( "#run" ).click( function() { clearDisplay(); var rangeLeft = $( "#rangeLeft" ).val(); var rangeRight = $( "#rangeRight" ).val(); if ( ! checkRanges( rangeLeft, rangeRight ) ) return; $( "#result" ).append( generateFullRegExp(rangeLeft, rangeRight)+"
" ); $( "#test" ).show(); } ); $( "#test" ).click( function() { var rangeLeft = $( "#rangeLeft" ).val(); var rangeRight = $( "#rangeRight" ).val(); var re = new RegExp( "^"+generateFullRegExp(rangeLeft, rangeRight)+"$" ); for( var i=Math.pow( 10, rangeLeft.length-1 ); iparseInt(rangeRight) ) ) $( "#result" ).append( "Тест провален на: " + i+"
" ); if ( !re.test( i+"" ) && ( i>parseInt(rangeLeft) && i" ); }; $( "#result" ).append( "Тест пройден от "+Math.pow( 10, rangeLeft.length-1 )+" до "+i+"
" ); } ); } ); function checkRanges( rangeLeft, rangeRight ) { if ( /\D/.test( rangeLeft ) || /\D/.test( rangeRight ) ) { $( "#result" ).append( "Введите два числа
" ); return false; }; rangeLeft = parseInt( rangeLeft ); rangeRight = parseInt( rangeRight ); if ( isNaN( rangeLeft ) || isNaN( rangeRight ) ) $( "#result" ).append( "Не указаны границы диапазонов
" ); if ( rangeLeft < 0 ) $( "#result" ).append( "Левая граница меньше 0
" ); if ( rangeRight < 0 ) $( "#result" ).append( "Правая граница меньше 0
" ); if ( rangeLeft > rangeRight ) $( "#result" ).append( "Левая граница больше правой границы
" ); return( !( rangeLeft < 0 || rangeRight < 0 || rangeLeft > rangeRight || isNaN( rangeLeft ) || isNaN( rangeRight ) ) ); }; function maxBeginStr( str1, str2 ) { var res = /^(.*)[^-]*\-\1/.exec( str1 + "-" + str2 ); return res ? res[1] : ""; }; function midDiap( start, end ){ var st0int = parseInt( start[0] ); var en0int = parseInt( end[0] ); if ( st0int+1 == en0int ) { var res = end[0]; } else { if ( st0int == en0int-2 ) { res=( st0int+1 )+""; } else { res="["+( st0int+1 )+"-"+(en0int-1)+"]"; }; }; if ( start.length == 1 ) return res; return res+"\\d{"+(start.length-1)+"}"; }; function lowDiap( num, pos ) { var res = num.substr(0, pos); var highRange = parseInt( num[pos] )-1; if ( highRange == -1 && pos == num.length-1 ) return num; if ( highRange == -1 ) return null; // выражение можно не включать if ( pos == num.length-1 ) highRange++; res += "[0-"+highRange+"]"; if ( num.length != pos+1 ){ res += "\\d{"+(num.length-pos-1)+"}"; } return res; }; function highDiap( num, pos ) { var res = num.substr(0, pos); var lowRange = parseInt( num[pos] )+1; if ( lowRange==10 && pos == num.length-1 ) return num; if ( lowRange==10 ) return null; // выражение можно не включать if ( pos == num.length-1 ) lowRange--; res += "["+lowRange+"-9]"; if ( num.length != pos+1 ){ res += "\\d{"+( num.length -pos-1)+"}"; } return res; }; function getRegExp( start, end ) { if ( start.length != end.length ) return "Invalid input"; var res= maxBeginStr( start, end ); start= start.substr( res.length ); end = end.substr( res.length ); if ( start.length == 0 ) return res; var st0int = parseInt( start[0] ); var en0int = parseInt( end[0] ); var resArr= Array(); if ( start.length > 1 ) { if ( st0int != en0int-1 ) { resArr.push( midDiap( start, end) ); } for ( var i=1; i 1 ) resArr.push( ("\\d{"+(rangeLeft.length+1)+","+(rangeRight.length-1)+"}").replace(/(\d+),\1/, "$1") ); resArr.push( getRegExp( "1"+"0".repeat( rangeRight.length-1 ), rangeRight ) ); return "(?:"+resArr.join("|")+")"; }; function clearDisplay() { $( "#result" ).html( "" ); $( "#test" ).hide(); }; #test { display:none } -


    
  



Существующий недочет Для диапазона 10-29 и.т.п. сгенерируется избыточное выражение (?:2[0-9]|1[0-9])

Комментариев нет:

Отправить комментарий