要求
写一算法，识别一次读入的一个以@为结束符的字符序列是否为形如‘序列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等等变量。或许会有更简洁的方法，以后我会学习优化。
