#!/usr/bin/perl
use strict;
use warnings;

use File::Basename;

=head1 QUEST

    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.  For example,
    given the argument '3', the program should print these five lines:

           ((()))
           (()())
           (())()
           ()(())
           ()()()

    in some order.  (The order is not important.)  

    For the argument '1'; the output should be:
           
           ()

    and for argument '4', the output should be:

           (((())))
           ((()()))
           ((())())
           ((()))()
           (()(()))
           (()()())
           (()())()
           (())(())
           (())()()
           ()((()))
           ()(()())
           ()(())()
           ()()(())
           ()()()()

    in some order.

=cut


main();
exit;


sub next_parenthesis ($$) {
    my ($is, $n) = @_;
    my @np;

    my $open  = () = $is =~ m/\(/g;
    my $close = () = $is =~ m/\)/g;

    push @np, '(' if $open < $n;
    push @np, ')' if $close < $open;

    return @np;
}


sub main {
    my $n = $ARGV[0];

    die "syntax: ", basename($0),
        " N\n\twhere N is a natural number (number of pairs of parenthesis)\n"
        unless defined $n and $n > 0;

    my @output = ('');

    for my $position (1 .. 2*$n) {
        my @output2;

        for my $is (@output) {
            push @output2, "$is$_" for next_parenthesis($is, $n);
        }
        @output = @output2;
    }

    printf "%3d: %s\n", $_+1, $output[$_] for 0.. $#output;
}