一道小题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道小题

一道小题# JobHunting - 待字闺中

r*u2010-01-06 08:01

1 楼

Develop an algorithm to find out all valid combinations of n brackets. Like
for n =3 possible combinations can be ((())) or ()()() or (()()) and so on
这个就是用个stack放'(', 然后有个output array, 如果stack不空，output这个位置
可以放'('或)，如果stack空就只能放'('还有遇到（。push it to stack，遇到)，pop
。然后递归，对吧。我code了一下怎么都不对，有没有谁给个code我能参考一下，谢谢
！

v*u2010-01-06 08:01

2 楼

int n=3;
char stk[100];
void printlegal( int ipos, int ileft, int iright)
{
if (ipos==2*n-1)
{
stk[ipos]=')';
for (int i=0; iprintf("%c", stk[i]);
printf("\n");
}else if (ileft==iright)
{
stk[ipos] = '(';
printlegal( ipos+1, ileft-1, iright );
}else if (ileft==0)
{
stk[ipos] = ')';
printlegal( ipos+1, i

【在 r**u 的大作中提到】

: Develop an algorithm to find out all valid combinations of n brackets. Like
: for n =3 possible combinations can be ((())) or ()()() or (()()) and so on
: 这个就是用个stack放'(', 然后有个output array, 如果stack不空，output这个位置
: 可以放'('或)，如果stack空就只能放'('还有遇到（。push it to stack，遇到)，pop
: 。然后递归，对吧。我code了一下怎么都不对，有没有谁给个code我能参考一下，谢谢
: ！

k*e2010-01-06 08:01

3 楼

it is similar to Catalan number but a little different in the recursive relation.
can solve it using dynamic programming in time n^2 time.

Like
pop

【在 r**u 的大作中提到】

c*n2010-01-06 08:01

4 楼

用recursive容易很多啊
void comb(int l,int r, char *result,int size){
//printf("%d, %d, %s\n",l,r,result);
if(l==0 && r==0){
printf("%s\n",result);
return;
}
if(l==r){
strcat(result,"(");
comb(l-1,r,result,size);
}
else if(lif(l>0 && r>0){
char *result1=calloc(size,1);
strcpy(result1,result);
strcat(r

【在 r**u 的大作中提到】

r*u2010-01-06 08:01

5 楼

谢谢。你和vincexu的思路一样，我思路跑偏了。你的code我有一个小小疑问，你这个
放结果的string，size总是3啊，但是最后结果的length是6，这是不是有点问题？

【在 c*********n 的大作中提到】

: 用recursive容易很多啊
: void comb(int l,int r, char *result,int size){
: //printf("%d, %d, %s\n",l,r,result);
: if(l==0 && r==0){
: printf("%s\n",result);
: return;
: }
: if(l==r){
: strcat(result,"(");
: comb(l-1,r,result,size);

c*n2010-01-06 08:01

6 楼

啊对。。。这个是大问题，memory leak了，谢谢提醒

【在 r**u 的大作中提到】

: 谢谢。你和vincexu的思路一样，我思路跑偏了。你的code我有一个小小疑问，你这个
: 放结果的string，size总是3啊，但是最后结果的length是6，这是不是有点问题？