Train Problem I

時(shí)間限制：3000?ms ?|? 內(nèi)存限制：65535?KB 難度：2 描述

As the new term comes, the Ignatius Train Station is very busy nowadays. A lot of student want to get back to school by train(because the trains in the Ignatius Train Station is the fastest all over the world ^v^). But here comes a problem, there is only one railway where all the trains stop. So all the trains come in from one side and get out from the other side. For this problem, if train A gets into the railway first, and then train B gets into the railway before train A leaves, train A can't leave until train B leaves. The pictures below figure out the problem. Now the problem for you is, there are at most 9 trains in the station, all the trains has an ID(numbered from 1 to n), the trains get into the railway in an order O1, your task is to determine whether the trains can get out in an order O2.
輸入

The input contains several test cases. Each test case consists of an integer, the number of trains, and two strings, the order of the trains come in:O1, and the order of the trains leave:O2. The input is terminated by the end of file. More details in the Sample Input.

輸出

The output contains a string "No." if you can't exchange O2 to O1, or you should output a line contains "Yes.", and then output your way in exchanging the order(you should output "in" for a train getting into the railway, and "out" for a train getting out of the railway). Print a line contains "FINISH" after each test case. More details in the Sample Output.

樣例輸入

3 123 321 3 123 312

樣例輸出

Yes. in in in out out out FINISH No. FINISH

題意：給出兩個(gè)字符串，問(wèn)第一個(gè)字符串能否經(jīng)過(guò)棧轉(zhuǎn)化為第二個(gè)字符串。?如果可以，輸出進(jìn)棧和出棧的順序。

? ? ? 這是一個(gè)關(guān)于棧的問(wèn)題。棧是允許在同一端進(jìn)行插入和刪除操作的特殊線性表。允許進(jìn)行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動(dòng)；棧中元素個(gè)數(shù)為零時(shí)稱為空棧。插入一般稱為進(jìn)棧（PUSH），刪除則稱為退棧（POP）。棧也稱為后進(jìn)先出表。

#include<stdio.h> #include<string.h> #include<stack> /*定義棧*/ using namespace std; /*千萬(wàn)不要忘記*/ int main() {int n,i,j,k,flag[20];char s1[10],s2[10];stack<char> s;while(~scanf("%d%s %s",&n,s1,s2)){memset(flag,-1,sizeof(flag));j=k=0;for(i=0;i<n;i++){s.push(s1[i]);flag[k++]=1; /*1為進(jìn)棧，in*/while(!s.empty()&&s.top()==s2[j]) /*棧非空且棧頂元素與s2中的元素相等*/{flag[k++]=0; /*0為出棧，out*/s.pop(); /*清除棧頂元素*/j++; /*與s2中的下一個(gè)元素比較*/}}if(j==n) /*可以轉(zhuǎn)換*/{printf("Yes.\n");for(i=0;i<k;i++){if(flag[i]) /*flag[i]==1*/printf("in\n");elseprintf("out\n");}printf("FINISH\n");}else /*不能轉(zhuǎn)換*/printf("No.\nFINISH\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的NYOJ 150 Train Problem I STL栈的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。