CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

Home: Perl Programming Help: Intermediate:
Matching brackets

 



zapzap
User

Nov 29, 2013, 3:47 PM

Post #1 of 10 (4384 views)
Matching brackets Can't Post

Greetings,

I have a string s = '[[][]]'

How would I go about making sure all the brackets are closed 'properly'

Something like '[[][[[]' is not considered closed properly

I think I need a recursive type regex. I looked up turning off backtracking but I think that feature may have been removed, (besides I didn't really understand it anyway).




Code
My approach: 

my $str2 = '[][[]';
my $str3 = "[[1,2,4],['words','dog'],[],[]]";

sub closedBrackets {
$_ = shift;
while( 1 ) {
my $index1 = rindex($_,'[');
my $index2 = index($_,']',$index1);
return 1 if ($index1 < 0 && $index2 < 0);
return if ($index1 > 0 && $index2 < 0) || ($index1 < 0 && $index2 > 0);
$_ = substr($_,0,$index1) . substr($_,$index2+1);
}
}

closedBrackets($str2) ? print $str2 . " ok\n" : print $str2 . " NOT ok\n";
closedBrackets($str3) ? print $str3 . " ok\n" : print $str3 . " NOT ok\n";


There should be a much nicer approach, more concise, possibly soleley with a regex?


Laurent_R
Veteran / Moderator

Nov 30, 2013, 10:23 AM

Post #2 of 10 (4375 views)
Re: [zapzap] Matching brackets [In reply to] Can't Post

Well, it is possible, but notoriously difficult to check for balancing parens or brackets with regexes.

I would suggest that you simply count the opening and the closing brackets and check that the numbers match. This approach, however, would not detect an error in something like this:

Code
[]][

If you want to detect this as an error, then set a counter to 0, read your data, increment the counter for any opening bracket, decrement it for every closing bracket, and report an error if the counter ever becomes negative or if it is not zero at the end.


FishMonger
Veteran / Moderator

Nov 30, 2013, 11:20 AM

Post #3 of 10 (4370 views)
Re: [zapzap] Matching brackets [In reply to] Can't Post

Take a look at the Regexp::Common::balanced module.
http://search.cpan.org/~abigail/Regexp-Common-2013031301/lib/Regexp/Common/balanced.pm


zapzap
User

Dec 1, 2013, 11:29 AM

Post #4 of 10 (4325 views)
Re: [Laurent_R] Matching brackets [In reply to] Can't Post

Thanx, you gave me an idea


Code
my $str = '[helow [] ] []'; 

sub isBalanced {
my $balanced = 0;
for (split(//,shift)) {
$balanced++ if /\[/;
$balanced-- if /\]/;
return if $balanced < 0;
}
$balanced == 0 ? return 1 : return;
}


print "Balanced\n" if isBalanced($str);
print "Not Balanced\n" if not isBalanced($str);


What if we also monitored for a closing bracket as well, and if there are more closing brackets then opening brackets at any moment an error is thrown. This check in addition to the check at the end for '0' would do the trick....Agree,disagree. I think we would now be able to catch unbalanced brackets?
Thanks again for your help. I kind of knew the regex approach would be difficult. I doubt I would even like to try.

###############

Thanks FishMonger for pointing out of the Regex module. I'll check it out. So many modules, so so many.

Thank you again,
zap


Lastly, is my previous approach any good. It doesn't seem Perlish in my opinion. Can somebody help modify my code (or even my new code ) so that it hints of a 'Perl' veteran.


Kenosis
User

Dec 1, 2013, 1:19 PM

Post #5 of 10 (4312 views)
Re: [zapzap] Matching brackets [In reply to] Can't Post

Both of your routines say that '[[ ][[ ]]]' is balanced. The r/l brackets are, but it's not well-formed.


Laurent_R
Veteran / Moderator

Dec 2, 2013, 8:52 AM

Post #6 of 10 (4232 views)
Re: [Kenosis] Matching brackets [In reply to] Can't Post

They are balanced, and that's what the OP wanted to figure out. Well-formed or not? well, it depends for what purpose, they may very well be well-formed in some contexts, and not in others.


Kenosis
User

Dec 2, 2013, 10:43 AM

Post #7 of 10 (4224 views)
Re: [Laurent_R] Matching brackets [In reply to] Can't Post

Being well-formed, i.e., properly nested, is implicit in all of the OP's examples. That qualification also merely paraphrases your earlier statement about the "error" (read "not well-formed") in "[]]["--unless, of course, "[]][" "...may very well be well-formed in some contexts, and not in other." However, if "[]][" is well-formed "in some contexts," then its instance not categorically an error.


(This post was edited by Kenosis on Dec 2, 2013, 10:44 AM)


zapzap
User

Dec 2, 2013, 2:24 PM

Post #8 of 10 (4207 views)
Re: [Kenosis] Matching brackets [In reply to] Can't Post

Well-formed? Defining well-formed is difficult.

My original post stated:

Code
I have a string s = '[[][]]' 

How would I go about making sure all the brackets are closed 'properly'

Something like '[[][[[]' is not considered closed properly


Notice -- 'properly'

Nevertheless,
Thanks for everyones' comments and suggestions because I know at the 'root' of it all we all strive to help each other. Again, thank you everyone


Kenosis
User

Dec 2, 2013, 4:38 PM

Post #9 of 10 (4199 views)
Re: [zapzap] Matching brackets [In reply to] Can't Post


Quote
Defining well-formed is difficult.

Your excellent examples clearly exemplify an operational definition of "well-formed," in this case. The notions of "nesting" and "proper closure" can be included as necessary conditions in a stipulative definition of "well-formed."

I don't think defining "well-formed" is difficult here. The difficulty comes in creating an effective parsing engine that tests for this "well-formedness."


zapzap
User

Dec 3, 2013, 4:34 PM

Post #10 of 10 (4175 views)
Re: [Kenosis] Matching brackets [In reply to] Can't Post

Thank you. I strive to give quality examples. Ambiguity is a nemisis. You brought up the notion of well-formed.

For some reason you decided to point out:
'Both of your routines say that '[[ ][[ ]]]' is balanced. The r/l brackets are, but it's not well-formed. '

From the onset, my quest was to make sure the brackets were closed 'properly'. I explicitly quoted properly because many may debate what properly means. I gave examples of my quest in hopes of clarifying any misunderstanding.

You also stated:

The notions of "nesting" and "proper closure" can be included as necessary conditions in a stipulative definition of "well-formed."

This is true. However, just because something can be included does not mean it should be included.

Lastly, I gave examples of what my quest was and for some reason you brought up how my results where not well-formed. I sought for the brackets to be closed 'properly' and 'properly' may not be equivalent to 'well-formed'.

In any case, thank you for your comments. Thank you to everyone.
Until the next time
zap

 
 


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives