Some test cases failing while trying to implement palindrome of a string in C without using built in functions

Question

I was given this problem as a lab assignment and I've only got 3 days left to submit it.

The program is to print 1 for a palindrome and -1 for not palindrome. I could've easily done this using strrev() but the coding platform that our college uses is hosted on Linux so most built in string functions don't work.

I've tried many work arounds and nothing is working. I'm forced to implement the problem without string functions so it's getting a bit complicated. I managed to find some decent semi working code but it fails at some test cases.

Apparently, it's printing the opposite sign of -1 or 1 in some test cases and that's whats causing the errors.

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

int main(){
    char string[25],reverse_string[25]={'\0'};
    int i, length = 0, flag =0;
    int i,length=0,t,flag=0;
    scanf("%d",&t);
    while(t--){
        gets(string);
        for(i=0;string[i]!='\0';i++){
            length++;
        }
        for(i=length-1;i>=0;i--){
            reverse_string[length-i-1]=string[i];
        }
        for(flag=1,i=0;i<length;i++){
            if(reverse_string[i]!=string[i]){
                flag=0;
            }
        }
        if(flag==1){
            printf("1\n");
        }
        else{
            printf("-1\n");
        }
    }
}

Expected output:

3
asdffgg
-1
qq
1
dfghht
-1

The output that I'm getting in the website:

3
asdffgg
1
qq
-1
dfghht
-1

The output that I'm getting locally in the console:

3
1
asdffgg
-1
qq
-1

Answer 1

For starters the code shall not be compiled becuase there are duplicated declarations

int i, length = 0, flag =0;
int i,length=0,t,flag=0;

You should remove the first declaration.

Now about your obtained output if your actual code does not contain the above mentioned typo.

After this call of scanf

scanf("%d",&t);

the input buffer will contain the new line character '\n' that corresponds to the pressed key Enter. So the following call of gets at once encounters the new line character and as a result stores an empty string. And you get the following output

3
1

because an empty string is a palindrome. Pay attention to that the function gets removes the new line chracter '\n' from the input buffer.

Then after you entered this string

asdffgg

Your program correctly reported that the string is not a palindrome.

asdffgg
-1

After that you entered the string

qq

but within the current iteration of the while loop you did not reset the value of the variable length. It still stores the length of the previous entered string "asdffgg" that is equal to 7. And this for loop for the string "qq"

for(i=0;string[i]!='\0';i++){
    length++;
}

makes the value of the variable length equal to 9 (7 plus the length of the string "qq").

As a result the following for loops invoke undefined behavior and you get

qq
-1

First of all do not use the function gets. It is unsafe and is not supported by the C Standard. Instead use either scanf or fgets. For example

scanf( "%24s", string );

The auxiliary array reverse_string is redundant. And within each iteration of the while loop reset the value of the variable length to 0.

Also you should declare variables in minimum scopes where they are used. So before the while loop declare only the variable t

unsigned int t;

scanf( "%u", &t );
while ( t-- ){
//...

All other variables including the array string declare within the while loop.

For example to check if a string is a palindrome you can write

size_t n = 0;

while( string[n] ) ++n;

size_t i = 0;

while ( i < n / 2 && string[i] == string[n - i - 1] ) ++i;

printf( "%d\n", i == n / 2 ? 1 : -1 );

Answer 2

• strrev() is not standard C and also is not needed here
• coding platform that our college uses is hosted on Linux so most built in string functions don't work. Well, it is not true about Linux, or Windows.
• gets() was marked obsolete decades ago. Do not use it, ever. Prefer fgets().
• scanf() is ok, but it is a scanner, hence its name. It does not goes well with keyboard input, and it is source of some of the problems you had with your code:
  • to read nothing is ok for a scanner. Always test the return code.
  • scanf() reads only what is needed to satisfy the specifiers. The rest is left untouched in the input buffer. This includes the \n that ended the input.
  • scanf() skips white space, things like tabs, spaces and newlines. Many times is not what you want.
• scanf() was written to consume large files with tabular data, like csv files, not free format input as the keyboard offers.

Two examples for isPal()

Below are 2 examples and a test program with output. One is iterative, other is recursive and the 2 are common ways to write these. Sure, the iterative one is almost identical as the answer from @Wlad: it is the same thing. The recursive one, with 3 lines, must be everywhere on internet or text books, unless it is wrong :) I wrote them for a local reference here.

The logic is simple:

• Once you have he complete string you compute the size, or call strlen from string.h
• Consider the trivial case: a 1-char string is for sure palindrome.
• if the string size is odd then the center char is irrelevant, as in "ABCBA" C does not matter.
• you just need to check the 1st and last letter and zoom in until half way. In this case A==A and B==B so we have a palindrome
• integer division in C truncates the result so you can just divide by 2 the size. Here 5/2 = 2 and this is the number of comparisons to do.

an iterative version: isPal

int isPal(const char* str)
{
    char*  p    = (char*)str;
    size_t size = 0;
    while (*p++ != 0) ++size;  // strlen
    for (size_t i = 0; i < size / 2; i += 1)
        if (*(str + i) != *(str + size - i - 1))
            return -1;  // exit at 1st different
    return 1;           // all equal
}

As expected:

• the while loop computes size
• the for loop does the required size/2 comparisons, returning -1 at the first difference
• if no difference is found 1 is returned.

a recursive version, isPal_r

I included it here because it is a common assignment in introduction of recursive functions (a recursive function is one that calls itself)

int isPal_r(const char* str, const size_t size)
{
  if (size < 2) return 1;  // trivial
  if (*str != *(str + size - 1)) return -1;
  return isPal_r(str + 1, size - 2);  // try inner string
}

It is shorter because the loop is transformed in recursive calls, in the last line.

a test program

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

int  isPal(const char*);
void test_isPal(const char*);

int main(int argc, char** argv)
{
    if (argc < 2)
    {
        fprintf(
            stderr,
            "\nPlease enter strings on the command line: "
            "Ex: program "
            "str1 str2 ...\n");
        return -1;
    }
    fprintf(
        stderr,
        "     %d arguments.\n     Return '+1/-1' means "
        "string is "
        "'palindrome/NOT palindrome'\n\n",
        argc - 1);
    for (size_t i = 1; i < argc; i += 1)
        test_isPal(argv[i]);
    return 0;
}

int isPal(const char* str)
{
    char*  p    = (char*)str;
    size_t size = 0;
    while (*p++ != 0)++ size;  // strlen
    for (size_t i = 0; i < size / 2; i += 1)
        if (*(str + i) != *(str + size - i - 1))
            return -1;  // exit at 1st different
    return 1;           // all equal
}

int isPal_r(const char* str, const size_t size)
{
    if (size < 2) return 1;  // trivial
    if (*str != *(str + size - 1)) return -1;
    return isPal_r(str + 1, size - 2);  // try inner string
}

void test_isPal(const char* str)
{
    if (str == NULL) return;
    fprintf(stderr, "\nstring is \"%s\"\n", str);
    int res = isPal(str);
    fprintf(stderr, "     isPal() returned %d\n", res);
    char*  p    = (char*)str;
    size_t size = 0;
    while (*p++ != 0) ++size;  // strlen
    res = isPal_r(str, size);
    fprintf(stderr, "     isPal_r() returned %d\n", res);
}

This program calls the 2 functions. The program expects the strings in the command line, as it is the simplest way to test things: just enter the program name and the strings at the terminal...

Never write interactive code. It will just slows you down. Read from files, use constants, generators, whatever. When the program is ok, and only then, you can add the interacivity.

a simple test run

SO > v0 abc
     1 arguments.
     Return '+1/-1' means string is 'palindrome/NOT palindrome'


string is "abc"
     isPal() returned -1
     isPal_r() returned -1

SO > v

Please enter strings on the command line: Ex: program str1 str2 ...

SO > v aBc BB abcdxba abc1234321cba
     4 arguments.
     Return '+1/-1' means string is 'palindrome/NOT palindrome'


string is "aBc"
     isPal() returned -1
     isPal_r() returned -1

string is "BB"
     isPal() returned 1
     isPal_r() returned 1

string is "abcdxba"
     isPal() returned -1
     isPal_r() returned -1

string is "abc1234321cba"
     isPal() returned 1
     isPal_r() returned 1

SO > v A
     1 arguments.
     Return '+1/-1' means string is 'palindrome/NOT palindrome'


string is "A"
     isPal() returned 1
     isPal_r() returned 1

SO >