By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
435,337 Members | 2,048 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,337 IT Pros & Developers. It's quick & easy.

A stack of words in C (Sentence Palindrome)

P: 1
I was given this problem and I needed to create a code for it. So we have a string which is inputed by the user and then the code needs to check if the sentence is a palindrome or not ( the symmetric words to the middle of the sentence should be the same. But we should implement this using a stacks. I am familiar with functions pop() and push() (even thought I have not used them below). What I have thought until now is that I take the strings and create a stack of words out of this strings and use that stack to check if the sentence is a palindrome. I am stuck now and I can't really think of anything else. Help would be much appreciated.

Expand|Select|Wrap|Line Numbers
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. struct stack
  6. {
  7.     char s[30];
  8.     struct stack *next;
  9. };
  10.  
  11. typedef struct stack STACK;
  12.  
  13. struct top
  14. {
  15.     int num;
  16.     struct stack *top;
  17. };
  18.  
  19. typedef struct top TOP;
  20.  
  21. void create_stack(TOP *s, char str[1000])
  22. {
  23.     char temp1[30];
  24.     int i=0, j=0;
  25.  
  26.     STACK *temp;
  27.     temp=(STACK*)malloc(1*sizeof(STACK));
  28.  
  29.     while(1)
  30.     {
  31.         if(str[i]!=' ' && str[i]!='\0')
  32.         {
  33.             temp1[j]=str[i];
  34.             j++;
  35.         }
  36.         else
  37.         {
  38.             temp1[j]='\0';
  39.             strcpy(temp->s,temp1);
  40.             printf("%s\n", temp->s);
  41.  
  42.             if(s->top==NULL)
  43.             {
  44.                 s->top=temp;
  45.                 s->num=1;
  46.             }
  47.             else
  48.             {
  49.                 temp->next=s->top;
  50.                 s->top=temp;
  51.                 s->num++;
  52.             }
  53.             j=0;
  54.         }
  55.         if(str[i]=='\0')
  56.         {
  57.             break;
  58.         }
  59.         i++;
  60.     }
  61. }
  62.  
  63. void move_cursor(STACK *cursor, int pos)
  64. {
  65.     while (pos!=0)
  66.     {
  67.         cursor=cursor->next;
  68.         pos--;
  69.     }
  70. }
  71.  
  72. void compare(TOP *s)
  73. {
  74.     STACK *cursor1, *cursor2;
  75.     cursor1=s->top;
  76.     cursor2=s->top;
  77.     int cursor_move1, cursor_move2, i=0, check=1;
  78.  
  79.     if(s->num%2==0)
  80.     {
  81.         cursor_move1=s->num/2;
  82.         cursor_move2=(s->num/2)+1;
  83.  
  84.         while (i!=cursor_move1)
  85.         {
  86.             cursor1=s->top;
  87.             cursor2=s->top;
  88.             move_cursor(cursor1, i);
  89.             move_cursor(cursor2, cursor_move2);
  90.  
  91.             if(strcmp(cursor1->s,cursor2->s)!=0)
  92.             {
  93.                 check=0;
  94.                 break;
  95.             }
  96.             else
  97.             {
  98.                 i++;
  99.                 cursor_move2++;
  100.             }
  101.         }
  102.     }
  103.  
  104.     if(check==0)
  105.         printf("%d Neg", check);
  106.     else
  107.         printf("1Pos");
  108. }
  109.  
  110. void display(TOP *top)
  111. {
  112.     STACK *cursor;
  113.     cursor=top->top;
  114.  
  115.     while(cursor->next==NULL)
  116.     {
  117.         printf("%s pos\n ", cursor->s);
  118.  
  119.         cursor=cursor->next;
  120.     }
  121. }
  122.  
  123. int main()
  124. {
  125.     char input[1000];
  126.     TOP top;
  127.     top.num=0;
  128.     top.top=NULL;
  129.  
  130.     fgets(input, 100, stdin);
  131.  
  132.     input[strlen(input)-1]='\0';
  133.  
  134.     create_stack(&top, input);
  135.  
  136.     printf("%d \n ", top.num);
  137.  
  138.     display(&top);
  139.     printf("---------------------------------------------------------\n");
  140.     compare(&top);
  141.  
  142.  
  143.     return 0;
  144. }
  145.  
Feb 24 '17 #1
Share this Question
Share on Google+
1 Reply


weaknessforcats
Expert Mod 5K+
P: 9,197
Palindromes read backwards and forwards using the same letters:

A man a plan a canal Panama

and not the same words.


To use your stack approach read the string from left to write and push() each letter onto a stack. Then read the string from right to left and push each letter onto a second stack. Finally, pop each stack repeatedly and compare corresponding letters. If all letters match, you have a palindrome.

BTW: Use tolower() to be sure all stack entries are in lower case.
Feb 24 '17 #2

Post your reply

Sign in to post your reply or Sign up for a free account.