Javascript also uses the 'pairs: '' and "" ... ~greg krsnadas.org
-- from Raul Miller <[email protected] to Programming forum <[email protected] date 8 October 2009 10:22 subject Re: [Jprogramming] Balanced parens On Thu, Oct 8, 2009 at 12:27 PM, Oleg Kobchenko <[email protected]> wrote: That's why it's called "finite". But when you need a stack or when you have arbitrary combinations "[(", "[((",..."[(((((((((",... etc, they are not finite. That's... That would be correct if the input sequence could be infinite in length. However, formal treatement of push down automata seems to require that the input sequence be finite. So, personally, I would not characterize pushdown automata as not being finite. Raul -- from Oleg Kobchenko <[email protected] reply-to Programming forum <[email protected] to Programming forum <[email protected] date 8 October 2009 09:27 subject Re: [Jprogramming] Balanced parens From: Raul Miller <[email protected] On Thu, Oct 8, 2009 at 7:57 AM, Dan Baronet wrote: How about using FSM (;:) here? Given the original spec, I do not think ;: will help much. All of the relevant tokens are single characters. ;: would help if some relevant tokens needed multiple characters. That's why it's called "finite". But when you need a stack or when you have arbitrary combinations "[(", "[((",..."[(((((((((",... etc, they are not finite. -- from Henry Rich <[email protected] to Programming forum <[email protected] date 7 October 2009 15:11 subject Re: [Jprogramming] Balanced parens One-pass version: pairs =. _2 ]\ '()[]{}' remnant =: (2&}.)^:(pairs e.~ 2&{.)@,/@(#~ e.&(,pairs)) balanced =: (+&(*...@#) -.&({."1 pairs))@remnant Henry Rich Henry Rich wrote: This removes inner matched pairs repeatedly and analyzes what's left. Suitable if the nesting level is not very high. Should be 3 lines. pairs =. _2 ]\ '()[]{}' remnant =: (#~ [: (+: _1&(|.!.0)) [: +./ pairs&(E."1))^:_ @ (#~ e.&(,pairs)) balanced =: ( *...@# + *...@#@(-.&({."1 pairs)) )@remnant balanced '()[]' 0 balanced '()[](' 1 balanced '()[](]' 2 Henry Rich -- from R.E. Boss <[email protected] to Programming forum <[email protected] date 7 October 2009 09:58 subject Re: [Jprogramming] Balanced parens Another try. blnc3=: 3 : 0 z=. +/1 2 3 * (0 1 2,:1 _1 0) rpl (_2 [\ '[]{}()') i."1 y z=. ((}...@])`,`,@.(*...@+{.))/ z (0:`1:`2: @.(*@<./))(,#) z ) blnc3 '[({[({})]} [({})] )]' 0 blnc3 '[({[({})]} [({})]' 1 blnc3 '[({ [({})] [({})] )]' 2 R.E. Boss -- Van: [email protected] [mailto:programming- [email protected]] Namens R.E. Boss Verzonden: woensdag 7 oktober 2009 16:45 Aan: 'Programming forum' Onderwerp: Re: [Jprogramming] Balanced parens Thanks to Schott who pointed out I misunderstood the specs. R.E. Boss -- Van: [email protected] [mailto:programming- [email protected]] Namens R.E. Boss Verzonden: woensdag 7 oktober 2009 14:42 Aan: 'Programming forum' Onderwerp: Re: [Jprogramming] Balanced parens Alternative: blnc1=: 3 : 0 z=. * +/\"1 (0 1 2,:1 _1 0) rpl (_2 [\ '[]{}()') i."1 y (((0 ~: {:) *. 0 <: <./) + 2 * 0 > <./)"1 z ) gives the desired output per paren. [t=:'[{(]{]1)}([)' [{(]{]1)}([) blnc1 t 2 1 0 so [] is unbalanced, {} has closing delimiters to come and () is balanced. R.E. Boss -- Van: [email protected] [mailto:programming- [email protected]] Namens R.E. Boss Verzonden: woensdag 7 oktober 2009 12:18 Aan: 'Programming forum' Onderwerp: Re: [Jprogramming] Balanced parens I gave an incomplete answer. rpl=:] - (-/ , 0:)@[ {~ {...@[ i. ] NB. from rpl2a in NB. http://www.jsoftware.com/pipermail/programming/2007- July/007303.html blnc0=: 3 : ' * +/"1 (0 1 2,:1 _1 0) rpl (_2[\''[]{}()'') i."1 y' blnc=: 3 : '(((0 < >./)*.0 <: <./)+ 2 * 0 > <./) blnc0 y' [t=:'[]{}()' {~ 1...@# 6 (({(][)[)] blnc\ t 1 1 1 1 2 1 1 1 1 1 so >./ blnc\ t is the ultimate answer. |: blnc0\ t 0 0 0 0 _1 0 0 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 indicates where what went wrong. R.E. Boss -- from Raul Miller <[email protected] to Programming forum <[email protected] date 7 October 2009 08:23 subject Re: [Jprogramming] Balanced parens On Wed, Oct 7, 2009 at 10:45 AM, R.E. Boss <[email protected]> wrote: Thanks to Schott who pointed out I misunderstood the specs. If incremental processing is really desirable, the data structures should include the queue of unprocessed characters and a stack of unclosed [ { ( (bill lam's suggesion.) Raul -- from bill lam <[email protected] to [email protected] date 6 October 2009 23:17 subject Re: [Jprogramming] Balanced parens On Wed, 07 Oct 2009, Chris Burke wrote: > ... I guess you can push { [ ( into stack while scanning. On seeing } ] ) pop stack and fail if the top of stack is not compatible brackets. -- regards, == GPG key 1024D/4434BAB3 2008-08-24 gpg --keyserver subkeys.pgp.net --recv-keys 4434BAB3 -- from Oleg Kobchenko <[email protected] to Programming forum <[email protected] date 6 October 2009 22:53 subject Re: [Jprogramming] Balanced parens From: Chris Burke <[email protected] How to check if a string has balanced [] {} ()? Any pair by itself is easy enough, but I want to check all three balance together, e.g. ...[(])... would fail. Assume there are no character strings. Ideally, I'd like a result of 0 = balanced 1 = balanced so far, but some closing delimiters to come 2 = unbalanced (and broken) 1. remove all non-parens 2. progressively remove "()", "[]" or "{}" while possible empty string => balanced none of ")]}" => balanced to come ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
