[SPOILER] QotW 23

Bruce J Keeler <[email protected]> Fri, 03 Sep 2004 23:59:19 -0700

Newsgroups	gmane.comp.lang.perl.qotw.discuss
Message-ID	<[email protected]>

My first inclination was to try to avoid recursion, as it can be
expensive in Perl.  Also, I rather liked the checker that was posted and
how it operated (by repeatedly doing s/\(\)//g), so I thought I might
try to see if I could make it work in reverse, so to speak. 
Unfortunately, my algorithm produced a lot of dupes, so I had to use a
hash to filter them out.  Combined with the @pipeline array, this was
both slow and memory-wasteful.  This is the program 'parens', below.

'parens2' was a completely different approach.  It scales well
memory-wise, and doesn't really do any work that it doesn't need to
algorithm-wise.  It is, however, recursive.

I got the notion of reimplementing it in C, just for the heck of it. 
It's way fast; I think it's probably about as fast as it can get.

Bruce

parens (application/x-perl, 495 B) - not displayed

parens2 (application/x-perl, 461 B) - not displayed

parens.c (text/x-csrc, 893 B)

#include <stdlib.h>
#include <stdio.h>

int n;
char *buf;

void fooblicate(register int opens, register int closes)
{
    if (opens > 0) {
        buf[n - opens - closes] = '(';
        fooblicate(opens - 1, closes);
    }
    if (closes > opens) {
        if (closes == 1) {
            buf[n - 1] = ')';
            write(1, buf, n + 1);
            return;
        }
        buf[n - opens - closes] = ')';
        fooblicate(opens, closes - 1);
    }
}

main(int argc, char **argv) {
    if (argc < 2) {
        fprintf(stderr, "Usage: %s <n>\n", argv[0]);
        exit(1);
    }
    n = atoi(argv[1]);
    if (n < 1) {
        fprintf(stderr, "Usage: %s <n>\n", argv[0]);
        exit(1);
    }
    n *= 2;
    buf = malloc(n + 1);
    if (buf == NULL) {
        fprintf(stderr, "malloc failed\n");
        exit(3);
    }
    buf[n] = '\n';
    fooblicate(n / 2, n / 2);
    return 0;
}