[SPOILER] Perl Quiz of the Week #23

> Write a program, 'parens', which gets a command line argument, n',
> which is an integer.  The program should print all the
> properly-balanced strings of parentheses of length 2n.
> [...]

The program below uses "0" to indicate left parens and "1" to
indicate right parens.  This simplifies the logic inside my
head (and hopefully in the script).  Feedback welcome.

Core idea:
* Use "0" to indicate left parens and "1" for right parens.
* Step from "0000...1111" (maximal nesting) to "010101...01" (zero nesting).
* If balanced, translate to parens and print.

Advantages of zero-one:
* I find zero's and one's easier to think about than left and right parens.
* No need to backslash "\(" and "\)" in regexps.
* $x computation in &parity is simpler.

Disadvantages:
* It needs $x and y/// before printing.

----------------------\/--------BEGIN---------\/----------------------
#!/usr/bin/env perl

# Intention: MJD's QOTW #23.

# $Id: matching-parens.pl,v 1.10 2004/09/07 15:02:46 ksundar Exp ksundar $

# Core idea:
# * Use "0" to indicate left parens and "1" for right parens.
# * Step from "0000...1111" (maximal nesting) to "010101...01" (zero nesting).
# * If balanced, translate to parens and print.
#
# Advantages of zero-one:
# * I find zero's and one's easier to think about than left and right parens.
# * No need to backslash "\(" and "\)" in regexps.
# * $x computation in &parity is simpler.
#
# Disadvantages:
# * It needs $x and y/// before printing.

use 5.006; use strict; use warnings; $^W = 1;

my $N=shift;

my $x;

for ($_ = ((0 x $N) . (1 x $N)); # Maximal nesting: "0000...1111"
     ! /^(01)+11$/;              # Haven't gone past zero nesting.
     s/0(1*)1$/1 . (0 x length($1)) . 1/e   # Step along.
    ) {
    ($x=$_) =~ y/01/()/, print $x, "\n"
        if ((y/0/0/ == y/1/1/) && &parity);
} # for

exit 0;

sub parity {
    my $x;
    for (split "") {
        return 0 if ($x += $_ ? -1 : 1) < 0;
    }
    1;
} # &parity

__END__

Buggestions:
----------------------/\---------END----------/\----------------------

peace,          || Byatrayanapura: Better governance thru online taxes:
--{kr.pA}       || http://tinyurl.com/296js
-- 
"If I have not seen farther, it is because giants have stood on my shoulders."
    -- V. Guhan.  [with apologies to Newton, Sir Isaac.]