Solved

palindrome

Posted on 2004-09-07
13
421 Views
Last Modified: 2008-02-01
Hey..
I have managed to code a function to check if a word is a palindrome..
However, how to check if a sentence with many words is a palindrome?

Example of a palindrome sentence are these:
1. He is the the is he.
2. hello world hello.


Can give me hints on how to figure this?
0
Comment
Question by:ee_guest
  • 3
  • 2
  • 2
  • +5
13 Comments
 
LVL 11

Expert Comment

by:avizit
ID: 12003275
you mean when the words are taken as a whole?
i.e  He is the the is he  is obviously not a palindrome if you comsider letters  and not words

anyway a crude way to check if a sentence is a palindrome ( by your definition)
would be to

store the words in an array  

char array1[MaxWords] [Maxlength]  ;    where the MaxWords and Maxlength are constants chosen to your need

after you have filled the array with the words in the sentence you
can read it backwards and put the words in another array

now if both the arrays match then the sentence is a palindrome.

e.g  

This is This

your array now contains

A1[0] = This
A1[1]  = is
A1[2]  = This

read it in reverse and put in array2

A2[0] = This
A2[1]  = is
A2[2]  = This

and since they are same , it is a palindrome


similarly for

This is dog
we have

A1[0] = This
A1[1]  = is
A1[2]  = dog

and the reverse is

A2[0] = dog
A2[1]  = is
A2[2]  = This
so since A1 is not equal to A2  this is not a palindrome








0
 

Author Comment

by:ee_guest
ID: 12003412
the number of words and the number of letters per word is not known.
that's the problem.
0
 
LVL 11

Expert Comment

by:avizit
ID: 12003428
you can use the strtok() function

NAME
       strtok, strtok_r - extract tokens from strings

SYNOPSIS
       #include <string.h>

       char *strtok(char *s, const char *delim);

       char *strtok_r(char *s, const char *delim, char **ptrptr);

DESCRIPTION
       A  `token'  is a nonempty string of characters not occurring in the string delim, followed by \0 or by a character occur-
       ring in delim.

       The strtok() function can be used to parse the string s into tokens. The first call to strtok()  should  have  s  as  its
       first  argument.  Subsequent  calls  should  have the first argument set to NULL. Each call returns a pointer to the next
       token, or NULL when no more tokens are found.

       If a token ends with a delimiter, this delimiting character is overwritten with a \0 and a pointer to the next  character
       is saved for the next call to strtok().  The delimiter string delim may be different for each call.

       The  strtok_r()  function  is a reentrant version of the strtok() function, which instead of using its own static buffer,
       requires a pointer to a user allocated char*. This pointer, the ptrptr parameter, must be the same while parsing the same
       string.
0
 

Expert Comment

by:lebuihung
ID: 12003442
he is the the is he

1st:
count how many words u have in ur sence ( by looping thourgh the whole string and using SPACE delimiter)

2nd:
-tokenzise ur sentence into arrary of string

char * array[n]  -> n is the number that u obtain from 1st step
using strtok(char* str, char* delimiter)

for example:

char * s="he is the the is he"
strtok(s," ') will be "he"
strtok(NULL," ") will be "is"
strtok(NULL," ") will be "the"
....

( remember u should work on a copy of ur sentence string cuz strtok gonna change ur input string)

3rd:
compare
first string with last string: array[0] with array[n-1-0]   : array is array of string u got from step 2, and n is number of words in ur sentence (step 1)
second with second last: array[1] with array[n-1-1]
...
array[m] with array[n-1-m]

to compare to 2 string, use function strcmp(char*,char*) -> return 0 if they are equals.

-> for 3rd step, u can use for loop.

Hope it will help.


       
0
 

Expert Comment

by:lebuihung
ID: 12003460
to count a number of word in a sentence string, use this function

int countToken(char* s)
{
  int count;
 
  if(s==NULL)
    return 0;

  /* first one */
  strtok(s," ');
  count=1;

  /* keep tokenize until it returns a NULL */
  while(strtok(NULL," ")!=NULL)
     count++; /* increase the number of words */
 
  return count;
}

remember: use a copy of ur original string cuz strtok gonna change ur string. For example:

orginal string="This is an example"
Strtok function will put '\0' into spaces between ur orginal string:
"This'\0'is'\0'an'\0'example"

0
 
LVL 4

Expert Comment

by:pankajtiwary
ID: 12003928
This is the function which takes as input the string and returns the result as 1 if the input is a palindrome in words and 0 otherwise.

int is_palindrome_word(char* s) {
      char str[100];
      char* token[10] ;
      int no_of_tokens = 0, i ;
      strcpy(str, s) ;
      token[0] = strtok(str, " ");
      no_of_tokens++;
      while((token[no_of_tokens] = strtok(NULL, " ")) != NULL)
            no_of_tokens++;
      printf("Total tokens = %d\n", no_of_tokens);
      for(i = 0 ; i < (no_of_tokens/2); i++) {
            if ( strcmp(token[i], token[no_of_tokens-i-1] ) )
                  return 0 ;
      }
      return 1 ;
}

Do get beck in case of any problem.

Cheers!!!
0
VMware Disaster Recovery and Data Protection

In this expert guide, you’ll learn about the components of a Modern Data Center. You will use cases for the value-added capabilities of Veeam®, including combining backup and replication for VMware disaster recovery and using replication for data center migration.

 

Author Comment

by:ee_guest
ID: 12006264
to all..
the string to be checked has got unknown length and so using fixed array size is not feasible here..
0
 
LVL 23

Expert Comment

by:Mysidia
ID: 12012335
Consider using a recursive call.  Peel away the first and last word, compare them,
and check the inner piece at each succesive call.
0
 

Assisted Solution

by:lebuihung
lebuihung earned 30 total points
ID: 12013641
hi ee_guest,

basically, we dont have to know the length of string -> cuz all i do is try to find terminated character '\0' or use strlen function to get the length of this string.
0
 
LVL 12

Accepted Solution

by:
stefan73 earned 40 total points
ID: 12016988
Hi Mysidia,
> Consider using a recursive call.
Yes, that would be a solution "by the book". As this problem smells like homework, that's probably the way to do it :-)

Basically, like this:

is_palidrome(word,position)
   backposition = length of word - position
   
   if(backposition <= position)
      return true

   else if word[position]  != word[backposition]
      return false

   else
      return is_palidrome(word, position +1 )


Cheers!

Stefan
0
 
LVL 1

Expert Comment

by:bsnh99
ID: 12033058
No recursion needed: keep two pointers, one to beginning of sentence, one to end. Similar to Mysidia's solution, compare first/last words, move end pointer forward one word, move front pointer one word. Stop when end is in front of start pointer. This way you could test a sentence of thousands of words without crashing.

Also, it might help to write a wordcmp() function that uses space character as terminator.
0
 

Assisted Solution

by:aasia
aasia earned 30 total points
ID: 12042857
int getTokenCount(char *input)
{
      int wordCount = 0;
      if (strlen(input) == 0)
            return wordCount;
      char *tokenInput = strtok(input, " ");
      while (tokenInput != NULL)
      {
            wordCount++;
            tokenInput = strtok(NULL, " ");
      }
      return ((wordCount / 2) + (wordCount % 2));
}

char **getTokens(char *input, int tokCount)
{
      if (strlen(input) == 0)
            return NULL;
      int wordIdx = 0;
      char *tokenInput = strtok(input, " ");
      char **tokens = (char **)malloc(tokCount * sizeof(char **));
      while ((tokenInput != NULL) && (wordIdx < tokCount))
      {
            tokens[wordIdx] = (char *) malloc((strlen(tokenInput) + 1) * sizeof(char));
            strcpy(tokens[wordIdx++], tokenInput);
            tokenInput = strtok(NULL, " ");
      }

      return tokens;
}

bool isPalin(char *input)
{
      bool retVal = true;
      if (strlen(input) == 0)
            return retVal;
      
      char *tempInp = strdup(input);

      int tokCount = getTokenCount(tempInp);

      free(tempInp);

      tempInp = strdup(input);

      char **inputTokens = getTokens(tempInp, tokCount);

      free(tempInp);

      char *revInput = strdup(input);
      strrev(revInput);
      char **outputTokens = getTokens(revInput, tokCount);
      for (int idx = 0; (idx < tokCount) && retVal; idx++)
      {
            if (strcmpi(inputTokens[idx], strrev(outputTokens[idx])) != 0)
                  retVal = false;
      }
      free(inputTokens);
      free(revInput);
      free(outputTokens);
      return retVal;
}
0
 
LVL 12

Expert Comment

by:stefan73
ID: 12673185
BTW: my solution suggestion is tail-recursive. A good optimizer should be able to convert it into a loop, so you don't have to worry about crashing because of stack usage.
0

Featured Post

Scale it in WD Gold

With up to ten times the workload capacity of desktop drives, WD Gold hard drives employ advanced technology to deliver among the best in reliability, capacity, power efficiency and performance.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

932 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now