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

要求:

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

思路:

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

#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;
}

测试结果如下:



发表评论

电子邮件地址不会被公开。 必填项已用*标注