Question

如果进栈顺序为A,B,C和D,则可能的出栈序列是?不求答案，求编程解决问题的代码。 求高手指教！

Answer 1

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

#define N (4) //N>1

char in_str[N+1] = "ABCD";
int count = 0;

//对[start,n)区间进行全排列
void Permunation(char *in_str,int start,int n);

//注意，由于出栈序列个数为C(2n,n)/(n+1)，故若n较大时，count计数会出错，并且该程序在短时间内无法完成！
int main(void)
{
Permunation(in_str,0,N);
printf("总共%d种出栈序列\n",count);
return 0;
}

//是否为正确的出栈序列，排除错误序列——假定入栈序列为p1,p2,p3,p4，则错误序列中含有pi,pj,pk满足
//以下条件：pj < pk < pi,如出栈序列中含有p4 p2 p3(不要求pi,pj,pk连续)
//这里的p1,p2,p3,p4对应的是入栈顺序，如A-1,B-2,C-3,D-4,这里字符ABCD刚好满足这种大小关系故可以不增加入栈顺序数组
int IsPopLiner(const char *pop_str)
{
int len = strlen(pop_str);
int i,j,big1,big2;
for(i = 1; i < len - 1; ++i)
{
big1 = i;
for(j = 0; j < i; ++j) //选出i前比pop_str[i]大的最大元素
if(pop_str[j] > pop_str[big1])
big1 = j;
if(big1 != i) //i前存在比pop_str[i]大的元素
{
big2 = i;
int one = 1;
for(j = i + 1; j < len; ++j) //找出i后比pop_str[i]大的最小元素
if(one && pop_str[j] > pop_str[i])
{
one = 0;
big2 = j;
}
else if(pop_str[j] > pop_str[i] && pop_str[j] < pop_str[big2])
big2 = j;
if(big2 != i)
{
if(pop_str[i] < pop_str[big2] && pop_str[big2] < pop_str[big1])
return 0;
}
}
}
return 1;
}

//对[start,n)区间进行全排列
void Permunation(char *in_str,int start,int n)
{
int temp;
if(start == n)
{
if(IsPopLiner(in_str)) //是正确的出栈序列
{
printf("%s\n",in_str);
++count;
}
return;
}
//全排列时，每个元素都可以放到起始位置
for(int i = start; i < n; ++i)
{
if(i != start) //减少自身交换
{
temp = in_str[start];
in_str[start] = in_str[i];
in_str[i] = temp;
}
//对剩余序列进行全排列
Permunation(in_str,start + 1, n);
//回溯
if(i != start) //减少自身交换
{
temp = in_str[start];
in_str[start] = in_str[i];
in_str[i] = temp;
}
}
}

//另一种方法就是用递归进行模拟入栈出栈情况!,你自己想吧，谢谢！

Answer 2

#include<iostream>
using namespace std;

int n=4;
string s="abcd";
//全局变量是非常危险的事情。
void fn(int a,int b,int data1[],int result1[])
{
//a是栈中元素的个数，b是还未入栈的元素的个数。
int result[4];//记录路径。
int data[4];//记录栈中的元素。
memcpy(data,data1,4*sizeof(int));
memcpy(result,result1,4*sizeof(int));
if(b==0)
{
//打印结果。
while(result[b])
{
cout<<s[result[b++]-1];
}
for(int i=a-1;i>=0;i--)
{
cout<<s[data[i]-1];
}
cout<<endl;
}
else
{
data[a]=n-b+1;
a++;
b--;
fn(a,b,data,result);

a--;
b++;//恢复数据。
data[a]=0;
if(a>0&&b!=0)
{
result[n-a-b]=data[a-1];
data[a-1]=0;
a--;
fn(a,b,data,result);
}
}
}

int main()
{
int data[4]={0};
int result[4]={0};
fn(0,4,data,result);
return 0;
}

dcba
cdba
cbda
cbad
bdca
bcda
bcad
badc
bacd
adcb
acdb
acbd
abdc
abcd
请按任意键继续. . .

Answer 3

编程啊？这一般都是选择题的啊