原理：DFS
代码语言：javascript复制#include<iostream>
#include<string>
#include<stack>
using namespace std;
string a,b;//用来存每组字符串的第一个和第二个
int sum;//用来存每组需要的操作数目（等于第一组字符串长度的二倍）
//深度优先搜索函数，六个参数分别为，
//第一个字符串（初始字符串），第二个字符串（目标字符串），中间栈，
//出栈组成字符串，用来存放出入栈的字符数组，执行到当前的出入栈操作综合
void dfs(string a,string b,stack<char>temp,string now,char flag[100],int num)
{
//当出栈组成的字符串和目标字符串相同的时候，达到退出条件。
if(now == b)
{
for(int i = 0;i < num;i )
{
cout << flag[i] << " ";
}
cout << endl;
return 0;
}
//减支，去掉不需要的数据
if(num > sum)
{
return 0;
}
string test;
string test_now = now;
char flag_test[100];
//判断能否压栈
if(a != "")
{
//压栈
temp.push(a[0]);
flag[num] = 'i';
test.assign(a,1,a.length() - 1);
}
for(int j = 0;j <= 99;j )
{
flag_test[j] = flag[j];
}
//压栈分支
if(a != "")
{
dfs(test,b,temp,test_now,flag_test,num 1);
if(!temp.empty())
{
temp.pop();
}
}
//出栈分支
if((!temp.empty())&&b[now.size()] == temp.top())
{
flag[num] = 'o';
string now_test = now temp.top();
char testt = temp.top();
if(!temp.empty())
{
temp.pop();
}
dfs(a,b,temp,now_test,flag,num 1);
temp.push(testt);
}
}
int main()
{
while(cin >> a >> b)
{
string sumstring[10000] = {""};
sum = 2*a.size()-1;//记录此组数据最大出入栈操作数总和
char flag[100];
string c="";
stack<char>temp;
cout<<"["<<endl;//规范输出格式
dfs(a,b,temp,c,flag,0);
cout<<"]"<<endl;
}
}
