Balanced brackets
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
BASIC
<lang qbasic>DECLARE FUNCTION checkBrackets% (brackets AS STRING)
DATA "[]", "][", "[][]", "][][", "[[][]]", "[]][[]", ""
DO
READ x$
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
checkBrackets% = -1
END FUNCTION</lang>
Output:
[] OK
][ NOT OK
[][] OK
][][ NOT OK
[[][]] 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: ][]]][[[[][][][]
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
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
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>
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 = get; my $s = (<[ ]> xx $N).pick(*).join; say "$s {balanced($s) ?? "is" !! "is not"} well-balanced"</lang>
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
TUSCRIPT
<lang tuscript>$$ MODE DATA $$ SET brackets=*
[
[]
][
[]]
][][
][][]
[[[]][
[]][[[]
][][][[]
][]][][[]
[]][[]][[]
][[]]][]]][
[[]][[[[]]]]
[[]]
[[[[]]]]
[[]][][]]]][[ _____________ $$ BUILD X_TABLE brackets=*
[[(4 ]] )4 [[[ (3 ]]] )3 (2 )2 [ (1 ] )1
$$ MODE TUSCRIPT LOOP b=brackets status=CHECK_BRACKETS (b,brackets,a1,e1,a2,e2) PRINT b," ",status ENDLOOP</lang> Output:
[ ERROR
[] OK
][ ERROR
[]] ERROR
][][ ERROR
][][] ERROR
[[[]][ ERROR
[]][[[] ERROR
][][][[] ERROR
][]][][[] ERROR
[]][[]][[] ERROR
][[]]][]]][ ERROR
[[]][[[[]]]] OK
[[]] OK
[[[[]]]] OK
[[]][][]]]][[ ERROR
_____________ OK