ee_guest
asked on
palindrome
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?
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?
ASKER
the number of words and the number of letters per word is not known.
that's the problem.
that's the problem.
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.
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.
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.
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.
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'examp le"
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'examp
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!!!
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]
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!!!
ASKER
to all..
the string to be checked has got unknown length and so using fixed array size is not feasible here..
the string to be checked has got unknown length and so using fixed array size is not feasible here..
Consider using a recursive call. Peel away the first and last word, compare them,
and check the inner piece at each succesive call.
and check the inner piece at each succesive call.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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.
Also, it might help to write a wordcmp() function that uses space character as terminator.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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.
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