栈的基本应用(一)：对称字符串的检测

要求：

输入一个带“&”的字符串，判断“&”前和“&”后部分是否为逆串。

思路：

依次读入字符串中的每个字符，当未读到“&”时，将每个读入的字符入栈保存。读入“&”后与栈顶字符比较，若相同，则出栈继续读下一个字符直到读取所有符号，否则不满足要求，停止读取。

#include <bits/stdc++.h>
using namespace std;

class SeqStack
{
public:
    SeqStack(int cnt);
    bool pop(); //出栈
    bool push(char num); //压栈
    bool isFull();
    bool isEmpty();
    int getLength(); //取栈的长度
    char getTop()
    { return *(p+top); }
    void show();
    void empty()
    { top = bottom; }
    ~SeqStack()
    {
        delete [] p;
    }
private:
    int top; //栈顶位置
    int bottom; //栈底位置，此处不存放有效值
    char * p; //顺序栈数组的首地址
    int cnt; //顺序栈的最大长度
};

SeqStack::SeqStack(int cnt)
{
    p = new char[cnt+1]();
    bottom = top = 0;
    this->cnt = cnt;
}

bool SeqStack::isEmpty()
{
    if (bottom == top)
        return true;
    else
        return false;
}

bool SeqStack::isFull()
{
    if (top == cnt)
        return true;
    else
        return false;
}

int SeqStack::getLength()
{
    return top;
}

bool SeqStack::push(char newChar)
{
    if (this->isFull())
    {
        cout<<"顺序栈已满，无法压栈！"<<endl;
        return false;
    }
    top++;
    *(p+top) = newChar;
    return true;
}

bool SeqStack::pop()
{
    if (this->isEmpty())
    {
        cout<<"顺序栈为空，无法出栈！"<<endl;
        return false;
    }
    top--;
    return true;
}

void SeqStack::show()
{
    if (this->isEmpty())
    {
        cout<<"顺序栈为空，无法遍历！"<<endl;
        return;
    }
    for (int i = 1; i<=top; i++)
    {
        printf("%c ",*(p+i));
    }
    printf("\n");
}

int main()
{
    cout<<"请输入一行含有\'&\'的字符串："<<endl;
    string str;
    cin>>str;
    SeqStack stack((int)str.length()/2); //栈的大小只需要字符串长度的一半
    int i; //便于遍历str串中的字符
    for (i = 0; str[i] != '&'; i++)
    {
        if( stack.isFull() ) //当&前串的长度大于&后串的长度时，肯定不关于&对称
        {
            cout<<"字符串不关于\'&\'对称或输入的字符串不含\'&\'！"<<endl;
            return 0;
        }
        stack.push(str[i]); //将&前的字符进行压栈操作
    }
    for (i++; str[i] == stack.getTop() && !stack.isEmpty(); i++)
        //判断栈顶的值与遍历的字符是否一致，若一致，则出栈直到栈为空（对称），否则终止循环（不对称）
    {
        stack.pop();
    }
    if ( stack.isEmpty() )
        cout<<"字符串关于\'&\'对称！"<<endl;
    else
        cout<<"字符串不关于\'&\'对称！"<<endl;
    return 0;
}

测试结果如下：