Balanced brackets: Difference between revisions
No edit summary |
|||
Line 612: | Line 612: | ||
[[][]]: true |
[[][]]: true |
||
[]][[]: false</pre> |
[]][[]: false</pre> |
||
=={{header|Objeck}}== |
|||
<lang objeck> |
|||
bundle Default { |
|||
class Balanced { |
|||
function : IsBalanced(text : String) ~ Bool { |
|||
level := 0; |
|||
each(i : text) { |
|||
character := text->Get(i); |
|||
if(character = ']') { |
|||
if(level = 0) { |
|||
return false; |
|||
}; |
|||
level -= 1; |
|||
}; |
|||
if(character = '[') { |
|||
level += 1; |
|||
}; |
|||
}; |
|||
return level = 0; |
|||
} |
|||
function : Main(args : String[]) ~ Nil { |
|||
IsBalanced("")->PrintLine(); |
|||
IsBalanced("[]")->PrintLine(); |
|||
IsBalanced("[][]")->PrintLine(); |
|||
IsBalanced("[[][]]")->PrintLine(); |
|||
IsBalanced("][")->PrintLine(); |
|||
IsBalanced("][][")->PrintLine(); |
|||
IsBalanced("[]][[]")->PrintLine(); |
|||
} |
|||
} |
|||
} |
|||
</lang> |
|||
<pre> |
|||
true |
|||
true |
|||
true |
|||
true |
|||
false |
|||
false |
|||
false |
|||
</pre> |
|||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
Revision as of 15:56, 5 March 2011
You are encouraged to solve this task according to the task description, using any language you may know.
Task:
- Generate a string with opening brackets (“
[
”) and closing brackets (“]
”), in some arbitrary order. - Determine whether the generated 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
Ada
brackets.adb: <lang Ada>with Ada.Numerics.Discrete_Random; with Ada.Text_IO; with Ada.Strings.Fixed; procedure Brackets is
package Random_Positive is new Ada.Numerics.Discrete_Random (Positive); Positive_Generator : Random_Positive.Generator; procedure Swap (Left, Right : in out Character) is Temp : constant Character := Left; begin Left := Right; Right := Temp; end Swap; function Generate_Brackets (Bracket_Count : Natural; Opening_Bracket : Character := '['; Closing_Bracket : Character := ']') return String is use Ada.Strings.Fixed; All_Brackets : String := Bracket_Count * Opening_Bracket & Bracket_Count * Closing_Bracket; begin for I in All_Brackets'Range loop Swap (All_Brackets (I), All_Brackets (Random_Positive.Random (Positive_Generator) mod (Bracket_Count * 2) + 1)); end loop; return All_Brackets; end Generate_Brackets; function Check_Brackets (Test : String; Opening_Bracket : Character := '['; Closing_Bracket : Character := ']') return Boolean is Open : Natural := 0; begin for I in Test'Range loop if Test (I) = Opening_Bracket then Open := Open + 1; elsif Test (I) = Closing_Bracket then if Open = 0 then return False; else Open := Open - 1; end if; end if; end loop; return True; end Check_Brackets;
begin
Random_Positive.Reset (Positive_Generator); Ada.Text_IO.Put_Line ("Brackets"); for I in 0 .. 4 loop for J in 0 .. I loop declare My_String : constant String := Generate_Brackets (I); begin Ada.Text_IO.Put_Line (My_String & ": " & Boolean'Image (Check_Brackets (My_String))); end; end loop; end loop;
end Brackets;</lang>
Output:
Brackets : TRUE []: TRUE ][: FALSE []][: FALSE ][][: FALSE ][][: FALSE [[]]][: FALSE [][][]: TRUE []]][[: FALSE ][][][: FALSE ]]][[[[]: FALSE [[[]][]]: TRUE [][][]][: FALSE [[][]]][: FALSE []]]][[[: FALSE
AutoHotkey
<lang AutoHotkey>; Generate 10 strings with equal left and right brackets Loop, 5 { B = %A_Index% loop 2 { String = Loop % B String .= "[`n" Loop % B String .= "]`n" Sort, String, Random StringReplace, String, String,`n,,All Example .= String " - " IsBalanced(String) "`n" } } MsgBox % Example return
IsBalanced(Str) { Loop, PARSE, Str { If A_LoopField = [ i++ Else if A_LoopField = ] i-- If i < 0 return "NOT OK" } Return "OK" }</lang> Output:
][ - NOT OK ][ - NOT OK [][] - OK [[]] - OK []][[] - NOT OK ]][[[] - NOT OK ][[]][][ - NOT OK [][[[]]] - OK [][]]][[[] - NOT OK [[][[]]][] - OK
A second example repeatedly replacing []: <lang AutoHotkey>Loop, 5 { B = %A_Index% loop 2 { String = Loop % B String .= "[`n" Loop % B String .= "]`n" Sort, String, Random StringReplace, String, String,`n,,All Example .= String " - " IsBalanced(String) "`n" } } MsgBox % Example return
IsBalanced(Str){ While (Instr(Str,"[]")) StringReplace, Str, Str,[],,All Return Str ? "False" : "True" }</lang> Sample output:
[] - True ][ - False ]][[ - False []][ - False [[]]][ - False ]][[[] - False [][]]][[ - False []][][][ - False [[[][]][]] - True [][][[[]]] - True
BASIC
<lang qbasic>DECLARE FUNCTION checkBrackets% (brackets AS STRING) DECLARE FUNCTION generator$ (length AS INTEGER)
RANDOMIZE TIMER
DO
x$ = generator$ (10) PRINT x$, IF checkBrackets(x$) THEN PRINT "OK" ELSE PRINT "NOT OK" END IF
LOOP WHILE LEN(x$)
FUNCTION checkBrackets% (brackets AS STRING)
'returns -1 (TRUE) if everything's ok, 0 (FALSE) if not DIM L0 AS INTEGER, sum AS INTEGER
FOR L0 = 1 TO LEN(brackets) SELECT CASE MID$(brackets, L0, 1) CASE "[" sum = sum + 1 CASE "]" sum = sum - 1 END SELECT IF sum < 0 THEN checkBrackets% = 0 EXIT FUNCTION END IF NEXT
IF 0 = sum THEN checkBrackets% = -1 ELSE checkBrackets% = 0 END IF
END FUNCTION
FUNCTION generator$ (length AS INTEGER)
z = INT(RND * length) IF z < 1 THEN generator$ = "": EXIT FUNCTION REDIM x(z * 2) AS STRING FOR i = 0 TO z STEP 2 x(i) = "[" x(i + 1) = "]" NEXT FOR i = 1 TO UBOUND(x) z = INT(RND * 2) IF z THEN SWAP x(i), x(i - 1) NEXT xx$ = "" FOR i = 0 TO UBOUND(x) xx$ = xx$ + x(i) NEXT generator$ = xx$
END FUNCTION</lang>
Sample output:
[][[][][]] OK ][[[]] NOT OK [][] OK []][][][[] NOT OK [][[]][[]] OK ][][[] NOT OK ][[] NOT OK ][][[]][][ NOT OK ][[[][]] NOT OK ][][[[]] NOT OK ][[]][ NOT OK OK
C#
<lang csharp>using System; using System.Linq;
class Program {
static bool IsBalanced(string text, char open = '[', char close = ']') { var level = 0; foreach (var character in text) { if (character == close) { if (level == 0) { return false; } level--; } if (character == open) { level++; } } return level == 0; }
static string RandomBrackets(int count, char open = '[', char close = ']') { var random = new Random(); return string.Join(string.Empty, (new string(open, count) + new string(close, count)).OrderBy(c => random.Next())); }
static void Main() { for (var count = 0; count < 9; count++) { var text = RandomBrackets(count); Console.WriteLine("\"{0}\" is {1}balanced.", text, IsBalanced(text) ? string.Empty : "not "); } }
}</lang> Sample output: <lang>"" is balanced. "[]" is balanced. "[]][" is not balanced. "[][][]" is balanced. "[[[]][]]" is balanced. "[][[][[]]]" is balanced. "[]][][][[][]" is not balanced. "[]]][][]][[][[" is not balanced. "[]]][]]][[][[][[" is not balanced.</lang>
C++
<lang cpp>#include <algorithm>
- include <iostream>
- include <string>
std::string generate(int n, char left = '[', char right = ']') {
std::string str(std::string(n, left) + std::string(n, right)); std::random_shuffle(str.begin(), str.end()); return str;
}
bool balanced(const std::string &str, char left = '[', char right = ']') {
int count = 0; for (std::string::const_iterator it = str.begin(); it != str.end(); ++it) { if (*it == left) count++; else if (*it == right) if (--count < 0) return false; } return count == 0;
}
int main() {
srand(time(NULL)); // seed rng for (int i = 0; i < 9; ++i) { std::string s(generate(i)); std::cout << (balanced(s) ? " ok: " : "bad: ") << s << "\n"; }
}</lang> Output:
ok: ok: [] ok: [][] bad: []][[] ok: [[[]][]] bad: ][[[[]][]] ok: [[[]][[]][]] bad: ]][[]][[[[][]] bad: [[]]]][]][[][[[]
D
D has a built-in method for this. <lang d>import std.stdio, std.algorithm, std.string, std.random;
void main() {
foreach (i; 0 .. 9) { auto s = "[]".repeat(i).dup; randomShuffle(s); writeln(s.balancedParens('[', ']') ? " OK: " : "bad: ", s); }
}</lang> One output:
OK: OK: [] bad: []][ OK: [][][] bad: [][]]][[ OK: [[[]][]][] bad: ][][[[][][]] bad: [[]][[]]]]][[[ bad: ][]]][[[[][][][]
Euphoria
<lang euphoria>function check_brackets(sequence s)
integer level level = 0 for i = 1 to length(s) do if s[i] = '[' then level += 1 elsif s[i] = ']' then level -= 1 if level < 0 then return 0 end if end if end for return level = 0
end function
function generate_brackets(integer n)
integer opened,closed,r sequence s opened = n closed = n s = "" for i = 1 to n*2 do r = rand(opened+closed) if r<=opened then s &= '[' opened -= 1 else s &= ']' closed -= 1 end if end for return s
end function
sequence s for i = 1 to 10 do
s = generate_brackets(3) puts(1,s) if check_brackets(s) then puts(1," OK\n") else puts(1," NOT OK\n") end if
end for</lang>
Sample output:
]]][[[ NOT OK [[[]]] OK [[]][] OK [][][] OK ]][[][ NOT OK [][[]] OK [[[]]] OK [[]][] OK []]][[ NOT OK [][[]] OK
F#
<lang fsharp>let isBalanced str =
let rec loop count = function | ']'::_ when count = 0 -> false | '['::xs -> loop (count+1) xs | ']'::xs -> loop (count-1) xs | [] -> count = 0 | _::_ -> false
str |> Seq.toList |> loop 0
let shuffle arr =
let rnd = new System.Random() Array.sortBy (fun _ -> rnd.Next()) arr
let generate n =
new string( String.replicate n "[]" |> Array.ofSeq |> shuffle )
for n in 1..10 do
let s = generate n printfn "\"%s\" is balanced: %b" s (isBalanced s)</lang>
Output:
"[]" is balanced: true "][][" is balanced: false "][[]][" is balanced: false "[][[]][]" is balanced: true "[[]][[]][]" is balanced: true "[[]][[[]][]]" is balanced: true "][[[]][[[]][]]" is balanced: false "][[][][]][[]][[]" is balanced: false "][[]][][]][[]][[[]" is balanced: false "][[]]][[][]][[]][[[]" is balanced: false
Fantom
<lang fantom> class Main {
static Bool matchingBrackets (Str[] brackets) { Int opened := 0 Int i := 0 while (i < brackets.size) { if (brackets[i] == "[") opened += 1 else opened -= 1 if (opened < 0) return false i += 1 } return true }
public static Void main (Str[] args) { if (args.size == 1 && Int.fromStr(args[0], 10, false) != null) { n := Int.fromStr(args[0]) Str[] brackets := [,] 20.times { brackets = [,] // create a random set of brackets n.times { brackets.addAll (["[", "]"]) } n.times { brackets.swap(Int.random(0..<2*n), Int.random(0..<2*n)) } // report if matching or not if (matchingBrackets(brackets)) echo (brackets.join(" ") + " Matching") else echo (brackets.join(" ") + " not matching") } } }
} </lang>
Output (for n=3):
[ ] [ ] [ ] Matching [ [ [ ] ] ] Matching ] [ [ ] ] [ not matching [ ] ] ] [ [ not matching ] ] [ ] [ [ not matching [ ] ] [ [ ] not matching [ ] ] [ [ ] not matching [ ] [ ] ] [ not matching [ [ ] ] [ ] Matching [ [ [ ] ] ] Matching [ ] ] [ [ ] not matching ] ] [ [ [ ] not matching [ ] ] [ [ ] not matching [ [ ] [ ] ] Matching [ ] [ ] [ ] Matching [ ] [ [ ] ] Matching [ [ [ ] ] ] Matching [ ] ] [ [ ] not matching ] ] [ ] [ [ not matching [ ] ] [ [ ] not matching
J
Solution: <lang j>bracketDepth =: '[]' -&(+/\)/@:(=/) ] checkBalanced =: _1 -.@e. bracketDepth genBracketPairs =: (?~@# { ])@#"0 1&'[]' NB. bracket pairs in arbitrary order</lang> Examples:<lang j> (,&' ' , ('bad';'OK') {::~ checkBalanced)"1 genBracketPairs i. 10
OK
][ bad
][[] bad
[[[]]] OK
[][[]][] OK
[][[[][]]] OK
[]][]][]][[[ bad
[[]][[][][]][] OK
]]]][[][][[[[]][ bad
[]]][][][[[[]][[]] bad</lang>
Comments: This task highlights the versatility and usefulness of J's scanning modifiers, /
and \
.
The checkBalanced
verb would need modification ( checkBalanced =: ((0 = {:) *. _1 -.@e. ])@bracketDepth
) if the task was extended to include uneven numbers of opening and closing brackets.
Java
<lang java5>public class Brackets {
public static boolean checkBrackets(String str){ int mismatchedBrackets = 0; for(char ch:str.toCharArray()){ if(ch == '['){ mismatchedBrackets++; }else if(ch == ']'){ mismatchedBrackets--; }else{ return false; //non-bracket chars } if(mismatchedBrackets < 0){ //close bracket before open bracket return false; } } return mismatchedBrackets == 0; }
public static String generate(int n){ if(n % 2 == 1){ //if n is odd we can't match brackets return null; } String ans = ""; int openBracketsLeft = n / 2; int unclosed = 0; while(ans.length() < n){ if(Math.random() >= .5 && openBracketsLeft > 0 || unclosed == 0){ ans += '['; openBracketsLeft--; unclosed++; }else{ ans += ']'; unclosed--; } } return ans; }
public static void main(String[] args){ String[] tests = {"", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]"}; for(int i = 0; i <= 16; i+=2){ String bracks = generate(i); System.out.println(bracks + ": " + checkBrackets(bracks)); }
for(String test: tests){ System.out.println(test + ": " + checkBrackets(test)); } }
}</lang> Sample output (generate uses random numbers, so it should not be the same every time):
: true []: true [[]]: true [[]][]: true [][][][]: true [][[][[]]]: true [[][[][][]]]: true [[][][]][[[]]]: true [][[[][[][[]]]]]: true : true []: true ][: false [][]: true ][][: false [[][]]: true []][[]: false
Objeck
<lang objeck> bundle Default {
class Balanced { function : IsBalanced(text : String) ~ Bool { level := 0; each(i : text) { character := text->Get(i); if(character = ']') { if(level = 0) { return false; }; level -= 1; };
if(character = '[') { level += 1; }; };
return level = 0; }
function : Main(args : String[]) ~ Nil { IsBalanced("")->PrintLine(); IsBalanced("[]")->PrintLine(); IsBalanced("[][]")->PrintLine(); IsBalanced("[[][]]")->PrintLine(); IsBalanced("][")->PrintLine(); IsBalanced("][][")->PrintLine(); IsBalanced("[]][[]")->PrintLine(); } }
} </lang>
true true true true false false false
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 = prompt "Number of brackets"; my $s = (<[ ]> xx $N).pick(*).join; say "$s {balanced($s) ?? "is" !! "is not"} well-balanced"</lang>
A solution using junctions is possible, too. (Though it doesn't work in Rakudo yet, because state
isn't implemented.
<lang perl6>sub balanced($s) {
return none(my @l) < 0 and @l[* - 1] == 0 given @l = map { state $l = 0; $l += $_ eq "]" ?? -1 !! +1 }, $s.comb;
}
my $N = prompt "Number of brackets"; my $s = (<[ ]> xx $N).pick(*).join; say "$s {balanced($s) ?? "is" !! "is not"} well-balanced"</lang> A more Perlish way to accomplish this is to repeatedly remove balanced pairs. (The following works under niecza but triggers a bug in rakudo.) <lang perl6>my $s = $*IN.get; $_ = $s; while s:g/'[]'// {} say "$s is", ($_ eq ?? !! ' not'), " well-balanced";</lang>
PicoLisp
<lang PicoLisp>(load "@lib/simul.l") # For 'shuffle'
(de generateBrackets (N)
(shuffle (make (do N (link "[" "]")))) )
(de checkBrackets (S)
(let N 0 (for C S (if (= C "[") (inc 'N) (if2 (= C "]") (=0 N) (off N) (dec 'N) ) ) ) (=0 N) ) )
(for N 10
(prinl (if (checkBrackets (prin (generateBrackets N))) " OK" "not OK")) )</lang>
Output:
[] OK [[]] OK ]]][[[not OK [[[][]]] OK [][][[[]]] OK []][[[][[]]]not OK [[[]]][][][][] OK ]][][[[[]][]]][[not OK []][][[[][[]]][]][not OK [[[][]]]]][][[]]][[[not OK
PureBasic
<lang PureBasic>Procedure.s Generate(N)
For i=1 To N sample$+"[]" Next For i=Len(sample$)-1 To 2 Step -1 r=Random(i-1)+1 If r<>i a.c=PeekC(@sample$+r*SizeOf(Character)) b.c=PeekC(@sample$+i*SizeOf(Character)) PokeC(@sample$+r*SizeOf(Character), b) PokeC(@sample$+i*SizeOf(Character), a) EndIf Next ProcedureReturn sample$
EndProcedure
Procedure Balanced(String$)
Protected *p.Character, cnt *p=@String$ While *p\c If *p\c='[' cnt+1 ElseIf *p\c=']' cnt-1 If cnt<0: Break: EndIf EndIf *p+SizeOf(Character) Wend If cnt=0 ProcedureReturn #True EndIf
EndProcedure
- - Test code
OpenConsole() For i=1 To 5
TestString$ = Generate(i) Print(TestString$) If Balanced(TestString$) PrintN(" is ballanced.") Else PrintN(" is not ballanced") EndIf
Next</lang> Output sample
[] is ballanced. [[]] is ballanced. [[[]]] is ballanced. [][]]][[ is not ballanced [][][][]][ is not ballanced
Python
<lang python>>>> def gen(N): ... txt = ['[', ']'] * 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>
Ruby
<lang ruby>re = /\A # beginning of string
(?<bb> # begin capture group <bb> \[ # literal [ \g<bb>* # zero or more <bb> \] # literal ] )* # end group, zero or more such groups
\z/x # end of string
(0..9).each do |i|
s = "[]" * i
# There is no String#shuffle! method. # This is a Knuth shuffle. (s.length - 1).downto(1) do |a; b| b = rand(a + 1) s[a], s[b] = s[b], s[a] end
puts((s =~ re ? " OK: " : "bad: ") + s)
end
["[[]", "[]]", "[letters]"].each do |s|
puts((s =~ re ? " OK: " : "bad: ") + s)
end</lang>
One output:
OK: OK: [] bad: ][][ bad: ][][][ bad: ]]][[[][ bad: ][]][][][[ bad: ][[][]]]][[[ bad: ]][][[[]]][][[ OK: [][[][][[][]]][] OK: [[[[[]]][[][]]][]] bad: [[] bad: []] bad: [letters]
Tcl
<lang tcl>proc generate {n} {
if {!$n} return set l [lrepeat $n "\[" "\]"] set len [llength $l] while {$len} {
set tmp [lindex $l [set i [expr {int($len * rand())}]]] lset l $i [lindex $l [incr len -1]] lset l $len $tmp
} return [join $l ""]
}
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}
}
for {set i 0} {$i < 15} {incr i} {
set s [generate $i] puts "\"$s\"\t-> [expr {[balanced $s] ? {OK} : {NOT OK}}]"
}</lang> Sample output:
"" -> OK "][" -> NOT OK "]][[" -> NOT OK "]]][[[" -> NOT OK "[][][[]]" -> OK "[[[][[]]]]" -> OK "[][][[][]][]" -> OK "[[]][]]]][[[][" -> NOT OK "][][[][][][[]]][" -> NOT OK "][[[][]][]]][][[][" -> NOT OK "]][][]][[][[][[]][][" -> NOT OK "[[[][[][]]][]]][[]]][[" -> NOT OK "[[]]][]][[[[]]][[][][[]]" -> NOT OK "][[][][]][[[]][[[[][]]]][]" -> NOT OK "]][[][[][[[[]][[][]][[]]]]][" -> NOT OK
Constructing correctly balanced strings
It is, of course, possible to directly construct such a balanced string, this being much more useful as the length of the string to generate grows longer. This is done by conceptually building a random tree (or forest) and then walking the tree, with open brackets being appended when a node is entered from its root and close brackets being appended when a node is left for its root. This is equivalent to inserting a balanced pair of brackets at a random place in an initially-empty string times, which might be done like this: <lang tcl>proc constructBalancedString {n} {
set s "" for {set i 0} {$i < $n} {incr i} {
set x [expr {int(rand() * ([string length $s] + 1))}] set s "[string range $s 0 [expr {$x-1}]]\[\][string range $s $x end]"
} return $s
}</lang> As noted, because the generated string is guaranteed to be balanced, it requires no further filtering and this results in much more efficient generation of balanced strings at longer lengths (because there's no need to backtrack).
TUSCRIPT
<lang tuscript> $$ MODE TUSCRIPT
SECTION gen_brackets values="[']",brackets="" LOOP n=1,12
brackets=APPEND (brackets,"","~") LOOP m=1,n a=RANDOM_NUMBERS (1,2,1),br=SELECT(values,#a) brackets=APPEND(brackets,"",br) b=RANDOM_NUMBERS (1,2,1),br=SELECT(values,#b) brackets=APPEND(brackets,"",br) ENDLOOP
ENDLOOP brackets=SPLIT (brackets,":~:") ENDSECTION
MODE DATA $$ BUILD X_TABLE brackets=*
[[(4 ]] )4 [[[ (3 ]]] )3 (2 )2 [ (1 ] )1
$$ MODE TUSCRIPT DO gen_brackets LOOP b=brackets status=CHECK_BRACKETS (b,brackets,a1,e1,a2,e2) PRINT b," ",status ENDLOOP </lang> Output:
OK ]] ERROR [[]] OK [][[]] OK []]]][[] ERROR []][]][][[ ERROR [[]][][]]]]] ERROR []][[][[]][[][ ERROR [][[[][[[[[[]][[ ERROR ]]][[]][]][[[][][[ ERROR ][][[]]][[[[[]]][[][ ERROR [[[][][]][]]]][[[[[[]] ERROR ][[[]][[][[[[[[[[[[[]]]] ERROR