Generating all strings is probably a dead end as the number of strings
is exponential in n and n can be up to 19.
This can be solved as a DP with no counting.
Your grammar is not useful because it's ambiguous. An LL grammar is S
= <empty> | [ S ] S .
However to enumerate, even the LL grammar is not so useful.
Below is a simple enumerator. Call it with b(0, 0, n);
char buf[100];
int b(int p, int open, int remaining)
{
if (open == 0 && remaining == 0)
printf("%.*s\n", p, buf);
else {
if (open > 0) {
buf[p] = ']';
b(p + 1, open - 1, remaining);
}
if (remaining > 0) {
buf[p] = '[';
b(p + 1, open + 1, remaining - 1);
}
}
}
On Sep 16, 11:12 am, "mc2 ." <[email protected]> wrote:
> Hey guys,
>
> I have the following grammar :
> S -> S{S}S or null
>
> i want to generate 2n number of brackets using this grammar. I gave it a try
> but my program is going out of stack.Could someone please help me code this
> grammar?
>
>
>
> On Fri, Sep 16, 2011 at 7:11 PM, mc2 . <[email protected]> wrote:
> > thanks a lot gene. :)
>
> > On Fri, Sep 16, 2011 at 7:00 PM, Gene <[email protected]> wrote:
>
> >> I'll do the 5th example. A proper bracket expression of size n has n
> >> ['s and n ]'s and every prefix has no more ]'s than ['s.
>
> >> Test case 5 is n = 4 k = 2, so the possible bracket expressions are
>
> >> [][][][] *
> >> [][][[]]
> >> [][[]][]
> >> [][[][]]
> >> [][[[]]]
> >> [[]][][] *
> >> [[]][[]]
> >> [[][]][]
> >> [[][][]]
> >> [[][[]]]
> >> [[[]]][]
> >> [[[]][]]
> >> [[[][]]]
> >> [[[[]]]]
>
> >> I have put *'s after the two cases that have [ at positions 5 and 7
> >> (with 1-based indexes).
>
> >> So the answer is 2.
>
> >> On Sep 16, 8:46 am, "mc2 ." <[email protected]> wrote:
> >> > Hey guys,
>
> >> > i am trying to solve this problem :http://www.spoj.pl/problems/SQRBR/
>
> >> > But i can't decipher the problem what it is asking for . Could someone
> >> > please give test cases for input set 4 and 5?
> >> > What does proper proper bracket expressions mean in these cases?
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to [email protected].
> >> To unsubscribe from this group, send email to
> >> [email protected].
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
