学步园

// test.cpp : Defines the entry point for the console application.
//

/**数据结构练习*/  
#include "stdafx.h"
#include "stdlib.h"
#include "stdio.h"
#include <iostream>  
#include <stack>  
#include <vector>  
#include "string"
using namespace std;  
string a,b;  
stack<char> build;  
vector<char> save;//容器，相当于动态数组  
int len;  
void dfs(int in,int out)///出入站的个数  
{  
	if(in==len&&out==len)  
	{  
		for(int i=0;i<save.size();i++)  
			cout<<save[i]<<" ";
		cout<<"\n";  
	}  
	if(in<len)  
	{  
		build.push(a[in]);  
		save.push_back('i');  
		dfs(in+1,out);   // 深度优先进行遍历
		build.pop();     // 深度优先返回以后，恢复原状态
		save.pop_back();  
	}  
	if(out<in&&out<len&&build.top()==b[out]) // 深度优先返回后，进行其他情况考虑，就是考虑出栈  
	{  
		char _s=build.top();build.pop();  
		save.push_back('o');dfs(in,out+1);  
		build.push(_s);save.pop_back();  
	}  
} 


int _tmain(int argc, _TCHAR* argv[])
{
	while(cin>>a>>b)  
	{  
		len=a.length();  
		cout<<"["<<"\n";  
		dfs(0,0);  
		cout<<"]"<<"\n";  
	}  
}