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
D
<lang d>import std.stdio, std.algorithm, std.string,
std.range, std.random, std.conv;
auto generate(int n) {
return text(map!((i){ return "[]"[uniform(0,2)]; })(iota(n)));
}
void main() {
foreach (i; 0 .. 14) {
auto s = generate(i);
writefln("%-15s is%s balanced", '"' ~ s ~ '"',
s.balancedParens('[', ']') ? "" : " not");
}
}</lang> Output:
"" is balanced "[" is not balanced "][" is not balanced "[]]" is not balanced "][][" is not balanced "][][]" is not balanced "[[[]][" is not balanced "[]][[[]" is not balanced "][][][[]" is not balanced "][]][][[]" is not balanced "[]][[]][[]" is not balanced "][[]]][]]][" is not balanced "[[]][[[[]]]]" is balanced "[[]][][]]]][[" is not balanced
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 ("%-22r is%s balanced" % (txt, if balanced(txt) else ' not')) ... is balanced '[]' is balanced '[][]' is balanced '][[[]]' is not balanced '[]][[][]' is not balanced '[][[][]]][' is not balanced '][]][][[]][[' is not balanced '[[]]]]][]][[[[' is not balanced '[[[[]][]]][[][]]' is balanced '][[][[]]][]]][[[[]' is not balanced</lang>
Tcl
<lang tcl>proc balanced s {
set n 0
foreach c [split $s ""] {
# Everything unmatched is ignored, which is what we want switch -exact -- $c { "\[" {incr n} "\]" {if {[incr n -1] < 0} {return false}} }
}
expr {!$n}
}</lang> Demonstration code: <lang tcl>foreach s {"" "[]" "][" "[][]" "][][" "[[][]]" "[]][[]"} {
puts "$s\t-> [expr {[balanced $s] ? {OK} : {NOT OK}}]"
}</lang> Output:
-> OK [] -> OK ][ -> NOT OK [][] -> OK ][][ -> NOT OK [[][]] -> OK []][[] -> NOT OK