Palindrome Using a stack
Our professor required us to check if a word is a palindrome by using stacks.
Every time I run it, there's an error: Unhandled Exception. Access violation
What am I doing wrong? How can i improve my code? My code is as follows:
typedef struct stack{
char name;
struct stack * next;
}Stack;
void push(Stack**head, char value);
char pop(Stack**head);
int main(){
char word[11];
int i=0;
int lenght = 0;
Stack*head = NULL;
printf("Please type the word: ");
scanf("%s", word);
lenght = strlen(word);
while(word[i]!='\0'){
push(&开发者_如何学JAVA;head, word[i]);
i++;
}
i = 0;
while(pop(&head)==word[i]){
i++;
}
if(i==lenght) printf("The word is a palindrome");
else printf("The word is not a palindrome");
}
Your push
function should take
- the address of the stack head (you've it correct) and
- the character that needs to be pushed in (this needs fixing).
So the method signature becomes:
void push(Stack**head, char value);
and in the body of the function you add value
to the top of stack as:
temp->name = value;
Also you must always check the return value of malloc
.
Since you are returning the popped value from the function pop
it's return type must not be void
, change it to char
in both the declaration and the definition as:
char pop(Stack**head)
There is another logical error:
To start with you push all the characters of the input into the stack. Next you start popping the characters. There is no terminating condition for your popping. When you've popped all the characters (so your stack is empty) the next call to pop
will lead to a crash as you'll be dereferencing a NULL
pointer ( *head
will be NULL
).
To fix this you pop only the characters you've pushed by doing:
while(i<lenght && pop(&head)==word[i]){
Since the &&
is short circuited, pop
will not be called once you've popped all the characters.
Alternatively (and preferred approach) is to write another function called isEmpty
which return true
/1
when the stack is empty and use this method before you call the pop
method.
you should check you rich the end of stack or not in your code:
while(i < length && pop(&head)==word[i]){
i++;
}
I think you should change 'void pop(Stack **head){' into
char pop(Stack **head) {
and also guard against empty stack :
char pop(Stack**head){
Stack* temp;
char val;
temp = *head;
if (!temp) return 0;
val = temp->name;
*head = (*head)->next;
free(temp);
return val;
}
You might also consider using "recursion" which is somehow similar to constructing a stack, just that it is done for your method calls implicitly.
The palindrome problem is a classical exercise for learning the power of recursion :)
This is the function as you are calling it:
push(&head, i, word[i]);
This is the function as declared and defined:
void push(Stack**head, int i, char value[i]);
So arg 3 in the declaration is a character array, whereas arg 3 in the calling portion is a character. Change your push()
to use a character for value
and just omit i
:
void push(Stack**head, char value){
Stack *temp = (Stack*)malloc(sizeof(Stack));
temp->name = value;
temp->next = *head;
*head = temp;
}
Now call it with:
push(&head, word[i]);
your code got problem on while-pop
portion.
For your convinience, I have attached the modified working code for you:
typedef struct stack{
char name;
struct stack * next;
}Stack;
void push(Stack**head, char value);
char pop(Stack**head);
int main (int argc, const char * argv[]) {
char word[11];
int i=0;
int lenght = 0;
Stack*head = NULL;
printf("Please type the word: ");
scanf("%s", word);
lenght = strlen(word);
while(word[i]!='\0'){
push(&head, word[i]);
i++;
}
//i = 0;
//while(pop(&head)==word[i]){
// i++;
//}
int counter=0;
i=0;
for (counter=0; counter<lenght; counter++) {
if (pop(&head) == word[counter])
{
i++;
}
}
if(i==lenght) printf("The word is a palindrome");
else printf("The word is not a palindrome");
return 0;
}
void push(Stack**head,char value){
Stack *temp = (Stack*)malloc(sizeof(Stack));
temp->name = value;
temp->next = *head;
*head = temp;
}
char pop(Stack**head){
Stack* temp;
char val;
temp = *head;
val = temp->name;
*head = (*head)->next;
free(temp);
return val;
}
精彩评论