Balanced brackets: Difference between revisions

From Rosetta Code
Content added Content deleted
(→‎{{header|Python}}: Assumes balance must be maintained for given string.)
(→‎{{header|Python}}: Task asks for a generator too!)
Line 55: Line 55:


=={{header|Python}}==
=={{header|Python}}==

<lang python>>>> def balanced(txt):
<lang python>>>> def gen(N):
... txt = ['['] * N + [']'] * N
... random.shuffle( txt )
... return ''.join(txt)
...
>>> def balanced(txt):
... braced = 0
... braced = 0
... for ch in txt:
... for ch in txt:
Line 64: Line 70:
... return braced == 0
... return braced == 0
...
...
>>> for txt in ',[],[][],[[][]],][,][][,[]][[],[[][]['.split(','):
>>> for txt in (gen(N) for N in range(10)):
... print ("%r is%s balanced" % (txt, '' if balanced(txt) else ' not'))
... print ("%r is%s balanced" % (txt, '' if balanced(txt) else ' not'))
...
...
'' is balanced
'' is balanced
'[]' is balanced
'[][]' is balanced
'[[][]]' is balanced
'][' is not balanced
'][' is not balanced
'][][' is not balanced
'[][]' is balanced
'[]][[]' is not balanced
'[[]]][' is not balanced
'[[][][' is not balanced</lang>
'][[[][]]' is not balanced
'][[[][]]][' is not balanced
'][[]][][][][' is not balanced
'][[]]]][[[][[]' is not balanced
'[[[]][]][][]][[]' is not balanced
'[[[[[][[[]][]]]]]]' is balanced</lang>

Revision as of 13:36, 20 February 2011

Task
Balanced brackets
You are encouraged to solve this task according to the task description, using any language you may know.

Problem: Generate a string with $N opening brackets ("[") and $N closing brackets ("]"), in some arbitrary order. Determine whether the string is balanced; that is, whether it consists entirely of pairs of opening/closing brackets (in that order), none of which mis-nest.

Examples:

   (empty)   OK
   []        OK   ][        NOT OK
   [][]      OK   ][][      NOT OK
   [[][]]    OK   []][[]    NOT OK

Perl 6

<lang perl6>sub balanced($s) {

   my $l = 0;
   for $s.comb {
       when "]" {
           --$l;
           return False if $l < 0;
       }
       when "[" {
           ++$l;
       }
   }
   return $l == 0;

}

my $N = get; my $s = (<[ ]> xx $N).pick(*).join; say "$s {balanced($s) ?? "is" !! "is not"} well-balanced"</lang>

PureBasic

<lang PureBasic>Procedure Balanced(String$)

 Protected *p.Character, cnt
 *p=@String$
 While *p\c
   If *p\c='['
     cnt+1
   ElseIf *p\c=']'
     cnt-1
   EndIf
   If cnt<0: Break: EndIf
   *p+SizeOf(Character)
 Wend
 If cnt=0
   ProcedureReturn #True
 EndIf

EndProcedure</lang> Testing the procedure <lang PureBasic>Debug Balanced("")  ; #true Debug Balanced("[]")  ; #true Debug Balanced("][")  ; #false Debug Balanced("[][]")  ; #true Debug Balanced("][][")  ; #false Debug Balanced("[[][]]")  ; #true Debug Balanced("[]][[]")  ; #false</lang>

Python

<lang python>>>> def gen(N): ... txt = ['['] * N + [']'] * N ... random.shuffle( txt ) ... return .join(txt) ... >>> def balanced(txt): ... braced = 0 ... for ch in txt: ... if ch == '[': braced += 1 ... if ch == ']': ... braced -= 1 ... if braced < 0: return False ... return braced == 0 ... >>> for txt in (gen(N) for N in range(10)): ... print ("%r is%s balanced" % (txt, if balanced(txt) else ' not')) ... is balanced '][' is not balanced '[][]' is balanced '[[]]][' is not balanced '][[[][]]' is not balanced '][[[][]]][' is not balanced '][[]][][][][' is not balanced '][[]]]][[[][[]' is not balanced '[[[]][]][][]][[]' is not balanced '[[[[[][[[]][]]]]]]' is balanced</lang>