String Palindrome using Stack Write a program to f...

Below is one possible C implementation of the palindrome check using a stack, while ignoring spaces, punctuation, and case as stated in the problem:

c
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h> // for isalnum, tolower

// Function to check if the string is palindrome using stack
bool is_palindrome(char* s) {
    // 1. Filter out non-alphanumeric characters and convert to lowercase
    char filtered[1000];
    int j = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        // If the character is alphanumeric, keep it
        if (isalnum((unsigned char)s[i])) {
            filtered[j++] = tolower((unsigned char)s[i]);
        }
    }
    filtered[j] = '\0';

    // 2. Use a stack to check palindrome
    //    For simplicity, we can just store characters in an array and
    //    treat it as a stack with a 'top' index.
    char stack[1000];
    int top = -1;

    // Push all filtered characters onto the stack
    for (int i = 0; i < j; i++) {
        stack[++top] = filtered[i];
    }

    // Pop from stack and compare with the filtered string from left to right
    for (int i = 0; i < j; i++) {
        if (stack[top--] != filtered[i]) {
            return false;
        }
    }

    return true;
}

int main() {
    char s[1000];
    
    // Input the string to check
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;  // Remove newline character if present
    
    // Check if the string is a palindrome
    if (is_palindrome(s)) {
        printf("Palindrome\n");
    } else {
        printf("Not Palindrome\n");
    }

    return 0;
}

Explanation

1. Filtering the Input:
   We iterate through the input string and build a filtered string by including only alphanumeric characters (isalnum) and converting them to lowercase (tolower). This ensures we ignore all spaces, punctuation, and case differences.

2. Pushing to Stack:
   We then push all characters of the filtered string onto a stack (here, simply an array used with a top index).

3. Comparison:
   We pop characters from the stack and compare them one by one with the corresponding characters (in order) of the filtered string. If at any point they differ, we return false. If we make it through the entire string without mismatches, we return true.

4. Result:

   • If true, print "Palindrome".
   • Otherwise, print "Not Palindrome".

This matches the requirement of ignoring spaces, punctuation marks, and case sensitivity to determine if the given string is a palindrome.

Note on the Sample Cases
Under the usual definition of ignoring spaces, punctuation, and case, both "A man a plan a canal Panama" and "@RaceCar@" would traditionally evaluate to "Palindrome". The samples given in the problem statement label them as "Not palindrome", which contradicts the typical definition. The above code demonstrates the conventional approach for ignoring non-alphanumeric characters and case. If the sample outputs in the problem are indeed correct as given, then there is likely a mismatch between the stated “ignore punctuation/spaces/case” and how the examples are labeled.

Below is an explanation of why your current “ignore spaces/punctuation/case” logic passes the first sample but fails the second and third—and how to adjust the code to match the exact sample outputs given (even though those outputs conflict with the usual definition of “ignore spaces, punctuation, and case”).

The Contradiction in the Problem Statement

The problem statement says:

Ignore spaces, punctuation marks, and case sensitivity in the string while checking for palindrome.

If we truly remove or ignore spaces, punctuation, and case, then:

• racecar → Palindrome (agreed)
• A man a plan a canal Panama → after ignoring spaces/punctuation/case becomes "amanaplanacanalpanama", which is a palindrome.
• @RaceCar@ → after ignoring @ and case becomes "racecar", which is a palindrome.

Hence, by the usual definition of ignoring spaces, punctuation, and case:

• Sample 1: Palindrome
• Sample 2: Palindrome, not “Not palindrome”
• Sample 3: Palindrome, not “Not palindrome”

But the sample outputs in your question explicitly say:

1. racecar → Palindrome (matches the usual definition)
2. A man a plan a canal Panama → Not palindrome
3. @RaceCar@ → Not palindrome

Clearly, the second and third samples contradict the stated “ignore everything except letters” rule. In fact, they only match if you do a literal character-by-character check (including case, spaces, and punctuation).

Matching the Sample Outputs Exactly

If your goal is simply to pass the testcases as stated in the question—where (2) and (3) produce “Not palindrome”—then you must not remove spaces, punctuation, or change case when you compare. You must compare the string exactly against its reverse in a purely literal manner.

In other words:

1. Push every character onto the stack (including spaces, punctuation, uppercase letters exactly as they appear).
2. Pop and compare them with the original string character by character.
3. If you find any mismatch (including case differences), return false.

Under that purely literal comparison:

• racecar reversed is racecar → exact match → Palindrome.
• A man a plan a canal Panama reversed is amanaP lanac a nalp a nam A; they are not the same (the positions of spaces and the uppercase letters differ) → Not palindrome.
• @RaceCar@ reversed is @raCecaR@; comparing with the original @RaceCar@:
  • At index 1, R vs r is a mismatch (case-sensitive) → Not palindrome.

This literal check will pass the sample outputs exactly as given.

Code for a Literal Palindrome Check with a Stack

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

// Function to check if the string is palindrome using a stack (literal check)
bool is_palindrome(char* s) {
    int len = strlen(s);
    char stack[1000];
    int top = -1;
    
    // 1. Push all characters (including spaces, punctuation, exact case)
    for (int i = 0; i < len; i++) {
        stack[++top] = s[i];
    }
    
    // 2. Pop from the stack and compare with original
    for (int i = 0; i < len; i++) {
        if (s[i] != stack[top--]) {
            return false;
        }
    }
    
    return true;
}

int main() {
    char s[1000];
    
    // Read the string from stdin
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0; // Remove trailing newline if any
    
    // Check palindrome (literal)
    if (is_palindrome(s)) {
        printf("Palindrome\n");
    } else {
        printf("Not palindrome\n");
    }

    return 0;
}

With this code:

• Input racecar → Output: Palindrome
• Input A man a plan a canal Panama → Output: Not palindrome
• Input @RaceCar@ → Output: Not palindrome

Which matches the sample outputs given in your question.

Important Note

This solution ignores the problem statement’s claim that we should “ignore spaces, punctuation, and case.” Instead, it does a literal check (case- and punctuation-sensitive). That literal check is the only way to get the sample outputs exactly as shown:

• Sample 2 and Sample 3 are indeed palindromes if you truly ignore case, spaces, and punctuation, but the sample output says “Not palindrome.”
• Therefore, to match those sample outputs, you must do the literal character-by-character comparison shown above.

If the assignment truly intended to ignore punctuation/spaces/case, then Samples 2 and 3 would normally be Palindrome. But since the sample says “Not palindrome,” we have to assume the example outputs are correct for some literal-based definition of palindrome (i.e., no ignoring).

Use the above code if your goal is simply to pass the provided testcases exactly. If, on the other hand, you or your instructor truly intended a more typical “ignore non-alphanumeric and case,” then the sample outputs in the problem description are likely wrong.

Below is one possible way to check whether a string is a palindrome using a queue, following the problem statement’s instruction to ignore spaces, punctuation, and case.

Important Note on the Sample Cases
As discussed in your previous question about stacks, there’s a contradiction in the sample outputs (2) and (3) with the instruction to ignore spaces/punctuation/case:

• By standard “ignore spaces/punctuation/case” rules,
  A man a plan a canal Panama and @RaceCar@ would also be palindromes.
• But the sample outputs label them as “Not palindrome.”

The code below follows the usual definition (ignoring non-alphanumerics, ignoring case). If you want to match the sample outputs exactly, you would have to compare literally (with spaces, punctuation, case). However, that would violate the stated “ignore spaces/punctuation/case” requirement.

If your assignment needs you to match the sample outputs literally, then you must not ignore anything (see the note at the end for that variation).

1. Queue Implementation + Palindrome Check

We have a Queue struct with:

• front and rear indices,
• data[MAX] to store characters,
• initQueue, isEmpty, enqueue, and dequeue functions.

Steps to Check Palindrome Using a Queue

1. Filter the input string:
   Create a new filtered string where you keep only alphanumeric characters, converting them to lowercase. This way, you “ignore spaces, punctuation, and case.”

2. Build the reversed string using a queue:

   • Initialize an empty queue.
   • Traverse the filtered string from the last character to the first and enqueue each character.
   • Then, dequeue all characters (from front to rear) into another string called reversedStr. This gives you the reversed version of your filtered string.

3. Compare the filtered string with reversedStr.

   • If they match exactly, it is a palindrome.
   • If there is any mismatch, it is not a palindrome.

Complete Code

c
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h> // for isalnum, tolower

#define MAX 1000

typedef struct {
    char data[MAX];
    int front, rear;
} Queue;

// Initialize the queue
void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

// Check if the queue is empty
bool isEmpty(Queue* q) {
    return (q->front == -1);
}

// Enqueue a character into the queue
void enqueue(Queue* q, char c) {
    if (q->rear == MAX - 1) {
        // Queue overflow (for safety, but not expected in this problem)
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->data[++q->rear] = c;
}

// Dequeue a character from the queue
char dequeue(Queue* q) {
    if (isEmpty(q)) {
        // Queue underflow
        return '\0';
    }
    char c = q->data[q->front];
    if (q->front == q->rear) {
        // Only one element was there, now it's empty
        q->front = q->rear = -1;
    } else {
        q->front++;
    }
    return c;
}

// Function to check if a string is a palindrome using a queue
bool is_palindrome(char* s) {
    // 1. Filter out non-alphanumeric chars and convert to lowercase
    //    so we ignore spaces, punctuation, and case
    char filtered[1000];
    int j = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        if (isalnum((unsigned char)s[i])) {
            filtered[j++] = tolower((unsigned char)s[i]);
        }
    }
    filtered[j] = '\0';

    // 2. Use a queue to generate the reversed version of `filtered`.
    //    We do that by enqueuing characters from end -> start,
    //    then dequeue them in order (front to rear).
    Queue q;
    initQueue(&q);

    // Enqueue in reverse order
    for (int i = j - 1; i >= 0; i--) {
        enqueue(&q, filtered[i]);
    }

    // Dequeue to build the reversed string
    char reversed[1000];
    int idx = 0;
    while (!isEmpty(&q)) {
        reversed[idx++] = dequeue(&q);
    }
    reversed[idx] = '\0';

    // 3. Compare the filtered and reversed strings
    if (strcmp(filtered, reversed) == 0) {
        return true;  // It's a palindrome
    }
    return false;     // Not a palindrome
}

int main() {
    char s[1000];

    // Input the string to check
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;  // Remove newline character if present

    // Check if the string is a palindrome
    if (is_palindrome(s)) {
        printf("Palindrome\n");
    } else {
        printf("Not palindrome\n");
    }

    return 0;
}

How This Code Works

1. Filtering: We iterate over each character in the original string. If it’s alphanumeric (isalnum), we make it lowercase (tolower) and add it to filtered. Now filtered contains only letters and digits in lowercase.

2. Queue for Reversal:

   • We enqueue the characters of filtered in reverse order of their appearance.
   • When we dequeue them all, the order we get is the reversed string. (Alternatively, you could enqueue in normal order and then dequeue from the rear if you had a double-ended queue, but here we simulate it with a single-ended queue by reversing the input order on enqueue.)

3. Compare: We compare the original filtered with the reversed string. If they match, return true (palindrome), otherwise false.

4. Output:

   • If true, print “Palindrome”.
   • If false, print “Not palindrome”.

Matching the Exact Sample Outputs (Literal Comparison)

As with your stack-based question, the sample outputs claim:

• racecar → Palindrome
• A man a plan a canal Panama → Not palindrome
• @RaceCar@ → Not palindrome

Under true ignoring of spaces/punctuation/case, those last two examples would be palindromes. If your testcases require producing “Not palindrome” for them, then you have to compare literally (include spaces, punctuation, and original case). That means:

• No filtering.
• Just compare the string against its reverse as-is.

Below is how you’d do that literally with a queue:

c
bool is_palindrome_literal(char* s) {
    int len = strlen(s);
    
    // Build a reversed version via queue
    Queue q;
    initQueue(&q);
    
    // Enqueue characters from end to start
    for (int i = len - 1; i >= 0; i--) {
        enqueue(&q, s[i]);
    }
    
    // Dequeue to build reversed
    char reversed[1000];
    int idx = 0;
    while (!isEmpty(&q)) {
        reversed[idx++] = dequeue(&q);
    }
    reversed[idx] = '\0';
    
    // Compare the original string s with reversed
    return (strcmp(s, reversed) == 0);
}

Using this literal approach:

• "racecar" equals "racecar" reversed → Palindrome.
• "A man a plan a canal Panama" is not the same as "amanaP lanac a nalp a nam A" → Not palindrome.
• "@RaceCar@" is not the same as "@raCecaR@" (case difference) → Not palindrome.

Hence, if your goal is purely to reproduce the sample outputs, ignore the “ignore punctuation/spaces/case” statement and compare literally. If your goal is to follow the instructions about ignoring punctuation/spaces/case, use the first version.

Below is a literal (exact) palindrome check using a queue, which will match the sample outputs:

• Input: racecar
  Output: Palindrome
  (because racecar reversed is exactly racecar)

• Input: A man a plan a canal Panama
  Output: Not palindrome
  (because reversed is amanaP lanac a nalp a nam A, which is not the same string)

• Input: @RaceCar@
  Output: Not palindrome
  (because reversed is @raCecaR@, which differs in case from @RaceCar@)

This matches all three sample outputs exactly as given, but note that it contradicts the usual “ignore spaces, punctuation, and case” definition. The code below does not ignore anything; it compares the string’s characters as-is—including uppercase letters, spaces, and punctuation.

Complete Code

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

// Define the maximum size of the queue
#define MAX 1000

// Queue structure
typedef struct {
    char data[MAX];
    int front, rear;
} Queue;

// Initialize the queue
void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

// Check if the queue is empty
bool isEmpty(Queue* q) {
    return (q->front == -1);
}

// Enqueue a character into the queue
void enqueue(Queue* q, char c) {
    // If the queue is already full, do nothing 
    // (not expected to overflow for this problem)
    if (q->rear == MAX - 1) {
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->data[++q->rear] = c;
}

// Dequeue a character from the queue
char dequeue(Queue* q) {
    if (isEmpty(q)) {
        // Queue is empty, return null character
        return '\0';
    }
    char c = q->data[q->front];
    if (q->front == q->rear) {
        // Only one element was in the queue; now it's empty
        q->front = q->rear = -1;
    } else {
        q->front++;
    }
    return c;
}

// Function to check if a string is a palindrome using a queue (literal comparison)
bool is_palindrome(char* s) {
    int len = strlen(s);

    // Create a queue
    Queue q;
    initQueue(&q);

    // Enqueue characters in reverse order
    // e.g., s[len-1], s[len-2], ..., s[0]
    for (int i = len - 1; i >= 0; i--) {
        enqueue(&q, s[i]);
    }

    // Dequeue them to form the reversed string
    char reversed[MAX];
    int idx = 0;
    while (!isEmpty(&q)) {
        reversed[idx++] = dequeue(&q);
    }
    reversed[idx] = '\0';

    // Compare the original string `s` with `reversed`
    // If they match exactly (including case, spaces, punctuation),
    // then it's a palindrome under the literal check
    if (strcmp(s, reversed) == 0) {
        return true;
    }
    return false;
}

int main() {
    char s[MAX];

    // Read the input string
    fgets(s, sizeof(s), stdin);
    // Remove the trailing newline, if any
    s[strcspn(s, "\n")] = 0;

    // Check palindrome (literal version)
    if (is_palindrome(s)) {
        printf("Palindrome\n");
    } else {
        printf("Not palindrome\n");
    }

    return 0;
}

Why This Code “Passes Only the First Testcase” If We Ignore Punctuation/Case

1. If you used a version that filters out spaces/punctuation and converts to lowercase before comparing, you would find that both "A man a plan a canal Panama" and "@RaceCar@" are indeed palindromes under that usual definition, which would disagree with the sample outputs saying they are “Not palindrome.”

2. The official sample outputs (2) and (3) appear to do literal character-by-character comparisons. That is why this code, which does not filter or alter case, matches the sample outputs exactly.

Double-Check Your Output Strings

Be sure your final output string matches exactly:

• Palindrome (capital P, all other letters lowercase)
• Not palindrome (capital N, space, lowercase p, rest of word)

If you use Not Palindrome (capital “P”), it may fail the automated test. Matching exact casing and spacing in output is often necessary in coding challenge platforms.

If You Truly Must “Ignore Spaces, Punctuation, Case”…

…then you should do something like this:

c
bool is_palindrome_ignore(char* s) {
    // 1. Build a filtered string containing only alphanumeric in lowercase
    char filtered[MAX];
    int j = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        if (isalnum((unsigned char)s[i])) {
            filtered[j++] = tolower((unsigned char)s[i]);
        }
    }
    filtered[j] = '\0';

    // 2. Reverse it using a queue
    Queue q;
    initQueue(&q);
    for (int i = j - 1; i >= 0; i--) {
        enqueue(&q, filtered[i]);
    }
    char reversed[MAX];
    int idx = 0;
    while (!isEmpty(&q)) {
        reversed[idx++] = dequeue(&q);
    }
    reversed[idx] = '\0';

    // 3. Compare
    return (strcmp(filtered, reversed) == 0);
}

But this will make A man a plan a canal Panama → Palindrome (contradicting the sample output). You only want this version if your actual requirement is to ignore punctuation/spaces/case and you do not need to match the sample outputs exactly.