2018-07-28-HDOJ-1515

题目：HDOJ-1515
栈模拟，使用了深搜的思想，可以想像成一棵二叉树，左边入栈，右边出栈，即进行遍历，在条件不符合时进行剪枝即可。
代码：

#include<stdio.h>
#include<string.h>

#define N 100

char a[N]={0},b[N]={0},re[N*2]={0},stack[N]={0};
int i=0,j=0,la=0,lb=0,r=0,top=0;

void output(void)
{
    int i1,m;
    for(i1=0,m=r;i1<m;i1++)
        printf("%c ",re[i1]);
    puts("");
    return ;
}

void dfs(void)
{
    if( i<la )
    {//能入栈优先入栈，因为题目要求字典序
        stack[top++]=a[i++];
        re[r++]='i';
        dfs();
//这是为了在debug的时候看得更明了
//        stack[--top]='\0';
//        re[--r]='\0';
        --top;--r;
        --i;
    }
    if( top>0 && j<lb && stack[top-1]==b[j] )
    {
        re[r++]='o';
//        stack[--top]='\0';
        --top;
        j++;
        if(j==lb)
            output();
        else
            dfs();
//以下这行是一个关键点，在频繁的出入栈模拟之后，栈本身可能已经被
//破坏，如何还原？看一下条件分支语句是如何进来的就行了
        stack[top++]=b[--j];
//        re[--r]='\0';
        --r;
    }
    return ;
}

int main()
{
    while( scanf("%s %s",a,b)!=EOF )
    {
        la=strlen(a);
        lb=strlen(b);
        puts("[");
        if(la==lb)
        {
            i=0,j=0,r=0,top=0;
            dfs();
        }
        puts("]");
    }
    return 0;
}