给一个源字符串和一个目标字符串,让你找到所有可能的入栈出栈操作序列,使得源字符串经过这些序列的操作得到目标字符串。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4
#include<iostream> #include<cstdio> #include<vector> #include<string> #include<algorithm> #include<stack> using namespace std; string st1,st2; vector<vector<char> > ops; vector<char> op; stack<char> st; int s1; int s2; void solve() { if ( s2==st2.size() &&st.empty()) { ops.push_back(op); } if (s1 <st1.size() ) { st.push(st1[s1++]); op.push_back('i'); solve(); st.pop(); s1--; op.pop_back(); } if (!st.empty()) { if ( st.top() == st2[s2]) { char c=st.top(); st.pop(); op.push_back('o'); s2++; solve(); s2--; op.pop_back(); st.push(c); } } } int main() { while(getline(cin,st1)) { getline(cin,st2); ops.clear(); op.clear(); if ( st1.size()==0 ) { printf("[\n]\n"); continue; } string tmp1=st1,tmp2=st2; sort(tmp1.begin(),tmp1.end()); sort(tmp2.begin(),tmp2.end()); if ( tmp1.compare(tmp2)!=0) { printf("[\n]\n"); continue; } solve(); printf("[\n"); for(int i=0;i<ops.size();i++) { if ( ops[i].empty()) continue; //printf("%c",ops[i][0]); for(int j=0;j<ops[i].size();j++) printf("%c ",ops[i][j]); printf("\n"); } printf("]\n"); } }