logically recurse parentheses

[rsiedl]

hey monks,

anyone know of a method or module for logically recursing through parentheses?
i.e.

( ( this OR that ) AND other )

i would like to be able to pull out the inner paren statement, check for true/false, then check the outer paren statement.
potentially the statements could become complex so the above is just for example purposes.
at the moment, i'm leaning towards something like:

while (statement) {
  regex to match for inner paren's
  perform true/false test
  break out if failed and say so
  search/replace found regex in statement to nothing
}
if we get through without any failures, must mean pass

think that will work? or can you suggest a better way/improvements?

cheers, reagen

[friedo]

Parse::RecDescent is good for this sort of thing.

[Limbic~Region]

friedo,
Assuming the task is as simple as stated, then I would agree. If on the other hand, if order of operations (precedence) and associativity (left or right) is important, Parse::RecDescent is not the first tool I reach for. I have a very long an unfinished meditation I have on the back burner that goes into much greater detail. In a nutshell, I prefer Parse::Yapp if precedence and associativity are important.

[bobf]

Perhaps Text::Balanced or Regexp::Common::balanced could help? I don't know what kind of content will be in the parens or how you will test for true/false, but the modules may help with tokenizing and the order of operations. Parse::RecDescent, as friedo mentioned, may also be helpful.

[BrowserUk]

This always start out as fun, but rapidly descends(sic!) into a much harder, if not impossible regex problem once the full requirements become clear. If your post reflects your real requirements and they are not going to 'grow', you might be able to use something relatively simple like this?

This will handle white space delimited infix operators and (I think) unlimited nested parens. It will detect trivially unbalanced parens, but maybe not badly nested ones. Adding unary prefix operators shoudl be possible without to much effort.

#! perl -slw
use strict;

my $reTokenise = qr[\s*(\S+)(?:\s+((?i:and|or)))?];

sub parseExpr {
    my $expr = shift;
    my @tokens = $expr =~ m[$reTokenise]g;
    pop @tokens unless defined $tokens[ $#tokens ];
    return '[' . join( '.', @tokens ) . ']';
}

while( <DATA> ) {
    chomp;
    warn "Unbalanced parens '$_'" and next unless tr[(][] == tr[)][];
    s[ \( ( [^()]+ ) \) ]{ parseExpr( $1 ) }xe while m[[()]];
    $_ = parseExpr( $_ ) if m[\s];
    print;
}

__DATA__
((A or B)
(A) or B)
((A) or B)
A or B or C and D
( ( this OR that ) AND other )
( A or ( B and (C or D) ) or (E and F) )
(A or (B or C) or (D and E))

Output:

c:\test>junk5
Unbalanced parens '((A or B)' at c:\test\junk5.pl line 15, <DATA> line
+ 1.
Unbalanced parens '(A) or B)' at c:\test\junk5.pl line 15, <DATA> line
+ 2.
[[A].or.B]
[A.or.B.or.C.and.D]
[[this.OR.that].AND.other]
[A.or.[B.and.[C.or.D]].or.[E.and.F]]
[A.or.[B.or.C].or.[D.and.E]]

Although it looks like it simply replaces spaces with dots and parens with brackets, it does actually parse correctly and substitutes a composite token for expressions as it goes.

Modifying it to substitute the appropriate truth value for the expression is trivial, but since you don't indicate the nature of 'this', 'that' & 'other'--eg. numeric, T or F, true or false etc.--it wasn't possible to post that.

If you think it will be useful and want to pursue it further, I've had a hankering to see how far it could be taken before it turns into an mess.

[johngg]

I have a script which evolved out of this thread which built on suggestions from ikegami. It matches balanced parentheses and pulls out the nested pairs in depth first, left to right order. Here's the script

use strict;
use warnings;

my @toTest =
(
   q{Cont(ains balanced( nested Br(ack)ets )in t)he text},
   q{Con(tains i(mbalan(ced Br(ack)ets, )one c)lose missing},
   q{Contains i(mbalan(ced Br(ack)ets, )one op)en m)missing},
   q{No brackets in this string},
   q{Won)ky br(ackets in) this s(tring},
   q{More wonky br(ackets in) th)is s(tring},
   q{Just the one( leading bracket},
   q{And just th)e one trailing bracket},
   q{So(me m(ultip)le n(est(s in) thi)s o)ne},
   q{Ther(e is( mo(re) de(e)p )nes(ti(n(g i)n (mul)ti)p(l)es) he)re},
   q{Th(er(e is( mo(re) de(e)p )nes(ti(n(g i)n (mul)ti)p(l)es) he)re},
   q{Ther(e is( mo(re) de(e)p )nes(ti(n(g i)n (mul)ti)p(l)es) he)r)e},
   q{Ther(e is( mo(re) de(e)p )n(es(ti(n(g i)n (mul)ti)p(l)es) he)re},
   q{Some d((oub)le b)rackets},
   q{(Some d((oub)le b)rackets)},
   q{ab(())cde},
   q{ab(c(d)e},
   q{ab(c)d)e},
   q{ab(c)de},
);

my @memoList;
my $rxNest;
$rxNest = qr
{(?x)
   (
      \(
      [^()]*
      (?:
         (??{$rxNest})
         [^()]*
      )*
      \)
   )
   (?{ [ @{$^R}, $^N ] })
};

my $rxOnlyNested;
{
    use re q(eval);
    $rxOnlyNested = qr
    {(?x)
       (?{ [] })
       ^
       [^()]*
       (?:
          $rxNest
          [^()]*
       )+
       \z
       (?{ @memoList = @{$^R} })
    };
}

testString($_) for @toTest;

sub testString
{
    my $string = shift;
    @memoList = ();
    print qq{\nString: $string\n};
    if($string =~ /$rxOnlyNested/)
    {
        print qq{     Match succeeded\n};
        print qq{     ---------------\n};
        print qq{     Before brackets:-\n};
        print qq{       -->@{[substr $string, 0, $-[1]]}<--\n};
        print qq{     Bracket pairs:-\n};
        print qq{          $_\n} for @memoList;
        print qq{     After brackets:-\n};
        print qq{       -->@{[substr $string, $+[1]]}<--\n};
    }
    else
    {
        print qq{     Match failed\n};
    }
}

and the output

Read more... (3 kB)

I hope you can get some use out of this.

Cheers,

JohnGG

[xicheng]

Hi, I was thinking that the OP can use a loop like the following to recursively check the embedded logical relations:

  $str = '( (1 == 1) and (2 < 1) ) or (2 > 0)';
  while ($str =~ s/(\([^()]+\))/$1/ee) {
    if (not eval($1)) {
       print "error: $1\n"; 
       last;
    }
  }

or probably in another form:

  $str = '( (1 == 1) and (2 < 1) ) or (2 > 0)';
  while ($str =~ s/(\([^()]+\))/qq($1 || 0)/ee) {
       print eval($1) ? 'ok' : 'error';
       print ": $1\n";
  }

which prints:

ok: (1 == 1)
error: (2 < 1)
error: ( 1 and 0 )
ok: (2 > 0)

The problem is that it actually recursively checks every inner balanced parens even if they are after a success 'or' operator. i.e.

  $str = '( (1 == 1) or (2 < 1) ) and (2 > 0)';

This is supposed to be a success pass, but it will return: (2 < 1) in my first code snippet which I think is not what OP wanted. Just some of my thought, might be useful for OP anyway.
Regards,
Xicheng