#!/usr/bin/perl
use warnings;
use strict;
use Switch;
use Data::Dumper::Simple;
use Parse::RecDescent;


# read input symbol by symbol.
# whenever you find a [ or (, push it onto the stack.
# whenever you find a } or }, it must be pulled off the stack.
# if you can't ever pull it off, reject
# if you end with stuff in the stack, reject
sub paren_1{
  my $input = shift;
  my @stack;
  foreach (split(//,$input)) {
    if ($_ =~ /\[|\(/) {
      push(@stack,$_);
    } elsif ($_ eq "]") {
      return unless @stack;
      return 0 unless pop(@stack) eq "[";
    } elsif ($_ eq ")") {
      return unless @stack;
      return 0 unless pop(@stack) eq "(";
    } else {
      return;
    }    
  }
  return 0 if scalar @stack;
  return 1;
}

sub paren_2{
  my $input = shift;
  return 1 unless $input;
  # the Parser incorrectly dosn't like ''. Allow it anyway.
  my $grammar = q{
    start:  nest(s) 

    nest:   "(" nest(s?) ")"
          | "[" nest(s?) "]"
    }; 
  my $parser = Parse::RecDescent->new($grammar);
  return $parser->start($input);
}


use Test::More qw(no_plan);

foreach("[[[]]]",
	"(((((((())))))))",
	"((([[[[(((())[][][[]]))[[]]]]]])))",
	"[[(())]]",
	"[()()[[]][][][][]()(())]",
	"[[[(()[][][[([[([][]()())[]][]][[]])]()])][]][]]",
	"(([[(([[(()())[]][]]())())[]][]]())())",
	"",
       ) {
  ok( paren_1($_),"Paren_1 match $_");
  ok( paren_2($_),"Paren_2 match $_");

}
foreach("((]]))]]",
	"((][",
	"[()()()",
        "([[(]))]",
	"(",
	")",
	"(()",
	")(",
	"]][[][][][]]][[",) {
  ok(!paren_1($_),"Paren_1 can't match $_");
  ok(!paren_2($_),"Paren_2 can't match $_");

}


