I was implementing a palindrome checker using stack and its misbehaving ,and the pop function doesn't work as intended.

The way I tried is to push first half values to stack and pop them and check if these popped elements matched with the elements after the half of string.

This is my code:

#include<stdio.h>
#include<string.h>


int top = -1;


char pop(char stack[])
{
    return stack[top--];
}

void push(char item, char stack[])
{
   stack[  top] = item;
}

int main()
{
int n,count=0;
char stack[50], s[50],str;

printf("enter string: ");
scanf("%s",s);

n = strlen(s);
// printf("stack is \n");
// puts(stack);

printf("len is %d\n", n/2);

for(int i=0; i<n/2; i  )
{
    push(s[i], stack);

}

for(int i=0; i<n/2; i  )
{ 
printf("pop is : %c\n", pop(stack));
  if(s[n-i] == pop(stack))
  {
     count  ;
  } 
}

printf("count is %d\n", count);

if (count == strlen(s)/2)
{
    printf("paalll\n");
}
else
{
    printf("not pall\n");
}

return 0;
}

and this is the out put im getting when tried to print the popped values:

enter string: dfhdS
len is 2
pop is : f
pop is : 

I tried printing out whether it is being pushed to stack or not, it is! ,thats working fine but the popping somehow fails.

CodePudding user response：

You push the values on to the stack from the start of the string to the middle. When popping these values, they will be retrieved in reverse.

You attempt to compare these reversed values to those starting from the end of the string until the middle of the string.

For example, using the string hannah:

After looping through the first half of this string, the stack will contain the following values:

top
    n
    a
    h

Correcting the off-by-one error (s[n-i] will start by checking the null terminating byte), the loop will compare:

popped value = n, end of string = h
popped value = a, end of string = a
popped value = h, end of string = n

You are also popping two values off the stack at a time

printf("pop is : %c\n", pop(stack));
if(s[n-i] == pop(stack))

which will deplete the stack too quickly.

Push the first half of the string onto the stack, and then compare the popped values with the second half of the string, always iterating towards the end of the string.

Make sure to adjust the second starting position for odd length strings.

#include <stdio.h>
#include <string.h>

int top = -1;

char pop(char stack[])
{
    return stack[top--];
}

void push(char item, char stack[])
{
    stack[  top] = item;
}

int main(void)
{
    char stack[50], s[50];

    printf("enter string: ");
    if (1 != scanf("Is", s)) {
        fprintf(stderr, "Failed to read string.\n");
        return 1;
    }

    size_t n = strlen(s);

    for (size_t i = 0; i < n / 2; i  )
        push(s[i], stack);

    for (size_t i = (n / 2)   (n & 1); i < n; i  ) {
        if (pop(stack) != s[i]) {
            puts("Not a palindrome!");
            return 0;
        }
    }

    puts("Is palindrome!");
}