#include <iostream>
#include <cctype> // 用于字符处理函数
using namespace std;

const int MAX_SIZE = 100; // 最大栈容量

// 使用数组模拟栈结构
char stack[MAX_SIZE]; // 字符栈数组
int top = -1;         // 栈顶指针，-1表示空栈

// 入栈函数
void push(char c) {
    if (top < MAX_SIZE - 1) { // 检查栈是否已满
        top++;                // 栈顶上移
        stack[top] = c;       // 存入字符
    }
}

// 出栈函数
char pop() {
    if (top >= 0) {           // 检查栈是否为空
        char c = stack[top];  // 取出栈顶字符
        top--;                // 栈顶下移
        return c;             // 返回取出的字符
    }
    return '\0'; // 栈为空时返回空字符
}

// 检查栈是否为空
bool isEmpty() {
    return top == -1; // 栈顶为-1表示空栈
}

// 回文判断函数
bool isPalindrome(string str) {
    // 重置栈，确保每次调用都是干净的
    top = -1;
    
    string cleanStr = ""; // 存储处理后的纯净字符串
    
    // 第一步：预处理字符串
    // 去掉非字母字符，并统一转为小写
    for (int i = 0; i < str.length(); i++) {
        char c = str[i];
        
        // 如果是字母字符
        if (isalpha(c)) {
            // 转换为小写
            char lowerC = tolower(c);
            // 添加到纯净字符串
            cleanStr += lowerC;
            // 同时压入栈中
            push(lowerC);
        }
    }
    
    // 第二步：检查是否是回文
    // 将栈中字符弹出，与纯净字符串比较
    for (int i = 0; i < cleanStr.length(); i++) {
        char originalChar = cleanStr[i]; // 原字符串中的字符
        char stackChar = pop();           // 从栈中弹出的字符
        
        // 如果字符不匹配，不是回文
        if (originalChar != stackChar) {
            return false;
        }
    }
    
    // 所有字符都匹配，是回文
    return true;
}

int main() {
    // 测试不同的字符串
    cout << "回文判断演示：" << endl;
    cout << "=============" << endl;
    
    string test1 = "racecar";
    cout << "\"" << test1 << "\" ";
    if (isPalindrome(test1)) {
        cout << "✅ 是回文" << endl;
    } else {
        cout << "❌ 不是回文" << endl;
    }
    
    string test2 = "A man a plan a canal Panama";
    cout << "\"" << test2 << "\" ";
    if (isPalindrome(test2)) {
        cout << "✅ 是回文" << endl;
    } else {
        cout << "❌ 不是回文" << endl;
    }
    
    string test3 = "hello";
    cout << "\"" << test3 << "\" ";
    if (isPalindrome(test3)) {
        cout << "✅ 是回文" << endl;
    } else {
        cout << "❌ 不是回文" << endl;
    }
    
    string test4 = "Was it a car or a cat I saw?";
    cout << "\"" << test4 << "\" ";
    if (isPalindrome(test4)) {
        cout << "✅ 是回文" << endl;
    } else {
        cout << "❌ 不是回文" << endl;
    }
    
    // 让小朋友可以自己输入测试
    cout << endl << "你想自己试试吗？输入一个字符串: ";
    string userInput;
    getline(cin, userInput);
    
    cout << "\"" << userInput << "\" ";
    if (isPalindrome(userInput)) {
        cout << "✅ 是回文！" << endl;
    } else {
        cout << "❌ 不是回文" << endl;
    }
    
    return 0;
}

代码解析（用小朋友能懂的语言）

1. 什么是回文？ 回文就是正着读和倒着读都一样的词语或句子！ 例子： • "racecar" → 正读：racecar，反读：racecar ✅ • "hello" → 正读：hello，反读：olleh ❌ • "A man a plan a canal Panama" → 忽略空格大小写后是回文 ✅
2. 使用栈判断回文的原理 想象栈就像一叠字母卡片： • 我们把字符串的每个字母按顺序放到卡片上 • 然后从最上面开始把卡片拿下来 • 这样拿下来的顺序就是反过来的 判断方法： • 如果正序和反序的字母都一样，就是回文！ • 如果有一个字母不一样，就不是回文
3. 程序执行步骤 第一步：清理字符串 text 原始: "A man, a plan..." 清理: 去掉逗号、空格、问号... 结果: "amanaplan..." 同时: 所有字母转成小写 第二步：使用栈反转 text 把清理后的字符串压入栈中： a → m → a → n → a → p → l → a → n ...

从栈中弹出（反转顺序）： n ← a ← l ← p ← a ← n ← a ← m ← a 第三步：比较 text 原字符串: a m a n a p l a n ... 反转字符串: n a l p a n a m a ... 逐个比较：❌ 发现不匹配！ 4. 为什么用栈？ 因为栈的后进先出特性正好能帮我们把字符串反转！ • 入栈顺序：第一个字母在栈底，最后一个字母在栈顶 • 出栈顺序：最后一个字母先出来，第一个字母最后出来 • 效果：出来的顺序正好是原字符串的反转