VPF::[C++] Поиск палиндромов (используя стек) в строке

Apache

Дата 9.11.2006, 16:04 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 9.11.2006

Репутация: нет
Всего: нет

Всем добрый день!

Буду очень признателен, если кто-нибудь поможет с написанием алгоритма для программы.
Программа должна во введенной с клавиатуры строке текста находить палиндром(последовательность символов, которая читается одинаково во всех направлениях). Находить палиндром программа должна при помощи стека.

Вот полный текст задания:

Цитата

Cтек магазинного типа на базе связного списка. Интерфейс должен включать операции вставки (push) и выталкивания (pop) элемента, вывода всего содержимого стека, определения числа элементов стека. Постфиксные (инфиксные) выражения должны включать операции *, /, +, -.

Цель работы: поиск палиндромов в строке (фрагментов, одинаково читаемых в обоих направлениях). Пробелы и знаки пунктуации при этом игнорируются.

При этом:

1) Для "общения" с пользователем программа должна использовать библиотеку "readline"(у меня получалось только под Unix скомпилировать и запустить, и то - с проблемами...)
2) Для ввода строки с клавиатуры нельзя использовать gets(), строка должна передаваться параметром readline'а по запросу(очень желательно)
3) Найденные палиндромы надо будет вывести на экран.

Вот, что у меня получилось с реализацией стека:

Код


#include <stdlib.h> 
#include <iostream> 
#include <readline/readline.h>
#include <readline/history.h>
#include <string.h>

using namespace std;

struct stackNode               
{                              
 char data;                    
 struct stackNode *nextPtr;    
};                             
typedef stackNode StackNode;
typedef StackNode *StackNodePtr;

class Stack                                                     
{                                                               
 public:                                                         
        Stack();                                               
        char pop(void);                                         
        void push(char);                                        
        char get(void);                                         
        int isEmpty();                                       
        void print(); 
                             
 private:                                                 
         StackNode *StackStart;                  
}; 


Stack::Stack():StackStart(NULL){};             



char Stack::pop()                                          
{                                                              
 StackNode *tempPtr;                                  
 char output;                                             
 if(isEmpty())                                           
              return 0;                                    
 else                                                   
     {                                                 
      if(StackStart!=NULL)                                  
      tempPtr=StackStart;                                  
      StackStart=StackStart->nextPtr;                          
      output=tempPtr->data;                                 
      delete tempPtr;                                      
      return (output);                                        
  }                                                           
}                                                              



void Stack::push(char input)                                   
{                                                            
  StackNode *newPtr;                                         
 newPtr=new StackNode;                                       
newPtr->data=input;                                              
if(isEmpty() )                                               
{                                                           
StackStart=newPtr;                                            
StackStart->nextPtr=NULL;                                    
}                                                              
else                                                           
 {                                                               
 newPtr->nextPtr=StackStart;                                  
 StackStart=newPtr;                                        
 }                                                            
}                                                              


char Stack::get(void)
{
if(!isEmpty())
return StackStart->data;     
else return 0;
}



int Stack::isEmpty()                                            
{                                                              
 return (StackStart)==0;                                         
}                                                              



void Stack::print()                                              
{                                                              
 if(isEmpty())                                                   
              {                                                  
               cout<<"The stack is empty.\n\n";                  
               return;                                          
              }                                               
 else                                                            
     {                                                           
      StackNode *currentPtr;                                    
      cout<<"Stack content: ";                                  
      currentPtr=StackStart;                                 
      while(currentPtr!=NULL)                                  
                          {                                    
                           cout<<currentPtr->data<<"->";      
                           currentPtr=currentPtr->nextPtr;     
                          }                                      
      cout<<"\n\n";                                       
     }                                                    
}                                                                


int main()                                                     
{
                                                        
}

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

Код


 struct com_mod
  {
   char *name;
   rl_icpfunc_t *func_line;
   char *expl;
  };

int Exit_p(), print_com_list();//прототипы функций ридлайна...


 com_mod comand_list[] =           // Массив, содержащий названия команд, функций, их описания
   {

         {"exit", Exit_p, " - Exit program"},
         {"?", print_com_list, " - To see a KEYWORDS` list"},

/* тут должно быть описание функций для ввода строки, ее анализа на содержание палиндромов  */

         {(char *)NULL, (rl_icpfunc_t *)NULL, (char *)NULL }

   }   ;




int Exit_p(char *)
{
 exit(0);
}


int print_com_list(char *)
{
   register int i;
     for(i=0;i<6;i++)
     cout << comand_list[i].name  << comand_list[i].expl << endl;
   return 0;
}


char *string_up(char *str)
{
   register char *s, *t;
      for(s = str; whitespace(*s);s++)
         if(*s == 0) return (s);
   t = s + strlen(s) - 1;
      while(t > s   &&  whitespace(*t))
      t--;
     *++t = '\0';
     return s;
}


struct com_mod *find(char *income_str)
{
int i;
     for(i = 0; comand_list[i].name; i++)
     if(!strcmp(income_str, comand_list[i].name))
     return (&comand_list[i]);
     return NULL;
}


int exec_line(char *word_in)
{
struct com_mod *comm;
char *line;
     line = strtok(word_in, " \n");
     comm = find(line);
     line = strtok(NULL, "\n");
       if(!comm)
          {
            cout<<"There is no such command :-("<<endl;
            return -1;
          }
return  (   (*(comm->func_line)) (line) );
}



void command_module()
{
   char *input_word, *exec_string;
   cout << "\n Welcome!!! (^_^)\n\n";

   while(1)
    {
      input_word = readline("\Make your choice: >>");
      exec_string = string_up(input_word);
        if(*exec_string) exec_line(exec_string);
      delete input_word;
    }

}

int main()
{
char *line, *s;
int done;



  /* Loop reading and executing lines until the user quits. */
  for ( ; done == 0; )
    {
      line = readline ("Menu: ");

      if (!line)
        break;

      /* Remove leading and trailing whitespace from the line.
         Then, if there is anything left, add it to the history list
         and execute it. */
   //   s = stripwhite (line);                                       

      if (*s)
        {
          add_history (s);
         // execute_line (s);
        }

      free (line);
    }
  exit (0);  
  
  
  
    
return 0; 
}

Помогите, пожалуйста!!!

sergejzr

Дата 9.11.2006, 16:14 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 11
Всего: 360

Блин! представляешь, что будет, если задать в поиск по форуму слово "палиндром" ? smile

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

Apache

Дата 9.11.2006, 19:36 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 9.11.2006

Репутация: нет
Всего: нет

Цитата(sergejzr @ 9.11.2006, 16:14)

Блин! представляешь, что будет, если задать в поиск по форуму слово "палиндром" ? smile

Если задать его в поиск, будет найдено много тем, в которых описано, как искать палиндром.
Ни одна из них не описывет, как это делать, используя стек smile

. У меня проблема в этом...
Не могу загнать строку, как массив символов, не используя gets(), не знаю, как надо искать палиндром, и каким образом сохранять(отображать) найденный палиндром, если он есть.

Это сообщение отредактировал(а) Apache - 10.11.2006, 20:14

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »