题目大意就是给你两个单词,比如madam,adamm要你用堆栈的形式转换成第二个单词,Push用i表示,pop用o表示。
我用的是dfs,但出栈条件s->top==r[po]看不懂
#include <string>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
stack<char> s;
vector<char> op;//存储指令
string o,r;//源单词和目标单词
int len;
void dfs(int ph,int po)//ph是push次数,po是pop次数
{
if(ph==len&&po==len)
{
for(vector<char>::iterator it=op.begin();it!=op.end();it++)
cout<<*it<<" ";
cout<<endl;
}
else
{
if(ph<len)
{
s.push(o[ph]);
op.push_back('i');
dfs(ph+1,po);
s.pop();
op.pop_back();
}
if(!s.empty()&&s.top()==r[po])//&&后面这个看不懂为什么
{
char tmp=s.top();
s.pop();
op.push_back('o');
dfs(ph,po+1);
s.push(tmp);
op.pop_back();
}
}
}
int main()
{
while(cin>>o>>r)
{
len=int(o.length());
cout<<"["<<endl;
dfs(0,0);
cout<<"]"<<endl;
op.clear();
}
return 0;
}