Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: поиск строк по шаблону из символов "?" и "*"  (Прочитано 23506 раз)
0 Пользователей и 1 Гость смотрят эту тему.
chestr
Гость
« : 20-05-2008 14:30 » 

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

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

Я кое-что пробовал, но у меня не очень вышло. Если есть варианты Вашей программы, напишите, или исправьте мою. Желательно с пояснениями. З.Ы: Спасибо.
« Последнее редактирование: 06-08-2008 19:08 от Алексей1153++ » Записан
chestr
Гость
« Ответ #1 : 20-05-2008 14:33 » 

вот программа:
Код:
#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;
}
« Последнее редактирование: 06-08-2008 19:10 от Алексей1153++ » Записан
Sands
Помогающий

ua
Offline Offline

« Ответ #2 : 20-05-2008 15:43 » 

chestr, А идеи хоть какие-нибудь в плане построения алгоритма есть?
Ну, тоесть, если ты писал приведенную выше програму, то на какую-то последовательность действий ты все-таки ориентировался. Может опишеш словами?
ЗЫ Приведенная программа, ИМХО, даже не скомпилится.
Записан
chestr
Гость
« Ответ #3 : 20-05-2008 15:46 » new

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

ua
Offline Offline

« Ответ #4 : 20-05-2008 15:56 » 

chestr, Ну что тебе сказать, здравая мысль в программе есть, однако реализация маненько шалит. Там столько раз скачут с указателей на символы, что лично мне страшно.
А относительно разбирать алгоритм по запутанной программе - так ето стоит делать только в крайних случаях. А вообще делается наоборот. Сначала алгоритм - потом реализация. Если реализация будет не твоя, то желательно еще и обильные коментарии в коде.
А теперь отвлечемся маненько.
Ты себе смысл задания представляеш хотя бы в общих чертах?
Записан
chestr
Гость
« Ответ #5 : 20-05-2008 16:01 » 

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

ua
Offline Offline

« Ответ #6 : 20-05-2008 16:06 » 

А вот книга о шаблонах(если имеются ввиду шаблоны, которые в С++ начинаются с template) это ты зря, тут шаблон - ето некоторое обобщенное понятие, синонимом которого является "образец", тоесть "шаблон строки" ето то же самое, что и "образец строки".
Наводящий вопрос:
Ты когда нибудь искал у себя на компе файлы, точное имя которых ты не помнил? Если да, то как ты задавал имя этого файла?
Записан
chestr
Гость
« Ответ #7 : 20-05-2008 16:09 » 

хм... естесственно искал.. задавал первыми буквами слова. ключевыми буквами
Записан
Sands
Помогающий

ua
Offline Offline

« Ответ #8 : 20-05-2008 16:14 » 

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

Насколько я знаю, "*" - это соответствует 0 или более вхождений предшествующего выражения. например "до*" - соответствует "д" и "дом"
"?" - Соответствует 0 или 1 предшествующих выражений. Например, "мыш(ка)?"  - "мыш" и "мышка"
но как это всё впихнуть в код, я даже не представляю...
« Последнее редактирование: 20-05-2008 16:22 от chestr » Записан
Sands
Помогающий

ua
Offline Offline

« Ответ #10 : 20-05-2008 16:29 » 

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

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

Теперь появились какие-то мысли в плане шагов для поиска строк по шаблону?
Если нет, поставь себя на место программы. Как бы ты совершал поиск строк в тексте, если бы тебе дали некоторый шаблон?
Записан
chestr
Гость
« Ответ #11 : 20-05-2008 16:43 » 

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

ru
Offline Offline
Пол: Мужской

« Ответ #12 : 20-05-2008 17:07 » 

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

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

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

ru
Offline Offline
Пол: Мужской

« Ответ #14 : 20-05-2008 17:18 » 

Ага. Первый курс, значит "конечные автоматы" и "регулярные выражения" - наверное, ещё пустой звук. А как насчёт рекурсии, умеешь делать? По-моему, задача обработки спецсимволов в самом простом варианте - рекурсивная. Да и в твоём примере - тоже так решается.
« Последнее редактирование: 20-05-2008 17:20 от Вад » Записан
chestr
Гость
« Ответ #15 : 20-05-2008 17:28 » 

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

ru
Offline Offline
Пол: Мужской

« Ответ #16 : 20-05-2008 17:33 » 

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

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #17 : 20-05-2008 17:40 » 

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
Гость
« Ответ #18 : 20-05-2008 18:10 » 

спасибо за ссылки, сейчас буду изучать)
Записан
chestr
Гость
« Ответ #19 : 20-05-2008 20:25 » 

#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
Гость
« Ответ #20 : 20-05-2008 20:26 » 

ну а щас.
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #21 : 20-05-2008 20:43 » 

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Sands
Помогающий

ua
Offline Offline

« Ответ #22 : 21-05-2008 09:08 » 

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

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines