Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1095545
  • 博文数量: 242
  • 博客积分: 10209
  • 博客等级: 上将
  • 技术积分: 3028
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 09:27
文章分类

全部博文(242)

文章存档

2014年(1)

2013年(1)

2010年(51)

2009年(65)

2008年(124)

我的朋友

分类: C/C++

2010-09-15 23:12:42

问题:Write a function Brackets(int n) that prints all combinations of well-
formed brackets. For Brackets(3) the output would be ((())) (()()) (())
() ()(()) ()()()

解答:You can approach this the same way you'd do it by hand.  Build up the
string of brackets left to right.  For each position, you have a
decision of either ( or ) bracket except for two constraints:
(1) if you've already decided to use n left brackets, then you can't
use a another left bracket and
(2) if you've already used as many right as left brackets, then you
can't use another right one.

This suggests the following alorithm. Showing what happens on the
stack is a silly activity.

#include

// Buffer for strings of ().
char buf[1000];

// Continue the printing of bracket strings.
//   need is the number of ('s still needed in our string.
//   open is tne number of ('s already used _without_ a matching ).
//   tail is the buffer location to place the next ) or (.
void cont(int need, int open, int tail)
{
 // If nothing needed or open, we're done.  Print.
 if (need == 0 && open == 0) {
   printf("%s\n", buf);
   return;
 }

 // If still a need for (, add a ( and continue.
 if (need > 0) {
   buf[tail] = '(';
   cont(need - 1, open + 1, tail + 1);
 }

 // If still an open (, add a ) and continue.
 if (open > 0) {
   buf[tail] = ')';
   cont(need, open - 1, tail + 1);
 }
}

void Brackets(int n)
{
 cont(n, 0, 0);
}

int main(void)
{
 Brackets(3);
 return 0;
}
阅读(1540) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~