2
\$\begingroup\$

I'm taking a sentence and determining whether or not it is a palindrome. I'm doing this while learning about stacks.

  1. Is there a way I can use pointers instead of char array 'sent' so that the number of input characters need not be constrained to 20 in the following code?

  2. The code is working fine, but should there be any improvements in terms of performance or anything else?

  3. Is there anything important about pointers I should remember while using stacks, like initializing it to NULL?

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

typedef struct node
{
    char data;
    struct node *link;
}StackNode;

void insertData(StackNode **);
void push(StackNode **, char);
void checkData(StackNode **);
bool pop(StackNode **,char *);

char sent[20] = "";

void main()
{
   StackNode *stackTop;
   stackTop = NULL;
   insertData(&stackTop);
   checkData(&stackTop);
   printf("\n");
   return;
}

void insertData(StackNode **stackTop)
{
    char c;
    int len;

    printf("Enter the Sentence\n");
    while( ( ( c = getchar() ) != '\n'))
    {   
        if( ( ( c>='a' &&c<='z') || (c>='A' && c<='Z')))
        {
            if((c>='A' && c<='Z'))
            {
                int rem;
                rem = c-'A';
                c='a' + rem;
            }
            push(stackTop,c);
            len = strlen(sent);
            sent[len++]=c;
            sent[len]='\0';
        }
    }
    printf("Letters are %s\n\n",sent);
}

void push(StackNode **stackTop,char c)
{
    StackNode *pNew;
    pNew = (StackNode*) malloc(sizeof(StackNode));
    if(!pNew)
    {
        printf("Error 100:Out of memory\n");
        exit(100);
    }
    pNew->data = c;
    pNew->link = *stackTop;
    *stackTop = pNew;
}

void checkData(StackNode **stackTop)
{
    char c;
    int i=0;
    while(pop(stackTop,&c))
    {
        if( c !=sent[i++])
        {
            printf("Not palindrome");
            return;
        }
    }
    printf("Palindrome");
}

bool pop(StackNode **stackTop,char *c)
{
    StackNode *pNew;
    pNew = *stackTop;
    if(pNew == NULL)
        return false;
    *c = pNew->data;
    *stackTop = pNew->link;
    printf("char poped %c\n",*c);
    free(pNew);
    return true;
}
\$\endgroup\$
5
\$\begingroup\$

One MAJOR problems here.

char sent[20] = "";

Don't use global variables. Globally mutable state makes your code hard to debug/test and generally behave correctly. You not only need to know what a function does but also what external state the function depends on. Pass all state into functions via the parameters (that way you know exactly what it depends on).

Note: Global constants are fine.

This is not a valid declaration of main() even in C

void main()

/* TRY */

int main(void)
/* OR */
int main(int argc, char* argv[])

Lets declare and initialize variables on the same line:

   StackNode *stackTop;
   stackTop = NULL;

   /* Try */
   StackNode *stackTop = NULL;

Note if you correct main you will also need to correct the return statement so it returns a value.

   return;

But when the function is void there seems little point in putting a return statement.

OK. This reads a line.

void insertData(StackNode **stackTop)

But there are already functions that do that.
You can use the scanf series of commands. Your code drops any non alphabetic characters (but you could read a line then post processes to remove and invalid characters).

You should read up on the functions for handling characters.

isalpha()       /* Note it is locale aware and thus will return true
                   for characters other than a-z A-Z if your locale is
                   not set to the default (which is C)
                 */

tolower()       /* Lowercases letters. No affect on anything else */

I would have done:

char  data[50]; /* You wanted a max of 20 letters.
                   But if the user types a space between every word
                   it can get longer and we post processes to remove
                   space so. So we will cut off at 50.
                */

fscanf(stdin, "%50[^\n]", data); /* read upto 50 characters
                                    that are not '\n'
                                    into data
                                 */
fscanf(stdin, "%*[^\n]");        /* Read the rest of the line if
                                    the user types more than 50 and
                                    throw it away
                                 */
fscanf(stdin, "\n");             /* Read the '\n' off the input */

/* Now remove any non letter characters and lowercase at the same time */
int removed = 0;
for(int loop = 0; data[loop]; ++loop)
{
    if (!isalpha(data[loop]))
    {
        removed++;
        continue;       // starts next iteration.
    }
    data[loop-removed] = tolower(data[loop]);
}
data[loop-removed] = '\0';  /* Add string terminator */

Back to reviewing your version.

This is going to enter an infinite loop if you hit an error or end of file before you hit '\n'.

    while( ( ( c = getchar() ) != '\n'))

Then end of file is a real possibility if somebody pipes a file into your command from the command line.

    cat file | ./palindromeCommand

This check:

        if( ( ( c>='a' &&c<='z') || (c>='A' && c<='Z')))

Is really covered by: isalpha()

This check:

            if((c>='A' && c<='Z'))
            {
                int rem;
                rem = c-'A';
                c='a' + rem;
            }

Is the same as: c = tolower(c);

This string append:

            len = strlen(sent);
            sent[len++]=c;
            sent[len]='\0';

Can be achieved with: strncat(sent, &c, 1);

Normally I don't want checking functions to mutate the state of any objects. The name "check" implies I am looking not modifying.

void checkData(StackNode **stackTop)

Also you are mixing business logic and presentation logic into a single function. Make this function check to see if it a palindrome and return an appropriate value (0 for false and non zero for true (for example)). The code can then use this function to check for a palindrome and take appropriate action (like display text) in the display logic:

Initialize and declare in the same line:

    StackNode *pNew;
    pNew = *stackTop;

    /* Easier to read as */
    StackNode *pNew = *stackTop;

Overall I think you overcomplicated the processes with your StackNode concept. But it works. It would have been much simpler to use pointers to either end of the sent array and work towards the middle checking letters.

int checkForPalindrome(char* sent, int length)
{
     char*    st   = sent;
     char*    ed   = sent + length - 1;

     int   result = true;

     while(st < ed && result)
     {
         if (*st != *ed) { result = false;}
         ++st;
         --ed;
     }
     return result;
}
\$\endgroup\$
2
\$\begingroup\$

Where to start ;) Some hints:

  1. Was is part of the task to use a stack for this? You could easily check for the palindrome just on the char array by looping over it from left to right.
  2. Why using two different data structures for the same content: an char array for data entered and a stack for the reverse string? Try to be consistent.
  3. Why having the char array as a global variable but passing the stack as function parameter? Try to be consistent.
  4. If you return the stack pointer, you don't have to pass it as pointer to pointer - just change in the function and return the new one.
  5. Same for the char in pop_stack() - pass back as return value, '\0' is a perfectly valid in bounds value here.
  6. I'd try to define and init a variable in one statement, e.g. StackNode *stackTop = NULL;. Avoids missing initialization, saves screen real estate, and sometimes even allows declaration as const - something admittedly not liked by all C programmers.
  7. Wrt NULLs - no quick answer here, you can find books filled with that. What I do: avoid where possible, use asserts, and even name variables/parameters, so that I easily see whether they can be NULL; e.g. opt_ptr, if ptr might be NULL.
  8. Good things last: you really think hard to have consistent naming, formatting, and structure - being self-driven here will keep you making progress, all those little things I mentioned above will just come with experience ;)
\$\endgroup\$
  • \$\begingroup\$ The advantage of push(&stack,c); is that the compiler makes sure that it is correctly called. Over stack = push(stack, c) here the caller needs to remember to assign the result to variable or loose track. So the first version is preferred as there is less chance of user error (it only needs to be done correctly once by the creator of the function rather than being done correctly every time by the user of the function). \$\endgroup\$ – Martin York Jun 23 '13 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.