String Palindrome using Stack Write a program to f...
बनाया गया: 8 फ़रवरी 2025
बनाया गया: 8 फ़रवरी 2025
String Palindrome using Stack
Write a program to find whether a given string is palindrome or not using stack.
Palindrome:
A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward, ignoring spaces, punctuation, and capitalization. In other words, if you reverse the order of characters in a palindrome, it will still match the original sequence.
Input Format
The input consists of a single string.
The string may contain spaces, alphabets, and special characters.
Output Format
Print "Palindrome" if the given string is a palindrome.
Print "Not palindrome" if the given string is not a palindrome.
Constraints
-1 ≤ |S| ≤ 1000
-The string S may contain both uppercase and lowercase letters.
-Ignore spaces, punctuation marks, and case sensitivity in the string while checking for palindrome.
Sample 1:
Input
Output
racecar
Palindrome
Sample 2:
Input
Output
A man a plan a canal Panama
Not palindrome
Sample 3:
Input
Output
@RaceCar@
Not palindrome
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
// Function to check if the string is palindrome using stack
bool is_palindrome(char* s) {
}
int main() {
char s[1000];
text// 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;
}
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; }
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.
Pushing to Stack:
We then push all characters of the filtered
string onto a stack (here, simply an array used with a top
index).
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
.
Result:
true
, print "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.
solution is passing only first testcase
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 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:
But the sample outputs in your question explicitly say:
racecar
→ Palindrome (matches the usual definition)A man a plan a canal Panama
→ Not palindrome@RaceCar@
→ Not palindromeClearly, 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).
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:
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@
:
R
vs r
is a mismatch (case-sensitive) → Not palindrome.This literal check will pass the sample outputs exactly as given.
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:
racecar
→ Output: Palindrome
A man a plan a canal Panama
→ Output: Not palindrome
@RaceCar@
→ Output: Not palindrome
Which matches the sample outputs given in your question.
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:
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.
Check Palindrome using Queue Write a program to find whether a given string is palindrome or not using queue.
Palindrome: A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward, ignoring spaces, punctuation, and capitalization. In other words, if you reverse the order of characters in a palindrome, it will still match the original sequence.
Input Format The input consists of a single string. The string may contain spaces, alphabets, and special characters.
Output Format Print "Palindrome" if the given string is a palindrome. Print "Not palindrome" if the given string is not a palindrome.
Constraints -1 ≤ |S| ≤ 1000 -The string S may contain both uppercase and lowercase letters. -Ignore spaces, punctuation marks, and case sensitivity in the string while checking for palindrome.
Sample 1: Input Output racecar Palindrome Sample 2: Input Output A man a plan a canal Panama Not palindrome Sample 3: Input Output @RaceCar@ Not palindrome #include <stdio.h> #include <string.h> #include <stdbool.h> #include <ctype.h>
// Define the maximum size of the queue #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) { // printf("Queue overflow\n"); 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)) { // printf("Queue underflow\n"); return '\0'; } char c = q->data[q->front]; if (q->front == q->rear) { // Reset queue if it's now 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) {
}
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;
}
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).
We have a Queue
struct with:
front
and rear
indices,data[MAX]
to store characters,initQueue
, isEmpty
, enqueue
, and dequeue
functions.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.”
Build the reversed string using a queue:
enqueue
each character.reversedStr
. This gives you the reversed version of your filtered string.Compare the filtered string with reversedStr
.
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; }
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.
Queue for Reversal:
filtered
in reverse order of their appearance.Compare: We compare the original filtered
with the reversed
string. If they match, return true
(palindrome), otherwise false
.
Output:
true
, print “Palindrome”.false
, print “Not palindrome”.As with your stack-based question, the sample outputs claim:
racecar
→ PalindromeA man a plan a canal Panama
→ Not palindrome@RaceCar@
→ Not palindromeUnder 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:
Below is how you’d do that literally with a queue:
cbool 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.
this is also passing only first testcase
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.
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; }
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.”
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.
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.
…then you should do something like this:
cbool 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.