Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

Need a start point for resolving {[()]}

by exilepanda (Pilgrim)
on Jun 13, 2013 at 04:37 UTC ( #1038666=perlquestion: print w/replies, xml ) Need Help??
exilepanda has asked for the wisdom of the Perl Monks concerning the following question:

Hi monks, I am working in a project in helping colleges to do logic check from batch of Excel files. Staffs will write a sort of simple syntax (still designing) within a INI file; basically the so called syntax(expression) are some and or eq etc. operators with {[()]}. , which will return a true or false.

The first problem come to me is how do I resolve those brackets, so I can determine the logic's precedence. Now I have this :

$expr = '(A&(B&C)|((C&D)|\((A EQ 1)))'; # 01234567890123456789012345678 my (@open, @close); my @charArr = split //, $expr; foreach my $pos ( 0..$#charArr ) { push @open, $pos if ( $charArr[$pos] =~ /\(/ && $charArr[$pos-1] n +e "\\" ) ; push @close, $pos if ( $charArr[$pos] =~ /\)/ && $charArr[$pos-1] +ne "\\" ) ; } die "Imbalance Pair" unless @open == @close; print "@open$/@close$/$/"; my @preced; foreach my $firstClose ( @close ) { my @temp = (); while ( @open ) { my $lastOpen = pop @open; if ( $lastOpen < $firstClose ) { push @preced, "$lastOpen - $firstClose"; @open = (@open, @temp); last } else { unshift @temp, $lastOpen; } } } print $_.$/ foreach @preced; __END__ prints: 0 3 9 10 18 7 14 25 26 27 3 - 7 10 - 14 18 - 25 9 - 26 0 - 27

The @preced carries the string positions of each open-end brackets, and their precedence order. However, it looks like a stupid algorithm, which sound unsafe and not efficient.

My questions :

1. What is the terminology of this sort of issues ? I like to look up more, but I don't know what is it called

2. Is there any module actually suits for this kind of case? What I have only a start up, implementing each block is another issue, if more operators are needed later, like >= == != boolean, string compare etc. situations. I can't foresee what's gonna happen.

Any clues for me ? Thanks in advance.

Replies are listed 'Best First'.
Re: Need a start point for resolving {[()]}
by hdb (Monsignor) on Jun 13, 2013 at 07:21 UTC

    This piece of code could be a starting point. Also look at Re: Convert Tcl Keyed List to Perl where I use the same technique in a different context.

    # node 1030367 use strict; use warnings; my $expr = '(A&(B&C)|((C&D)|\((A EQ 1)))'; my $level = 0; my $tab = "| "; my %action = ( '(' => sub { print "\n", $tab x ++$level, shift }, ')' => sub { print "\n", $tab x $level--, shift }, 'default' => sub { print shift }, ); ( $action{$_} // $action{'default'} )->($_) for $expr =~ /./g;
      Wow! This inspires a lot, by level shifting and tabbing! A very nice start point! Looks much more neat and firm. Thanks for the lead!
Re: Need a start point for resolving {[()]}
by Skeeve (Vicar) on Jun 13, 2013 at 06:45 UTC
      Finally!! Lexing and Parsing. I know where to really start now!! BIG THANKS!! XD
Re: Need a start point for resolving {[()]}
by Anonymous Monk on Jun 13, 2013 at 06:35 UTC
      Thank you very much for the valuable references, and there's so many approaches out there! I'd really have no idea on how to search these threads by myself. Thanks for the pointers!

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1038666]
Approved by davido
Front-paged by Corion
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (11)
As of 2017-10-19 16:50 GMT
Find Nodes?
    Voting Booth?
    My fridge is mostly full of:

    Results (255 votes). Check out past polls.