zoj1004

解题思路：本题讲述的是让你输入两个字符串序列，判断能否通过对第一个字符串进行进栈出栈操作得到第二个字符串，若能则输出所有能达到的进出栈操作过程。我通过全排列每得到一组操作过程，则用函数按照这个操作过程，判断能否得到第二个字符串，若能则表明此操作过程可行，输出。

#include<stdio.h>

#include<string.h>
int n,n1,n2; //总操作数，进栈操作数，出栈操作数
char in[1000]; //第一个输入的字符串，/***被操作字符串***/
char ou[1000]; //第二个输入字符串，/*需判断能否经操作字符串操作后得到的字符串*/
char reu[1000];
int judge(int len) //判断两个字符串是否含有相同种类和个数的字符
{
int i;
char ch1[26]={0},ch2[26]={0};
for(i=0;i<len;i++)
{
ch1[in[i]-'a']=ch1[in[i]-'a']+1; //统计第一个字符串中不同种类字符串的个数和种类
ch2[ou[i]-'a']=ch2[ou[i]-'a']+1;
}
if(strcmp(ch1,ch2)==0) //判断函数
return 1;
return 0;
}
int caozuo()
{
int i,j,k,t;
char ch[1000];
for(i=0,j=0,k=0,t=0;i<n;i++)
{
if(reu[i]=='i') //进栈操作
{
ch[j]=in[k];
j++;
k++;
}
else
{
if(ch[j-1]==ou[t]) //出栈时判断是否和需判断序列一致
{
j--;
t++;
}
else
return 0; //判断不成立，返回不成立
}
}
return 1;
}
void full_permutation(int L)
{ 
int i;
if (n1==0&&n2==0) //当进栈出栈数都没有时，及全部都用于操作以后
{ 
if(caozuo()) //调用操作函数按照得到的操作过程进行操作，并判断
{
for(i=0;i<n;i++)
printf("%c ",reu[i]); //当前操作可以，输出当前操作序列
printf("\n");
}
return;
}
if(n1>0)
{
reu[L]='i'; //在l位置放上进栈操作
n1--;
full_permutation(L+1); //填下一个位置
n1++;
}
if(n2>n1) //剩余的进栈操作是否少于出栈操作，即表明当前如果进行出栈操作，栈里面还有字符，操作合法
{
reu[L]='o'; //在l位置放上出栈操作
n2--;
full_permutation(L+1); //填下一个位置
n2++;
}
}
int main()
{
while(scanf("%s",in)!=EOF) //输入字符串
{
getchar(); //吸收回车符
gets(ou); //输入第二个字符串
printf("[\n"); 
int len1,len2;
len1=strlen(in); //求字符串的长度
len2=strlen(ou);
if(len1==len2) //如果两个字符串长度不一致那可以肯定绝对不行
{ 
if(judge(len1)) //调用函数，判断两个字符串所含字符种类，个数是否一致，原因如上条解释
{
n=len1*2; //因为一个字符有进出栈两个操作，所以操作数是字符串长度的两倍
n1=len1; //得到进栈操作数
n2=len1; 
full_permutation(0);//操作全排列
}
}
printf("]\n");
}
return 0;
}