поиск строк по шаблону из символов "?" и "*"

[chestr]

Здравствуйте. Прошу помощи в написании алгоритма, он по учёбе нужен, но у меня возникли проблемы, сам уж точно не справлюсь. вот. помогите чем сможете. Постановка задачи :

Пользователь вводит шаблон, включающий в себя символы "?" и "*". Найти в файле все строки, соответствующиешаблону и вывести на экран. (причём ещё и на русском языке нужно что б читала)

Я кое-что пробовал, но у меня не очень вышло. Если есть варианты Вашей программы, напишите, или исправьте мою. Желательно с пояснениями. З.Ы: Спасибо.

[chestr]

вот программа:

Код:

#include <iostream.h>
#include <stdio.h>

char fname[]="имя файла";

bool cmpchr(char z,char p) 
 if (p=='?'||z==p) return true;
 return false;
}

bool cmpstr(char *q, char *k) 
{
 if (*q=='\0'||*k=='\0') return false;
 while(true)
 {
  if (cmpchr(*q,*k))
  {
  q++; k++;
  } else break; 
  if (*q=='\0') return (*k=='\0');
 }
 if (*k!='*') return false;
 else
 {
  while(*k=='*') k++;
  if (*k=='\0') return true;
  char *w=q;
  bool ok=false;
  while(*w!='\0') 
  {
   ok=cmpstr(w,k);
   if (ok) break;
   w++;
  }
  return ok;
 }
}

void norm(char s) 
{
 while(s!='\0')
 {
  if (s=='?'&&*(s+1)=='*') s='*';
  if (s=='?'&&*(s-1)=='*') s='*';
  s++;
 }
}

int main()
{
 char x[500],y[2049],*i,*j,t;
 FILE *fl;
 if ((fl=fopen(fname,"r"))==NULL)
 {
  cout<<"error";
  return(0);
 }
 gets(x);
 norm(x);
 while(!feof(fl)) 
 {
  fgets(y,2048,fl);
  for(i=y;*i!='\0';i++) 
   for(j=i;*j!='\0';j++)
   {
    t=*j;
    *j='\0';
    if (cmpstr(i,x)) cout<<i<<endl;
    *j=t;
   }
 }
 fclose(fl);
 return 0;
}

[Sands]

chestr, А идеи хоть какие-нибудь в плане построения алгоритма есть?
Ну, тоесть, если ты писал приведенную выше програму, то на какую-то последовательность действий ты все-таки ориентировался. Может опишеш словами?
ЗЫ Приведенная программа, ИМХО, даже не скомпилится.

[chestr]

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

[Sands]

chestr, Ну что тебе сказать, здравая мысль в программе есть, однако реализация маненько шалит. Там столько раз скачут с указателей на символы, что лично мне страшно.
А относительно разбирать алгоритм по запутанной программе - так ето стоит делать только в крайних случаях. А вообще делается наоборот. Сначала алгоритм - потом реализация. Если реализация будет не твоя, то желательно еще и обильные коментарии в коде.
А теперь отвлечемся маненько.
Ты себе смысл задания представляеш хотя бы в общих чертах?

[chestr]

ничего подобного я ещё не делал, и лекций у нас не было таких.. так что у меня все представления основаны на том, что я вычитал в нете, и в книге о шаблонах... .

[Sands]

А вот книга о шаблонах(если имеются ввиду шаблоны, которые в С++ начинаются с template) это ты зря, тут шаблон - ето некоторое обобщенное понятие, синонимом которого является "образец", тоесть "шаблон строки" ето то же самое, что и "образец строки".
Наводящий вопрос:
Ты когда нибудь искал у себя на компе файлы, точное имя которых ты не помнил? Если да, то как ты задавал имя этого файла?

[chestr]

хм... естесственно искал.. задавал первыми буквами слова. ключевыми буквами

[Sands]

Идейно, но ето Виндовс тебя разбаловала, потому что она сама по твои мервым 2 буквам могла искать названия файлов, в которых ети буквы были и в конце и посредине. В ДОС-е таких вольностей не было, там все было менее лояльно, что просиш, то и дадут - причем имено так как поймет твой запрос система, а не так как ты думаеш он должен работать ))
Ладно, поставим вопрос по другому:
Понимаеш ли ты, что в шаблоне строки означают символы "?" и "*"?

[chestr]

Насколько я знаю, "*" - это соответствует 0 или более вхождений предшествующего выражения. например "до*" - соответствует "д" и "дом"
"?" - Соответствует 0 или 1 предшествующих выражений. Например, "мыш(ка)?"  - "мыш" и "мышка"
но как это всё впихнуть в код, я даже не представляю...

[Sands]

Ну ето не совсем так
"*" - ето 0 и больше символов вообще, тоесть шаблону "до*" будет соответствовать "до", "дом", "док", "долина" и так далее до бесконечности
"?" - ето 0 или 1 любой символ, тоесть шаблону "?ост" будут соответствовать "ост", "мост", "пост", "Ыост"(слова такого в словаре нету, но ето не лишает права на существование подобную комбинацию букв)

(по крайней мере такие соответствия прочно укоренились в моем мозгу. Если есть другие, то с радостью почитаю)

Теперь появились какие-то мысли в плане шагов для поиска строк по шаблону?
Если нет, поставь себя на место программы. Как бы ты совершал поиск строк в тексте, если бы тебе дали некоторый шаблон?

[chestr]

так... тогда я должен, основываясь на шаблоне (из скольки букв состоит, каких и тп.) задать код , состоящий из некоторых букв (шаблона) и * с ? вроде бы так. далее, через условный оператор надо делать проверку "похожести" на шаблон до конца файла , потом всё вывести на экран

[Вад]

chestr, задача учебная? Если да, то что уже знаешь/проходил, и в рамках какой дисциплины решаешь задачу? От этого зависит, какими словами тебе будут объяснять непонятое, и будут ли (может, ты уже всё должен знать )

Значит, так. Шаблон у тебя содержит, если грубо, "обычные слова" и спецсимволы. "Обычные слова" - это обязательные части, всё, кроме символов '*' и '?'. Следовательно, тебе нужно разбить шаблон на составные части и двигаться последовательно по проверяемой на соответствие шаблону строке. При этом для простых слов у тебя будет элементарная проверка на соответствие, а вот для спецсимволов нужно будет рассматривать каждый вариант от "0 символов" до "N любых символов" (для '?' N = 1, а вот для '*' N - любое).

[chestr]

вообще говоря, дисциплина "основы алгоритмизации и программирования", 1-й курс, курсач. на лекции не было этого на 100%, покупать не хочу, надо самому разбираться. вот. если будешь объяснять, попробуй по-понятнее) (благодарю за помощь)
пока всё понятно.. дай пример, может, какой-нить..

[Вад]

Ага. Первый курс, значит "конечные автоматы" и "регулярные выражения" - наверное, ещё пустой звук. А как насчёт рекурсии, умеешь делать? По-моему, задача обработки спецсимволов в самом простом варианте - рекурсивная. Да и в твоём примере - тоже так решается.

[chestr]

был бы просто в восторге если бы объяснил эту штуку "рекурсию" ))

[Вад]

Рекурсивный вызов функции - это вызов функции из неё самой.  В твоём примере так делает функция cmpstr. Ничего сложного. Пишется функция, которая выполняет один шаг алгоритма и затем новый шаг выполняется посредством рекурсивного вызова. Странно, что с этим понятием ты не знаком, хотя пример у тебя писал человек, с рекурсией знакомый

[RXL]

chestr, тебе надо много читать...

О рекурсии:
https://club.shelek.ru/viewart.php?id=184
https://club.shelek.ru/viewart.php?id=205
https://club.shelek.ru/viewart.php?id=220
https://club.shelek.ru/viewart.php?id=226

Вообще полезно почитать:
https://club.shelek.ru/view.php?id=25

Может заинтересует - уроки для новичков:
https://club.shelek.ru/view.php?id=3

[chestr]

спасибо за ссылки, сейчас буду изучать)

[chestr]

#include <iostream.h>
#include <stdio.h>

char fname[]="имя файла";

bool cmpchr(char z,char p)
{
if (p=='?'||z==p) return true;
return false;
}

bool cmpstr(char *q, char *k)
{
if (*q=='\0'||*k=='\0') return false;
while(true)
{
if (cmpchr(*q,*k))
{
q++; k++;
} else break;
if (*q=='\0') return (*k=='\0');
}
if (*k!='*') return false;
else
{
while(*k=='*') k++;
if (*k=='\0') return true;
char *w=q;
bool ok=false;
while(*w!='\0')
{
ok=cmpstr(w,k);
if (ok) break;
w++;
}
return ok;
}
}

void norm(char s)
{
while(s!='\0')
{
if (s=='?'&& ((s+1))=='*') s='*';
if (s=='?'&& ((s-1))=='*') s='*';
s++;
}
}

int main()
{
char x[500],y[2049],*i,*j,t;
FILE *fl;
if ((fl=fopen(fname,"r"))==NULL)
{
cout<<"error";
return(0);
}
gets(x);
//norm(x);
while(!feof(fl))
{
fgets(y,2048,fl);
for(i=y;*i!='\0';i++)
for(j=i;*j!='\0';j++)
{
t=*j;
*j='\0';
if (cmpstr(i,x)) cout<<i<<endl;
*j=t;
}
}
fclose(fl);
return 0;
}

[chestr]

ну а щас.

[RXL]

chestr, когда пишешь сообщение, оборачивай код этим тегом: [code]  [/code].

[Sands]

chestr, Извини за нескромный вопрос, но ты сам-то приведенную программу компилировал? Запускал на выполнение? От того, что ты закоментировал функцию нормализации шаблона суть программы не особо поменялась.
И, кстати, каковы твои познания в плане работы со строками и работы с файлами? А также в плане понимания чужого кода ))