栈的应用——判断字符是否为逆串

要求

写一算法，识别一次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。

其中序列1和序列2中都不包含字符‘&’且序列2时序列1的逆序列。
例如，‘a+b&b+a’是属于该模式的字符序列，而‘1+3&3-1’则不是。

判断输入的字符串中‘&’前和‘&’后的部分是否为逆串，是则返回1，否则返回0。

思路

=>STEP1：将字符串输入到str1中，判断字符是否有效。
判断无效时服从三点要求：1.字符串内有‘@’。2.字符串内有‘&’。3.‘@’在‘&’后面。

/*-------输入字符串------*/
while(1){   
    cin>>s;
/*-------判断合理性------*/
    while(s[i]!=NULL){
        if(s[i]=='&'){
            yes_and=1;
            before=i;}
        else if(s[j]=='@'){
                yes_end=1;
                after=j;}
        i++;
        j++;
    }

    if(yes_and==1 && yes_end==1&& after>before){
        yes=1;break;}else{
            cout<<"错误。请输入字符串，以@键结束。"<<endl;
        i=0;
        j=0;}
}
        i=0;

=>STEP2：将str1中字符串分割为单个字符。将每个字符压入栈a内。

/*-------输入字符串------*/
    cin>>s;

/*-------判断字符串长度------*/
    while(s[i]!='@'){
        i++;
        lenth=i;
    }

/*-------创建栈a与栈b-----*/
    arrStack<string> a(i);
    arrStack<string> b(i);
    a.clear();
    b.clear();
    i=0;

/*-------将字符串压入栈a------*/
    while(i!=lenth){
        a.push(s[i]);
        i++;
    }

=>STEP3:使栈a中字符‘&’以上的内容出栈并进入b中。
此时b中元素为字符‘&’后元素的倒叙，即只需要判断b中元素是否等于a中元素，即可判读该字符串是否为逆串。

    while(aMember[0]!='&'){
    a.pop(aMember);
    b.push(aMember[0]);
    }
    b.pop(bMember);

=>STEP4:判断栈a元素是否等于栈b元素。

/*-------判断栈a与栈b是否相同------*/
    while (alenth!=0&&blenth!=0){
        if (aMember!=bMember){
            testtrue=-1;break;}
        else if(alenth!=blenth){
            testtrue=-1;break;}
        a.pop(aMember);
        b.pop(bMember);
        a.getlenth(alenth);
        b.getlenth(blenth);
    }
    

    if(testtrue==-1){
        out=1;
        cout<<out<<"不相等"<<endl;}
    else{
        out=0;
        cout<<out<<"相等"<<endl;}
}

程序与运算结果

#include <iostream>
#include <stdio.h>
#include <string>  

using namespace std;

template <class T>

class arrStack{
private:
    int mSize;
    int top;
    T *st;

public:
    arrStack(int size){
        mSize=size;
        top=-1;
        st=new T[mSize];
    }

    ~arrStack(){
        delete[]st;
    }

    void clear(){
        top=-1;
    }

    void push(char &item){
        if(top == mSize - 1){
            cout << "stack is full, cannot push element!" << endl;
            return;
        }
        else{
            st[++top]=item;
        }
    }

    void pop(string &m){
        if(top == -1){
            cout << "empty" << endl;
        }
        else{
            m=st[top--];
        }
    }

    void getop(string &t){
        if(top ==-1){
            cout<<"empty!"<<endl;
        }
        else{
            t=st[top];
            cout<<"获得栈顶元素："<<t<<endl;
        }
    }

    void getlenth(int &m){
        m=top+1;
    }

};


void clear(){
    int i=0;
    int j=0;
    int before=0;
    int after=0;
    int lenth;//lenth
    int testtrue=0; 
    int alenth=2;
    int blenth=2;
    int n=0;
    int yes_and=0;
    int yes_end=0;
    int yes;
    int out;
    string s;
    string aMember;
    string bMember;
}

void start(){
int lenth;//lenth
    int i=0;
    int j=0;
    int before=0;
    int after=0;
    int testtrue=0; 
    int alenth=2;
    int blenth=2;
    int n=0;
    int yes_and=0;
    int yes_end=0;
    int yes;
    int out;
    string s;
    string aMember;
    string bMember;

/*-------输入字符串------*/


while(1){   
    cin>>s;

    while(s[i]!=NULL){
        if(s[i]=='&'){
            yes_and=1;
            before=i;}
        else if(s[j]=='@'){
                yes_end=1;
                after=j;}
        i++;
        j++;
    }


    if(yes_and==1 && yes_end==1&& after>before){
        yes=1;break;}else{
            cout<<"错误。请输入字符串，以@键结束。"<<endl;
        i=0;
        j=0;}
}
        i=0;

                    

/*-------判断字符串长度------*/
    while(s[i]!='@'){
        i++;
        lenth=i;
    }

/*-------创建栈a与栈b-----*/
    arrStack<string> a(i);
    arrStack<string> b(i);
    a.clear();
    b.clear();
    i=0;

/*-------将字符串压入栈a------*/
    while(i!=lenth){
        a.push(s[i]);
        i++;
    }


/*-------将a中元素压入栈b，以符号&结束------*/
    while(aMember[0]!='&'){
    a.pop(aMember);
    b.push(aMember[0]);
    }
    b.pop(bMember);



/*-------判断栈a与栈b是否相同------*/
    while (alenth!=0&&blenth!=0){
        if (aMember!=bMember){
            testtrue=-1;break;}
        else if(alenth!=blenth){
            testtrue=-1;break;}
        a.pop(aMember);
        b.pop(bMember);
        a.getlenth(alenth);
        b.getlenth(blenth);
    }
    

    if(testtrue==-1){
        out=1;
        cout<<out<<"不相等"<<endl;}
    else{
        out=0;
        cout<<out<<"相等"<<endl;}
}

int main(){

    int n=0;
    cout<<"欢迎使用。"<<endl;
    while(1){
    clear();
    cout<<"请输入字符串，以@键结束。"<<endl;
    start();
    }
    system("pause");
    return 0;
}

Paste_Image.png

总结

程序运行结果比较好。
最重要的问题时觉得自己写的程序有点邋遢，不够简洁。
比如说判断输入字符是否合理时，我定义了after、before、i、j、yes_end，yes_and等等变量。或许会有更简洁的方法，以后我会学习优化。