[DSA] Kiểm tra chuỗi Palindrome dùng Stack

Nguồn: Click here

Chuỗi palindrome là một chuỗi ký tự mà khi đọc từ trái sang phải hay từ phải sang trái đều cho ra kết quả như nhau. Ví dụ như chuỗi "racecar" là một chuỗi palindrome, bởi vì khi đọc từ trái sang phải hay từ phải sang trái đều cho ra kết quả "racecar". Chuỗi palindrome thường được sử dụng trong các bài toán về xử lý chuỗi và các thuật toán liên quan đến chuỗi.

Để xác định xem một xâu kí tự có phải là Palindrome hay không bằng cách sử dụng cấu trúc dữ liệu Stack, chúng ta có thể thực hiện các bước sau:

• Khởi tạo một Stack rỗng.
• Đưa các kí tự của chuỗi vào Stack.
• Lấy các kí tự từ Stack theo thứ tự ngược lại để tạo thành một chuỗi mới.
• So sánh chuỗi mới với chuỗi ban đầu. Nếu hai chuỗi giống nhau, chuỗi ban đầu là Palindrome.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX_LENGTH 100

struct Stack {

int top;

char data[MAX_LENGTH];

};

void push(struct Stack *stack, char c) {

if (stack->top < MAX_LENGTH - 1) {

stack->top++;

stack->data[stack->top] = c;

} else {

printf("Stack Overflow.\n");

exit(1);

}

}

char pop(struct Stack *stack) {

if (stack->top >= 0) {

char c = stack->data[stack->top];

stack->top--;

return c;

} else {

printf("Stack Underflow.\n");

exit(1);

}

}

int isPalindrome(char *str) {

struct Stack stack;

stack.top = -1;

int n = strlen(str);

for (int i = 0; i < n; i++) {

push(&stack, str[i]);

}

char reversedStr[MAX_LENGTH];

for (int i = 0; i < n; i++) {

reversedStr[i] = pop(&stack);

}

reversedStr[n] = '\0';

if (strcmp(str, reversedStr) == 0) {

return 1;

} else {

return 0;

}

}

int main() {

//test with palindrome

char str1[] = "racecar";

printf("%s is Palindrome: %d \n", str1, isPalindrome(str1)); //test case 1

char str2[] = "level";

printf("%s is Palindrome: %d \n", str2, isPalindrome(str2)); //test case 2

char str3[] = "dad";//"deified";

printf("%s is Palindrome: %d \n", str3, isPalindrome(str3));

char str4[] = "madam";

printf("%s is Palindrome: %d \n", str4, isPalindrome(str4));

//test with non-palindrome

char str5[] = "abcdef";

printf("%s is Palindrome: %d \n", str5, isPalindrome(str5)); //test case 5

return 0;

}