啊哈算法——回文串(栈)

题目链接

描述：

“xyzyx”是一个回文字符串，所谓回文字符串就是指正读反读均相同的字符序列，如“席主席”、“记书记”、“aha”和“ahaha”均是回文，但“ahah”不是回文。输入一行字符（仅包含小写英文字母a~z）请判断这行字符串是否为回文。

输入格式：

只有一行，仅包含小写英文字母a~z的字符串，长度小于等于100。

输出格式：

只有一行，如果是回文请输出YES，不是回文则输出NO，请注意大小写。

输入样例1：

ahah

输出样例1：

NO

输入样例2：

ahaha

输出样例2：

YES

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    char s[105];
    gets(s);
    stack<char> head;
    stack<char> read;
    for(int i=0,j=strlen(s)-1;i<strlen(s);i++,j--){
        head.push(s[i]);//将元素放入栈底 
        read.push(s[j]);
    }
    int flag = 1;
    for(int i=0;i<strlen(s)/2;i++){
        char h = head.top();//输出栈顶元素 
        char r = read.top();
        head.pop();//删除栈顶元素 
        read.pop();
        if(h==r){
            flag = 1;
        }
        else{
            flag = 0;
            break;
        }
    }
    if(flag==1){
        printf("YES");
    }
    else{
        printf("NO");
    }
    return 0;
}

解析：

判断输入的字符串是否是回文串，将字符串分别头和尾将字符串压入两个栈。定义变量flag初始化为1，判断一个元素时，当字符串为1时，返回YES。循环遍历分别从头和尾进行比较字符串中的字符，循环次数为字符串长度除2。