ZOJ 1004 Anagrams by Stack

ZOJ 1004 Anagrams by Stack

这个题很早就看到了，但是当时关于栈没有很好的运用，而且还需要用递归所以就放过了。。今天重拾这个题，感觉应付起来很轻松，可能是因为进步了吧，嘿嘿。。1A~

i代表入栈操作，o代表弹出，对于一个字符串，从第一个字符开始，进行一系列的栈操作，问有没有可能出栈的字符可以按顺序组成另外一个字符串。ok函数表示得到的io操作是否能得到另外一个串。

#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<cstring>

using namespace std;
string START,END;
int CountI,CountO;
char IO[500];
int ok(void)
{
    stack<char> S;
    string result;
    int i,in = 0;
    for( i = 0; i < 2*END.length(); i++ )
    {
        if( IO[i] == 'i' )
            S.push(START[in++]);
        else
            result.append( 1,S.top() ),S.pop();
    }
    if( END == result ) return 1;
    else return 0;
}
void GeneIO( int x ,int CountI,int CountO )
{
    int i;
    if( x == 2*END.length() )
    {
        if( CountI - CountO ) return;
        if( ok() )
        {
            for( i = 0; i < 2*END.length(); i++ )
                cout << IO[i] << ' ';
            cout << endl;
        }
        return;
    }
    if( CountI > CountO )
    {
        IO[x] = 'i';
        GeneIO( x + 1 ,CountI + 1,CountO );
        IO[x] = 'o';
        GeneIO( x + 1 ,CountI,CountO + 1 );
    }
    else if( CountI == CountO )
    {
        IO[x] = 'i';
        GeneIO( x + 1 ,CountI + 1,CountO );
    }
}

int main(void)
{
    
    while( cin >> START >> END )
    {
        if( START.length() != END.length() )
        {
            cout << '[' << endl << ']' << endl;
            continue;
        }
        cout << '[' << endl;
        GeneIO(0,0,0);
        cout << ']' << endl;
    }    
    return 0;
}