设计一个算法,判断给定字符串是否为回文,通过栈和c语言实现

为了判断一个字符串是否是回文，我们可以利用栈的数据结构来辅助实现。以下是使用C语言的一个简单算法：

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

#define MAX_SIZE 100

// 判断字符是否是小写字母或数字
bool is_valid_char(char c) {
    return (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9');
}

// 向栈顶压入字符
void push(char* stack, char c) {
    if (stack == NULL || strlen(stack) == MAX_SIZE) {
        printf("Stack overflow!\n");
        return;
    }
    stack[strlen(stack)] = c;
    stack[strlen(stack) + 1] = '\0';
}

// 弹出栈顶字符并检查是否仍为回文
char pop_and_check(char* stack) {
    if (strlen(stack) == 0) {
        printf("Stack underflow!\n");
        return '\0'; // 或者返回错误标识
    }
    char top = stack[strlen(stack) - 1];
    stack[strlen(stack) - 1] = '\0';
    return top;
}

// 主函数，判断给定字符串是否为回文
bool is_palindrome(const char* str) {
    char stack[MAX_SIZE] = {0};
    int i = 0, j = strlen(str) - 1;

    while (i < j) {
        // 只保留字母和数字字符
        if (!is_valid_char(str[i])) {
            ++i;
            continue;
        }
        if (!is_valid_char(str[j])) {
            --j;
            continue;
        }

        push(stack, str[i++]); // 将左半边字符推入栈
        pop_and_check(stack);   // 检查右半边字符是否匹配
    }

    return strlen(stack) == 0; // 如果栈为空，说明原字符串是回文
}

int main() {
    char input[50];
    printf("Enter a string: ");
    fgets(input, sizeof(input), stdin);
    input[strcspn(input, "\n")] = '\0'; // 移除换行符

    if (is_palindrome(input)) {
        printf("%s is a palindrome.\n", input);
    } else {
        printf("%s is not a palindrome.\n", input);
    }

    return 0;
}

这个程序首先创建了一个栈，并从字符串的两端开始比较字符。只有当两边都是字母或数字时才会进行操作。如果任何时候栈顶的字符与当前检查的字符不匹配，那么该字符串就不是回文。最后，如果栈完全为空，说明原始字符串是回文。