Some people have sent email asking what the stack looks like as the
program runs. It's pretty silly to worry about this. If you really
want to know, it's easy to modify the program to print a stack
trace.
Here you go:
#include <stdio.h>
// Buffer for strings of ().
char buf[1000];
typedef struct stack_record_s {
struct stack_record_s *prev;
int need, open, tail;
} STACK_RECORD;
void dump_state(STACK_RECORD *sr)
{
int i = 0;
printf("\nstate: buf=%.*s\n", sr->tail, buf);
while (sr) {
printf("%d: need=%d, open=%d, tail=%d\n",
i++, sr->need, sr->open, sr->tail);
sr = sr->prev;
}
}
// 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(STACK_RECORD *sr)
{
// Dump the entire program state as we enter the continuation.
dump_state(sr);
// If nothing needed or open, we're done. Print.
if (sr->need == 0 && sr->open == 0) {
printf("output: %s\n", buf);
return;
}
// If still a need for (, add a ( and continue.
if (sr->need > 0) {
STACK_RECORD new_sr[1] = {{ sr, sr->need - 1, sr->open + 1, sr-
>tail + 1 }};
buf[sr->tail] = '(';
cont(new_sr);
}
// If still an open (, add a ) and continue.
if (sr->open > 0) {
STACK_RECORD new_sr[1] = {{ sr, sr->need, sr->open - 1, sr->tail +
1 }};
buf[sr->tail] = ')';
cont(new_sr);
}
}
void Brackets(int n)
{
STACK_RECORD sr[1] = {{ NULL, n, 0, 0 }};
cont(sr);
}
int main(void)
{
Brackets(3);
return 0;
}
When you run it, you get this output:
state: buf=
0: need=3, open=0, tail=0
state: buf=(
0: need=2, open=1, tail=1
1: need=3, open=0, tail=0
state: buf=((
0: need=1, open=2, tail=2
1: need=2, open=1, tail=1
2: need=3, open=0, tail=0
state: buf=(((
0: need=0, open=3, tail=3
1: need=1, open=2, tail=2
2: need=2, open=1, tail=1
3: need=3, open=0, tail=0
state: buf=((()
0: need=0, open=2, tail=4
1: need=0, open=3, tail=3
2: need=1, open=2, tail=2
3: need=2, open=1, tail=1
4: need=3, open=0, tail=0
state: buf=((())
0: need=0, open=1, tail=5
1: need=0, open=2, tail=4
2: need=0, open=3, tail=3
3: need=1, open=2, tail=2
4: need=2, open=1, tail=1
5: need=3, open=0, tail=0
state: buf=((()))
0: need=0, open=0, tail=6
1: need=0, open=1, tail=5
2: need=0, open=2, tail=4
3: need=0, open=3, tail=3
4: need=1, open=2, tail=2
5: need=2, open=1, tail=1
6: need=3, open=0, tail=0
output: ((()))
state: buf=(()
0: need=1, open=1, tail=3
1: need=1, open=2, tail=2
2: need=2, open=1, tail=1
3: need=3, open=0, tail=0
state: buf=(()(
0: need=0, open=2, tail=4
1: need=1, open=1, tail=3
2: need=1, open=2, tail=2
3: need=2, open=1, tail=1
4: need=3, open=0, tail=0
state: buf=(()()
0: need=0, open=1, tail=5
1: need=0, open=2, tail=4
2: need=1, open=1, tail=3
3: need=1, open=2, tail=2
4: need=2, open=1, tail=1
5: need=3, open=0, tail=0
state: buf=(()())
0: need=0, open=0, tail=6
1: need=0, open=1, tail=5
2: need=0, open=2, tail=4
3: need=1, open=1, tail=3
4: need=1, open=2, tail=2
5: need=2, open=1, tail=1
6: need=3, open=0, tail=0
output: (()())
state: buf=(())
0: need=1, open=0, tail=4
1: need=1, open=1, tail=3
2: need=1, open=2, tail=2
3: need=2, open=1, tail=1
4: need=3, open=0, tail=0
state: buf=(())(
0: need=0, open=1, tail=5
1: need=1, open=0, tail=4
2: need=1, open=1, tail=3
3: need=1, open=2, tail=2
4: need=2, open=1, tail=1
5: need=3, open=0, tail=0
state: buf=(())()
0: need=0, open=0, tail=6
1: need=0, open=1, tail=5
2: need=1, open=0, tail=4
3: need=1, open=1, tail=3
4: need=1, open=2, tail=2
5: need=2, open=1, tail=1
6: need=3, open=0, tail=0
output: (())()
state: buf=()
0: need=2, open=0, tail=2
1: need=2, open=1, tail=1
2: need=3, open=0, tail=0
state: buf=()(
0: need=1, open=1, tail=3
1: need=2, open=0, tail=2
2: need=2, open=1, tail=1
3: need=3, open=0, tail=0
state: buf=()((
0: need=0, open=2, tail=4
1: need=1, open=1, tail=3
2: need=2, open=0, tail=2
3: need=2, open=1, tail=1
4: need=3, open=0, tail=0
state: buf=()(()
0: need=0, open=1, tail=5
1: need=0, open=2, tail=4
2: need=1, open=1, tail=3
3: need=2, open=0, tail=2
4: need=2, open=1, tail=1
5: need=3, open=0, tail=0
state: buf=()(())
0: need=0, open=0, tail=6
1: need=0, open=1, tail=5
2: need=0, open=2, tail=4
3: need=1, open=1, tail=3
4: need=2, open=0, tail=2
5: need=2, open=1, tail=1
6: need=3, open=0, tail=0
output: ()(())
state: buf=()()
0: need=1, open=0, tail=4
1: need=1, open=1, tail=3
2: need=2, open=0, tail=2
3: need=2, open=1, tail=1
4: need=3, open=0, tail=0
state: buf=()()(
0: need=0, open=1, tail=5
1: need=1, open=0, tail=4
2: need=1, open=1, tail=3
3: need=2, open=0, tail=2
4: need=2, open=1, tail=1
5: need=3, open=0, tail=0
state: buf=()()()
0: need=0, open=0, tail=6
1: need=0, open=1, tail=5
2: need=1, open=0, tail=4
3: need=1, open=1, tail=3
4: need=2, open=0, tail=2
5: need=2, open=1, tail=1
6: need=3, open=0, tail=0
output: ()()()
On Sep 14, 12:29 pm, Gene <gene.ress...@gmail.com> wrote:
> 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 <stdio.h>
>
> // 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;
>
> }
>
> On Sep 14, 10:57 am, bittu <shashank7andr...@gmail.com> wrote:
>
>
>
> > Write a function Brackets(int n) that prints all combinations of well-
> > formed brackets. For Brackets(3) the output would be ((())) (()()) (())
> > () ()(()) ()()()
>
> > with explaination dat is at every call what is contant of stack during
> > pushing and popping- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
