#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_SIZE 100 // Maximum stack size
// Structure for the stack
struct Stack {
char items[MAX_SIZE];
int top;
};
// Function to initialize the stack
void initStack(struct Stack* stack) {
stack->top = -1;
}
// Function to check if the stack is empty
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
// Function to check if the stack is full
int isFull(struct Stack* stack) {
return stack->top == MAX_SIZE - 1;
}
// Function to push an item onto the stack
void push(struct Stack* stack, char item) {
if (isFull(stack)) {
printf("Stack overflow!\n");
exit(1);
}
stack->items[++stack->top] = item;
}
// Function to pop an item from the stack
char pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow!\n");
exit(1);
}
return stack->items[stack->top--];
}
// Function to clean the string (remove non-alphanumeric, convert to lowercase)
void cleanString(const char* input, char* output) {
int j = 0;
for (int i = 0; input[i] != '\0'; i++) {
if (isalnum(input[i])) {
output[j++] = tolower(input[i]);
}
}
output[j] = '\0';
}
// Function to check if the string is a palindrome using a stack
int isPalindrome(const char* input) {
// Clean the input string
char cleaned[MAX_SIZE];
cleanString(input, cleaned);
int len = strlen(cleaned);
if (len == 0) {
return 1; // Empty string is a palindrome
}
// Initialize stack
struct Stack stack;
initStack(&stack);
// Push first half of the string onto the stack
int mid = len / 2;
for (int i = 0; i < mid; i++) {
push(&stack, cleaned[i]);
}
// Skip the middle character for odd-length strings
int start = (len % 2 == 0) ? mid : mid + 1;
// Compare second half with popped characters
for (int i = start; i < len; i++) {
if (pop(&stack) != cleaned[i]) {
return 0; // Not a palindrome
}
}
return 1; // Palindrome
}
// Main function to test the palindrome check
int main() {
// Test cases
const char* testCases[] = {
"A man, a plan, a canal: Panama",
"race a car",
"Was it a car or a cat I saw?",
"",
"hello",
"12321",
"Madam, I'm Adam"
};
int numTests = sizeof(testCases) / sizeof(testCases[0]);
for (int i = 0; i < numTests; i++) {
printf("Input: \"%s\"\n", testCases[i]);
printf("Output: %s\n", isPalindrome(testCases[i]) ? "Palindrome" : "Not a Palindrome");
printf("\n");
}
return 0;
}
Output:
Comments
Post a Comment