栈的应用
View Code
1 /* 2 栈 3 */ 4 #include<stdio.h> 5 #include<string.h> 6 #include<stdlib.h> 7 #include<algorithm> 8 #include<iostream> 9 #include<queue> 10 #include<stack> 11 //#include<map> 12 #include<math.h> 13 using namespace std; 14 typedef long long ll; 15 //typedef __int64 int64; 16 const int maxn = 1005; 17 const int inf = 0x7fffffff; 18 const double pi=acos(-1.0); 19 const double eps = 1e-8; 20 char in[ maxn ],out[ maxn ]; 21 stack<int>mys; 22 int ans[ maxn ]; 23 int main(){ 24 int n; 25 while( scanf("%d",&n)!=EOF ){ 26 scanf("%s%s",in,out); 27 if( n==1 ){ 28 if( in[0]==out[0] ){ 29 printf("Yes.\n"); 30 printf("in\nout\n"); 31 printf("FINISH\n"); 32 continue; 33 } 34 printf("No.\n"); 35 printf("FINISH\n"); 36 continue; 37 } 38 while( !mys.empty() ) mys.pop();//mys.clear(); 39 int cnt=0; 40 int pos=0; 41 int ans_pos=0; 42 for( int i=0;i<n;i++ ){ 43 if( mys.empty() ){ 44 mys.push( in[ i ]-'0' ); 45 ans[ ans_pos++ ]=1; 46 }//火车进站 47 else if( mys.top()==(out[ pos ]-'0') ){ 48 while( !mys.empty()&&mys.top()==(out[ pos ]-'0') ){ 49 mys.pop(); 50 pos++; 51 cnt++; 52 ans[ ans_pos++ ]=-1; 53 } 54 i--; 55 }//火车出站 56 else { 57 mys.push( in[i]-'0' ); 58 ans[ ans_pos++ ]=1; 59 } 60 }//火车进站，这时候没火车出去 61 while( !mys.empty()&&mys.top()==(out[ pos ]-'0') ){ 62 mys.pop(); 63 pos++; 64 cnt++; 65 ans[ ans_pos++ ]=-1; 66 } 67 if( cnt==n ){ 68 printf("Yes.\n"); 69 for( int i=0;i<ans_pos;i++ ) 70 if( ans[i]==1 ) 71 printf("in\n"); 72 else 73 printf("out\n"); 74 } 75 else 76 printf("No.\n"); 77 printf("FINISH\n"); 78 } 79 return 0; 80 }