C++算法实战：利用栈优雅判断回文串

C++算法实战：利用栈优雅判断回文串

回文串，即正反读都一样的字符串，例如 'level'、'madam'。本文将介绍如何使用 C++ 编写一个函数 bool pal(string str)，利用栈来判断字符串 str 是否为回文串。

核心思想：

1. 将字符串的前半部分依次入栈。2. 从字符串的后半部分开始，依次与栈顶元素比较： - 若相等，则弹出栈顶元素，继续比较下一个字符； - 若不相等，则该字符串不是回文串。3. 若比较到最后栈为空，则该字符串是回文串。

**代码实现：**cpp#include #include #include

bool pal(std::string str) { std::stack charStack; int length = str.length();

// 将字符串的前半部分入栈    for (int i = 0; i < length / 2; ++i) {        charStack.push(str[i]);    }

// 从字符串的后半部分开始比较    for (int i = (length + 1) / 2; i < length; ++i) {         if (str[i] != charStack.top()) {            return false;         }        charStack.pop();    }

return true; }

int main() { std::string str; std::cout << '请输入一个字符串: '; std::cin >> str;

bool isPalindrome = pal(str);    if (isPalindrome) {        std::cout << str << ' 是回文串。

'; } else { std::cout << str << ' 不是回文串。 '; }

return 0;}

代码解读：

1. 头文件： 引入了 iostream (输入输出)、stack (栈)、string (字符串) 头文件。2. pal 函数： - 创建一个字符栈 charStack。 - 使用循环将字符串的前半部分字符依次入栈。 - 使用循环从字符串的后半部分开始，依次与栈顶元素比较，若不相等则返回 false，否则弹出栈顶元素。 - 最后，若栈为空，则所有字符都匹配，返回 true，否则返回 false。3. main 函数： - 获取用户输入的字符串。 - 调用 pal 函数判断是否为回文串。 - 根据返回值输出相应结果。

优化技巧：

• 可以只将字符串长度的一半入栈，减少栈空间的使用。- 可以使用迭代器代替下标访问字符串，提高代码可读性。

希望本文能帮助你理解如何使用C++和栈来判断回文串，提升你的算法能力！