C++ 栈实现回文判断：代码解析与优化

#include #define MAXSIZE 100 #define OK 1 #define ERROR 0 #define OVERFLOW -2 using namespace std; typedef struct { char *base; char *top; int stacksize; }SqStack; int InitStack(SqStack &S) {//栈初始化 S.base=new char[MAXSIZE]; if(!S.base) return OVERFLOW; S.top=S.base; S.stacksize=MAXSIZE; return OK; } int Push(SqStack &S, char e) {//入栈 if(S.top-S.base==S.stacksize) //栈满 return ERROR; *S.top=e; S.top++; return OK; } int Pop(SqStack &S) {//出栈返回栈顶元素 if(S.top==S.base) //栈空 return ERROR; S.top--; return *S.top; } int IsPalindrome(SqStack &S,char *t) {//判断栈的回文字符序列 /**begin/ int count=0; while(*t!=0) { count++; t++; } for(int i=0;i<count/2;i++) { Push(S, t[i]); } for(int i=(count+1)/2;i<count;i++) { char temp; Pop(S, temp); if(temp!=t[i]) return ERROR; } return OK; /**end/ } int main() { char t[100]; while(cin>>t&&t[0]!='0') { SqStack S; InitStack(S); if(IsPalindrome(S,t)==1) cout<<'YES'<<endl; else cout<<'NO'<<endl; } return 0; }

代码中的问题在于IsPalindrome函数的实现有误。以下是修正后的代码：

#include <iostream>
#include <cstring>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
using namespace std;
typedef struct
{
    char *base;
    char *top;
    int stacksize;
}SqStack;
int InitStack(SqStack &S)
{//栈初始化
    S.base=new char[MAXSIZE];
    if(!S.base) return OVERFLOW;
    S.top=S.base;
    S.stacksize=MAXSIZE;
    return OK;
}
int Push(SqStack &S, char e)
{//入栈
    if(S.top-S.base==S.stacksize)  //栈满
        return ERROR;
    *S.top=e;
    S.top++;
    return OK;
}
int Pop(SqStack &S)
{//出栈返回栈顶元素
    if(S.top==S.base)      //栈空
        return ERROR;
    S.top--;
    return *S.top;
}
int IsPalindrome(SqStack &S,char *t)
{//判断栈的回文字符序列
    /**************begin************/
    int count=0;
    while(*t!=0)
    {
        count++;
        t++;
    }
    for(int i=0;i<count/2;i++)
    {
        Push(S, t[i]);
    }
    for(int i=(count+1)/2;i<count;i++)
    {
        char temp;
        Pop(S, temp);
        if(temp!=t[i])
            return ERROR;
    }
    return OK;
    /**************end************/
}
int main()
{
    char t[100];
    while(cin>>t&&t[0]!='0')
    {
        SqStack S;
        InitStack(S);
        if(IsPalindrome(S,t)==1) 
            cout<<'YES'<<endl;
        else 
            cout<<'NO'<<endl;
    }
    return 0;
}

修正后的代码中，IsPalindrome函数使用栈来判断给定的字符序列是否为回文。首先将前一半的字符依次入栈，然后从后一半开始依次与栈顶元素比较，如果不相等则返回错误，如果都相等则返回正确。