|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Не знаю, что меня заставило сесть и написать пару слов на эту тему. Возможно, это очередной эксперимент, результаты которого я смогу дальше использовать в своем софте.
Когда-то мне нужно было добавить поддержку этих самых масок в собственноручно написанную процедуру поиска файлов на диске. Но ничего не вышло. И вот сейчас, когда прошло более 3х лет, понимание принципа работы пришло само собой. Теперь своей задачей я вижу передать то знание, которое открылось мне и идти вперед, за новым знанием.
Естественно, самый удобный процесс обучения строится по принципу "от простого - к сложному". Им мы и воспользуемся.
"?" заменяет один (любой) символ, может также и не обозначать ничего.
Т.е. по запросу 12?.pas можно получит как 123.pas, так и 12.pas. Теперь можно начинать ваять саму подпрограммку. Для простоты за базовый язык возьмем Pascal (но на C/C++ перевести тоже особого труда не составит).
Выходит, что нам нужно рассмотреть 2 варианта: когда знак вопроса заменяет конкретный символ строки и когда его просто нужно проигнорировать. Отсюда и следующий код:
function IsWildcardExpandable(mask:string;in_str:string):boolean;
//Нам же нужна стартовая функция...
var IsOk:boolean;
begin
IsOk:=false;
IsOk:=_iswildcardexpandable(mask,in_str);
//Вот и первая спичка, которая будет причиной пожара
Result:=IsOk;
end;
function _iswildcardexpandable(var mask:string;in_str:string):boolean;
//Непосредственно, сама рекуррентная функция
var Res1,Res2,IsSymbol,IsOk:boolean;
i:integer;
s:string;
begin
Res1:=false;
Res2:=false;
IsSymbol:=false;
IsOk:=true;
for i:=1 to max(length(mask),length(in_str)) do
begin
//Если совпадение произойдет, то цель достигнута
if (mask[i]<>in_str[i]) then
begin
IsOk:=false;
if mask[i]='?' then IsSymbol:=true;
break;
end;
end;
if IsOk then Result:=true
else begin
if IsSymbol then
begin
if mask[i]='?' then
begin
Res1:=_iswildcardexpandable(copy(mask,1,i-1)+copy(mask,i+1,length(mask)-i-1),instr);
if not Res1 then Res2:=_iswildcardexpandable(copy(mask,1,i-1)+in_str[i]+copy(mask,i+1,
length(mask)-i-1),instr);
//Ну если совпало, то зачем переливать из пустого в порожнее???
Result:=Res1 or Res2;
end;
//Тут можно описать и остальные символы маски
end;
if not IsSymbol then Result:=false;
//А тут не совпали символы... Не та строчка...
end;
end;
Не спорю, что этот код можно (и нужно) оптимизировать. Пусть это будет твоим домашним заданием. Бояться не стоит, оценки я ставить не буду, проверять его наличие тоже. Но если появятся интересные варианты, обязательно о них расскажу. А может, присланные решения вдохновят меня на новые подвиги...
А вот "звездочка" вносит в наш код некоторые коррективы...
"*" заменяет группу (любую) символов, может также и не обозначать ничего.
Здесь специфика несколько иная, т.к. может быть заменена любая группа символов. Может возникнуть очень неприятная ситуация с использованием некоторых комбинаций спецсимволов. Будем считать комбинации "*?" и "**" запрещенными, ведь вместо них можно использовать просто "*".
...
s:=in_str;
while pos(mask[i+1],s)<>0 do
begin
if (i=length(mask)) or (Res1) then
begin
Result:=true;
break;
end;
Res2:=_iswildcardexpandable(copy(in_str,1,length(in_str)-length(s)+1)+copy(mask,i+1,length(mask)-i-1),in_str);
s:=copy(s,pos(mask[i],s)+1,length(s)-pos(mask[i],s)-1);
Res1:=Res1 or Res2;
end;
...
Значит, для обработки обоих спецсимволов служебная функция _iswildcardexpandable будет выглядеть так:
function _iswildcardexpandable(var mask:string;in_str:string);
//Непосредственно, сама рекуррентная функция
var Res1,Res2,IsSymbol,IsOk:boolean;
i:integer;
s:string;
begin
Res1:=false;
Res2:=false;
IsSymbol:=false;
IsOk:=true;
for i:=1 to max(length(mask),length(in_str)) do
begin
//Если совпадение произойдет, то цель достигнута
if (mask[i]<>in_str[i]) then
begin
IsOk:=false;
if mask[i]='?' then IsSymbol:=true;
if mask[i]='*' then IsSymbol:=true;
break;
end;
end;
if IsOk then Result:=true
else begin
if IsSymbol then
begin
if mask[i]='?' then
begin
Res1:=_iswildcardexpandable(copy(mask,1,i-1)+copy(mask,i+1,length(mask)-i-1),instr);
if not Res1 then Res2:=_iswildcardexpandable(copy(mask,1,i-1)+in_str[i]+copy(mask,i+1,
length(mask)-i-1),instr);
//Ну если совпало, то зачем переливать из пустого в порожнее???
Result:=Res1 or Res2;
end;
if mask[i]='*' then
begin
s:=in_str;
while pos(mask[i+1],s)<>0 do
begin
if (i=length(mask)) or (Res1) then
begin
Result:=true;
break;
end;
Res2:=_iswildcardexpandable(copy(in_str,1,length(in_str)-length(s)+1)+copy(mask,i+1,
length(mask)-i-1),in_str);
s:=copy(s,pos(mask[i],s)+1,length(s)-pos(mask[i],s)-1);
Res1:=Res1 or Res2;
end;
end;
//Тут можно описать и остальные символы маски
end;
if not IsSymbol then Result:=false;
//А тут не совпали символы... Не та строчка...
end;
end;
Вот и все премудрости. На самом деле, подводных камней тут куда больше, чем я показал, но выход всегда есть: запретить одни комбинации, автоматически заменять их на другие.
Удачи.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
