Anagrams by Stack

ZOJ Problem Set - 1004 Anagrams by Stack

题目:来源

#include <iostream>
#include<cstring>
using namespace std;
#define N 100
char source[100];//原word
char target[100];//目标word
char pop_push[200];//栈操作序列
char stackf[100];//保存栈中栈中当前情况
char out[100];//保存生成word
void Search(int n,int p)//递归出所有的进栈出栈操作
{
    if(p==2*n)//边界条件
    {
        int i=0,s=0,f=0,o=0;//s指向当前要进栈的字母,f指向栈顶,o指向out中当前可放位置
        for (;i!=p;++i)
        {
            if(pop_push[i]=='i')
            {
                if(s==n)
                    break;//不合法的进栈,跳出
                stackf[f++]=source[s++];
            }
            else
            {
                if(f==0)
                    break;//不合法的出栈,跳出
                out[o++]=stackf[--f];
            }
        }
        out[o]='\0';
        if(strcmp(target,out)==0)
        {
            int i;
            for (i=0;i!=p;++i)//输出
                cout << pop_push[i] << " ";
            cout << endl;
        }
        return ;
    }
    pop_push[p++]='i';//首先进栈
    Search(n,p);//递归到下一层
    pop_push[p-1]='o';//退回,改成出栈
    Search(n,p);//下一层
}
int main()
{
    while (cin >> source >> target)
    {
        int n=strlen(source);
        cout << "[" << endl;
        Search(n,0);
        cout << "]" << endl;
    }
    return 0;
}

递归出所有栈操作,排除不合法的。找到满足条件的操作序列。

Comments