问题: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) |