这题是栈的模拟问题。
要求的就是输入序列能否用栈转化后变成输出序列。
要注意的是并不一定要输入序列完全进栈后再逐个出栈。显然的嘛,否则也太简单了吧。
比如数据4 1234 2134 也可。
流程如此:1进栈,不出。2进栈,出栈。此时3不能急于进栈,要先让1出栈。3入栈,3出栈。4入栈,4出栈。
AC代码:有注释的
#include<iostream> #include<stack> using namespace std; int main() { int n,i,j,k; char in[10],out[10],tmp; bool flag[20],flag1; stack<char> s; while(cin>>n) { while(!s.empty()) //如果上一次为NO,说明栈未出完,这次用需要清空 s.pop(); cin>>in>>out; j=k=0; flag1=true; for(i=0;i<n;i++) { if(flag1) { s.push(in[i]); flag[k++]=true; } tmp=s.top(); if(tmp==out[j]) { s.pop(); j++; flag[k++]=false; if(!s.empty()) { flag1=false; //如果有车出栈,并且栈不空,则不能让车出栈 i--; //此时占顶的车也有可能是需要出栈的,比如1234 2134 } //2进栈之后就可出栈,此时不能让3进栈,要让1出栈 else flag1=true; //如果栈为空,肯定要车进栈了 } else flag1=true; //如果当前没有车可以出栈,下列车可以进栈 } flag1=false; while(!s.empty()) //如果此时栈不空,说明能是Yes的情况是进栈与出栈序列完全为反 { tmp=s.top(); if(tmp==out[j]) { s.pop(); j++; flag[k++]=false; } else //只要中间有一个不满足,即可断定不满足了 { flag1=true; break; } } if(flag1) cout<<"No."<<endl; else { cout<<"Yes."<<endl; for(i=0;i<2*n;i++) { if(flag[i]) cout<<"in"; else cout<<"out"; cout<<endl; } } cout<<"FINISH"<<endl; } return 0; }