Balanced brackets: Difference between revisions
(reformat Ada code so lines are shorter than 80 characters) |
(remove lines too long notice) |
||
| Line 12: | Line 12: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
{{lines too long|Ada}} |
|||
brackets.adb: |
brackets.adb: |
||
<lang Ada>with Ada.Numerics.Discrete_Random; |
<lang Ada>with Ada.Numerics.Discrete_Random; |
||
Revision as of 12:51, 30 September 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
BBC BASIC
<lang bbcbasic>FOR x%=1 TO 10 test$=FNgenerate(RND(10))
PRINT "Bracket string ";test$;" is ";FNvalid(test$)
NEXT x% END
DEFFNgenerate(n%) LOCAL l%,r%,t%,output$ WHILE l%<n% AND r%<n%
CASE RND(2) OF
WHEN 1:
l%+=1
output$+="["
WHEN 2:
r%+=1
output$+="]"
ENDCASE
ENDWHILE IF l%=n% THEN output$+=STRING$(n%-r%,"]") ELSE output$+=STRING$(n%-l%,"[") =output$
DEFFNvalid(q$) LOCAL x%,count% IF LEN(q$)=0 THEN ="OK." FOR x%=1 TO LEN(q$)
IF MID$(q$,x%,1)="[" THEN count%+=1 ELSE count%-=1 IF count%<0 THEN ="not OK."
NEXT x% ="OK."</lang>
Bracket string [[[][]]] is OK. Bracket string [[[]][[[][[][]]]]] is OK. Bracket string ][][]][[ is not OK. Bracket string [][][] is OK. Bracket string [][]][]][[]]][[[ is not OK. Bracket string ]][[[[]]]][]]][[[[ is not OK. Bracket string [[][[[]]][]] is OK. Bracket string []][][][[[]] is not OK. Bracket string ][]][[ is not OK. Bracket string []][][][[] is not OK.
Brat
<lang brat>string.balanced? = {
brackets = [] balanced = true
my.dice.each_while { c |
true? c == "["
{ brackets << c }
{ true? c == "]"
{ last = brackets.pop
false? last == "["
{ balanced = false }
}
}
balanced }
true? brackets.empty?
{ balanced }
{ false }
}
generate_brackets = { n | (n.of("[") + n.of("]")).shuffle.join }
1.to 10 { n |
test = generate_brackets n
true? test.balanced?
{ p "#{test} is balanced" }
{ p "#{test} is not balanced" }
}</lang>
Output:
[] is balanced ][][ is not balanced [[]][] is balanced [[[]][]] is balanced [[[[]]]]][ is not balanced ][[][]][[[]] is not balanced ]][[][][[]][][ is not balanced [[[][[]]][][][]] is balanced ][]][]]]][][[[][[[ is not balanced ][[[[][][][[][][]]]] is not balanced
C
<lang c>#include<stdio.h>
- include<stdlib.h>
- include<string.h>
int isBal(char*s,int l){
signed c=0; while(l--)
if(s[l]==']') ++c; else if(s[l]=='[') if(--c<0) break;
return !c;
}
void shuffle(char*s,int h){
int x,t,i=h;
while(i--){
t=s[x=rand()%h]; s[x]=s[i]; s[i]=t;
}
}
void genSeq(char*s,int n){
if(n){
memset(s,'[',n); memset(s+n,']',n); shuffle(s,n*2);
} s[n*2]=0;
}
void doSeq(int n){
char s[64],*o="False";
genSeq(s,n);
if(isBal(s,n*2)) o="True";
printf("'%s': %s\n",s,o);
}
int main(){
int n=0; while(n<9) doSeq(n++); return 0;
}</lang>result:<lang>: True '[]': True ']][[': False '[][][]': True '[]][[]][': False '[]][[[[]]]': False ']]]][[[]][[[': False ']]]]]][][[[[[[': False '[][]][[][[[]]][]': False</lang>
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:
"" is balanced. "[]" is balanced. "[]][" is not balanced. "[][][]" is balanced. "[[[]][]]" is balanced. "[][[][[]]]" is balanced. "[]][][][[][]" is not balanced. "[]]][][]][[][[" is not balanced. "[]]][]]][[][[][[" is not balanced.
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: [[]]]][]][[][[[]
Clojure
<lang Clojure>(defn gen-brackets [n]
(->> (concat (repeat n \[) (repeat n \]))
shuffle
(apply str ,)))
(defn balanced? [s]
(loop [[first & coll] (seq s)
stack '()]
(if first
(if (= first \[)
(recur coll (conj stack \[)) (when (= (peek stack) \[) (recur coll (pop stack))))
(zero? (count stack)))))
user> (->> (range 10)
(map gen-brackets ,)
(map (juxt identity balanced?) ,) vec)
[["" true]
["[]" true] ["[[]]" true] ["[][[]]" true] ["[]][][][" nil] ["[[[[[]]]]]" true] ["]][[][][[[]]" nil] ["[]]]][[[[]][][" nil] ["][][[]]][[][][][" nil] ["][][]]][]][[[][[[]" nil]</lang>
Common Lisp
<lang lisp>(defun string-of-brackets (n)
(let ((result (make-string (* 2 n)))
(opening n)
(closing n))
(dotimes (i (* 2 n) result)
(setf (aref result i)
(cond
((zerop opening) #\])
((zerop closing) #\[)
(t (if (= (random 2) 0)
(progn (decf opening) #\[)
(progn (decf closing) #\]))))))))
(defun balancedp (string)
(zerop (reduce (lambda (nesting bracket)
(ecase bracket
(#\] (if (= nesting 0)
(return-from balancedp nil)
(1- nesting)))
(#\[ (1+ nesting))))
string
:initial-value 0)))
(defun show-balanced-brackets ()
(dotimes (i 10)
(let ((s (string-of-brackets i)))
(format t "~3A: ~A~%" (balancedp s) s))))</lang>
Output:
CL-USER> (show-balanced-brackets) T : NIL: ][ T : [[]] NIL: []]][[ T : [][][][] NIL: []][]][[[] NIL: []]]]][][[[[ NIL: ][]]]]][[[[][[ T : [[[[[[][[]]]]]]] NIL: ]][[[[][]][[[[]]]]
D
D standard library has a function for this. <lang d>import std.stdio, std.algorithm, std.random;
void main() {
foreach (i; 1 .. 9) {
char[] s;
foreach (_; 0 .. i*2)
s ~= ['[',']'][dice([50, 50])];
writeln(s.balancedParens('[', ']') ? " OK: " : "bad: ", s);
}
}</lang> One output:
OK: [] bad: []][ OK: [][][] bad: [][]]][[ OK: [[[]][]][] bad: ][][[[][][]] bad: [[]][[]]]]][[[ bad: ][]]][[[[][][][]
One implementation: <lang d>import std.stdio, std.random;
void main() { NEXT_STR:
foreach (j; 1 .. 9) {
char[] s;
foreach (_; 0 .. j*2)
s ~= ['[',']'][dice([50, 50])];
int balance;
foreach (i, c; s) {
balance += (c == '[') ? 1 : ((c == ']') ? -1 : 0);
if (balance < 0 || balance >= s.length - i) {
writefln("BAD: %s (%s)", s, balance < 0 ? "-" : "+");
continue NEXT_STR;
}
}
writefln(" OK: %s (=)", s);
}
}</lang> One output:
BAD: [[ (+) OK: [][] (=) BAD: ][[][[ (-) BAD: [[[[][][ (+) BAD: [][[[[[][] (+) BAD: ][]]][]]]]][ (-) BAD: ][]]]][[[[[][[ (-) BAD: [][[[][]][]][]]] (-)
Delphi
<lang Delphi>procedure Balanced_Brackets;
var BracketsStr : string;
TmpStr : string;
I,J : integer;
begin
Randomize;
for I := 1 to 9 do
begin
{ Create a random string of 2*N chars with N*"[" and N*"]" }
TmpStr := ;
for J := 1 to I do
TmpStr := '['+TmpStr+']';
BracketsStr := ;
while TmpStr > do
begin
J := Random(Length(TmpStr))+1;
BracketsStr := BracketsStr+TmpStr[J];
Delete(TmpStr,J,1);
end;
TmpStr := BracketsStr;
{ Test for balanced brackets }
while Pos('[]',TmpStr) > 0 do
Delete(TmpStr,Pos('[]',TmpStr),2);
if TmpStr = then
writeln(BracketsStr+': OK')
else
writeln(BracketsStr+': not OK');
end;
end;</lang>
[]: OK [[]]: OK [][][]: OK [[[]][]]: OK ]]]][[[[[]: not OK ][[][][[[]]]: not OK [][[]]][[][[]]: not OK [[[[[]][]][[]]]]: OK []]][][[[[[]][]][]: not OK
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
Forth
<lang forth>include lib/choose.4th ( n1 -- n2) include lib/ctos.4th ( n -- a 1)
10 constant /[] \ maximum number of brackets
/[] string [] \ string with brackets
\ create string with brackets
- make[] ( --)
0 dup [] place /[] choose 0 ?do 2 choose 2* [char] [ + c>s [] +place loop
- \ empty string, fill with brackets
\ evaluate string
- eval[] ( --)
[] count 2dup over chars + >r swap type 0 begin \ setup string and count over r@ < \ reached end of string? while \ if not .. dup 0< 0= \ unbalanced ]? while \ if not .. over c@ [char] \ - negate + swap char+ swap repeat \ evaluate, goto next character r> drop if ." NOT" then ." OK" cr drop
- \ evaluate string and print result
make[] eval[]</lang>
Examples:
[][[]] OK [[[[]][[ NOT OK ][[[]][] NOT OK ]][[[][ NOT OK []]]][][[ NOT OK []]][[]]] NOT OK OK [[[[]]]] OK [[]] OK [[[[]]]] OK [][[]] OK [] OK
GAP
<lang gap>Balanced := function(L)
local c, r;
r := 0;
for c in L do
if c = ']' then
r := r - 1;
if r < 0 then
return false;
fi;
elif c = '[' then
r := r + 1;
fi;
od;
return r = 0;
end;
Balanced("");
- true
Balanced("[");
- false
Balanced("]");
- false
Balanced("[]");
- true
Balanced("][");
- false
Balanced("[[][]]");
- true
Balanced("[[[]][]]]");
- false</lang>
Go
<lang go>package main
import (
"fmt" "rand" "strings" "time"
)
func init() {
rand.Seed(time.Nanoseconds())
}
func generate(n uint) string {
nb := strings.Repeat("[]", int(n))
px := rand.Perm(int(2 * n))
pb := make([]byte, 2*n)
for i := uint(0); i < 2*n; i++ {
pb[i] = nb[px[i]]
}
return string(pb)
}
func testBalanced(s string) {
fmt.Printf("%s: ", s)
var open int
for i := 0; i < len(s); i++ {
switch s[i] {
case '[':
open++
case ']':
if open == 0 {
fmt.Println("NOT OK")
return
}
open--
default:
panic("Unexpected content. Generator fail?")
}
}
if open == 0 {
fmt.Println("OK")
} else {
fmt.Println("NOT OK")
}
}
func main() {
for i := uint(0); i < 10; i++ {
testBalanced(generate(i))
}
testBalanced("()")
}</lang> Output:
: OK ][: NOT OK [][]: OK ][[][]: NOT OK [[][][]]: OK ]][][][][[: NOT OK ][][][]][[[]: NOT OK [[]][]]][][[[]: NOT OK ]][[[][][][][][]: NOT OK ][]]]][[[]][[[]][[: NOT OK (): panic: Unexpected content. Generator fail?
Haskell
<lang haskell> import Control.Monad import System.Random import Text.Printf import VShuffle
-- Return whether a string contains balanced brackets. Nothing indicates a -- balanced string, while (Just i) means an imbalance was found at, or just -- after, the i'th bracket. We assume the string contains only brackets. isBalanced :: String -> Maybe Int isBalanced = bal (-1) 0
where bal :: Int -> Int -> String -> Maybe Int
bal _ 0 [] = Nothing
bal i _ [] = Just i
bal i (-1) _ = Just i
bal i n ('[':bs) = bal (i+1) (n+1) bs
bal i n (']':bs) = bal (i+1) (n-1) bs
-- Print a string, indicating whether it contains balanced brackets. If not, -- indicate the bracket at which the imbalance was found. check :: String -> IO () check s = maybe (good s) (bad s) (isBalanced s)
where good s = printf "Good \"%s\"\n" s
bad s n = printf "Bad \"%s\"\n%*s^\n" s (n+6) " "
main :: IO () main = do
let bs = cycle "[]" rs <- replicateM 10 newStdGen zipWithM_ (\n r -> check $ shuffle (take n bs) r) [0,2..] rs
</lang> We put our list shuffling function in a separate module. For efficiency we use mutable vectors, although for the short lists in our example it doesn't really matter. <lang haskell> module VShuffle (shuffle) where
import Data.List (mapAccumL) import System.Random import Control.Monad.ST import qualified Data.Vector as V import qualified Data.Vector.Generic.Mutable as M
-- Generate a list of array index pairs, each corresponding to a swap. pairs :: (Enum a, Random a, RandomGen g) => a -> a -> g -> [(a, a)] pairs l u r = snd $ mapAccumL step r [l..pred u]
where step r i = let (j, r') = randomR (i, u) r in (r', (i, j))
-- Return a random permutation of the list. We use the algorithm described in -- http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm. shuffle :: (RandomGen g) => [a] -> g -> [a] shuffle xs r = V.toList . runST $ do
v <- V.unsafeThaw $ V.fromList xs
mapM_ (uncurry $ M.swap v) $ pairs 0 (M.length v - 1) r
V.unsafeFreeze v
</lang> Here's some sample output.
Good ""
Bad "]["
^
Good "[[]]"
Bad "[]][]["
^
Bad "[]]][][["
^
Bad "][][[[]][]"
^
Bad "[[][][]]][]["
^
Bad "][]][[[][][[]]"
^
Good "[[][[][[]]][[]]]"
Bad "]]][[[][][][[][]]["
^
Icon and Unicon
<lang Icon>procedure main(arglist) every s := genbs(!arglist) do
write(image(s), if isbalanced(s) then " is balanced." else " is unbalanced")
end
procedure isbalanced(s) # test if a string is balanced re: [] return (s || " ") ? (bal(,'[',']') = *s+1) end
procedure genbs(i) # generate strings of i pairs of [] s := "" every 1 to i do s ||:= "[]" # generate i pairs every !s := ?s # shuffle return s end</lang>
Output:
> isbal.exe 2 3 3 3 3 3 3 3 4 4 4 "[[]]" is balanced. "]]]]]]" is unbalanced "]]]]]]" is unbalanced "[][][]" is balanced. "]][[[]" is unbalanced "[[[][[" is unbalanced "]]]]]]" is unbalanced "[]]]]]" is unbalanced "]][]][]]" is unbalanced "[[[[[][[" is unbalanced "[[[[[][]" is unbalanced
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
JavaScript
<lang javascript> function createRandomBracketSequence(maxlen) {
var chars = { '0' : '[' , '1' : ']' };
function getRandomInteger(to)
{
return Math.floor(Math.random() * (to+1));
}
var n = getRandomInteger(maxlen);
var result = [];
for(var i = 0; i < n; i++)
{
result.push(chars[getRandomInteger(1)]);
}
return result.join("");
}
function bracketsAreBalanced(s) {
var open = (arguments.length > 1) ? arguments[1] : '[';
var close = (arguments.length > 2) ? arguments[2] : ']';
var c = 0;
for(var i = 0; i < s.length; i++)
{
var ch = s.charAt(i);
if ( ch == open )
{
c++;
}
else if ( ch == close )
{
c--;
if ( c < 0 ) return false;
}
}
return c == 0;
}
var c = 0; while ( c < 5 ) {
var seq = createRandomBracketSequence(8); alert(seq + ':\t' + bracketsAreBalanced(seq)); c++;
} </lang> Output:
: true [[]: false ]][[[][]: false ]]: false [][[]]: true
Liberty BASIC
<lang lb> print "Supplied examples" for i =1 to 7
read test$ print "The string '"; test$; "' is "; validString$( test$)
next i print data "", "[]", "][","[][]","][][","[[][]]","[]][[]"
print "Random generated examples" for example =1 to 10
test$ =generate$( int( 1 +10 *rnd(1))) print "The string '"; test$; "' is "; validString$( test$)
next example end
function validString$( in$)
if left$( in$, 1) <>"[" and len( test$) <>0 then
validString$ ="not OK. Opens wrongly."
exit function
end if
paired =0
for i =1 to len( in$)
c$ =mid$( in$, i, 1)
if c$ ="[" then paired =paired +1
if c$ ="]" then paired =paired -1
if paired <0 then
exit for
end if
next i
if ( lBr =rBr) and ( paired >=0) then validString$ ="OK." else validString$ ="not OK. Unbalanced."
end function
function generate$( N)
lBr =0
rBr =0
' choose at random until N of one type generated
while ( lBr <N) and ( rBr <N)
select case int( 1.5 +rnd( 1))
case 1
lBr =lBr +1
generate$ =generate$ +"["
case 2
rBr =rBr +1
generate$ =generate$ +"]"
end select
wend
' now pad with the remaining other brackets
if lBr =N then
generate$ =generate$ +string$( N -rBr, "]")
else
generate$ =generate$ +string$( N -lBr, "[")
end if
end function
function string$( n, c$)
for i =1 to n
op$ =op$ +c$
next i
string$ =op$
end function
end </lang>
Supplied examples The string is OK. The string '[]' is OK. The string '][' is not OK. Unbalanced. The string '[][]' is OK. The string '][][' is not OK. Unbalanced. The string '[[][]]' is OK. The string '[]][[]' is not OK. Unbalanced.
Random generated examples The string '[[][[[][]]]]' is OK. The string ']]]][[[[' is not OK. Unbalanced. The string '[[]][]' is OK. The string '[][[][[]][]]' is OK. The string '][[[]]][][' is not OK. Unbalanced. The string ']]]]][[[[[' is not OK. Unbalanced. The string '[[[]]]' is OK. The string ']][][[' is not OK. Unbalanced. The string '[[]]][][[][]' is not OK. Unbalanced. The string '][[][[][][]]][[]' is not OK. Unbalanced.
Lua
<lang Lua> function isBalanced(s)
--Lua pattern matching has a 'balanced' pattern that matches sets of balanced characters.
--Any two characters can be used.
return s:gsub('%b[]',)== and true or false
end
function randomString()
math.randomseed(os.time())
math.random()math.random()math.random()math.random()
local tokens={'[',']'}
local result={}
for i=1,8 do
table.insert(result,tokens[math.random(1,2)])
end
return table.concat(result)
end
local RS=randomString() print(RS) print(isBalanced(RS)) </lang>
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 {
": "->Print(); IsBalanced("")->PrintLine();
"[]: "->Print(); IsBalanced("[]")->PrintLine();
"[][]: "->Print(); IsBalanced("[][]")->PrintLine();
"[[][]]: "->Print(); IsBalanced("[[][]]")->PrintLine();
"][: "->Print(); IsBalanced("][")->PrintLine();
"][][: "->Print(); IsBalanced("][][")->PrintLine();
"[]][[]: "->Print(); IsBalanced("[]][[]")->PrintLine();
}
}
} </lang>
: true []: true [][]: true [[][]]: true ][: false ][][: false []][[]: false
OCaml
<lang ocaml>let generate_brackets n =
let rec aux i acc =
if i <= 0 then acc else
aux (pred i) ('['::']'::acc)
in
let brk = aux n [] in
List.sort (fun _ _ -> (Random.int 3) - 1) brk
let is_balanced brk =
let rec aux = function | [], 0 -> true | '['::brk, level -> aux (brk, succ level) | ']'::brk, 0 -> false | ']'::brk, level -> aux (brk, pred level) | _ -> assert false in aux (brk, 0)
let () =
let n = int_of_string Sys.argv.(1) in Random.self_init(); let brk = generate_brackets n in List.iter print_char brk; Printf.printf " %b\n" (is_balanced brk);
- </lang>
$ ocaml balanced_brackets.ml 3 []][[] false $ ocaml balanced_brackets.ml 3 [[]][] true
PARI/GP
<lang parigp>balanced(s)={
my(n=0,v=Vecsmall(s));
for(i=1,#v,
if(v[i]==91,
n++
,
if(v[i]==93 && n, n--, return(0))
)
);
!n
}; rnd(n)=Strchr(vectorsmall(n,i,if(random(2),91,93))) forstep(n=0,10,2,s=rnd(n);print(s"\t"if(balanced(s),"true","false")))</lang>
Perl
Straightforward depth counting: <lang Perl>use 5.10.0; # for given ... when construct sub balanced2 {
my $depth = 0;
my @a = split(, shift);
for my $i (0 .. $#a) {
given($a[$i]) {
when('[') { ++$depth }
when(']') { return if --$depth < 0 }
}
}
return !$depth
}
for (']', '[', '[[]', '][]', '[[]]', '[[]]]][][]]', 'x[ y [ [] z ]][ 1 ][]abcd') {
print balanced($_) ? "" : "not ", "balanced:\t'$_'\n";
}</lang>
or use regexp: <lang Perl>use 5.10.0; # for '++' non-backtrack behavior sub balanced {
my $_ = shift;
s/(\[(?:[^\[\]]++|(?1))*\])//g;
! /[\[\]]/;
}
for (']', '[', '[[]', '][]', '[[]]', '[[]]]][][]]', 'x[ y [ [] z ]][ 1 ][]abcd') a{
print balanced($_) ? "" : "not ", "balanced:\t'$_'\n";
}</lang>
Both methods print
not balanced: ']' not balanced: '[' not balanced: '[[]' not balanced: '][]' balanced: '[[]]' not balanced: '[[]]]][][]]' balanced: 'x[ y [ [] z ]][ 1 ][]abcd'
The counting method could easily give where the first unbalanced bracket occured, though.
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
Prolog
DCG are very usefull for this kind of exercice ! <lang Prolog>rosetta_brackets :- test_brackets([]), test_brackets(['[',']']), test_brackets(['[',']','[',']']), test_brackets(['[','[',']','[',']',']']), test_brackets([']','[']), test_brackets([']','[',']','[']), test_brackets(['[',']',']','[','[',']']).
balanced_brackets :- gen_bracket(2, B1, []), test_brackets(B1), gen_bracket(4, B2, []), test_brackets(B2), gen_bracket(4, B3, []), test_brackets(B3), gen_bracket(6, B4, []), test_brackets(B4), gen_bracket(6, B5, []), test_brackets(B5), gen_bracket(8, B6, []), test_brackets(B6), gen_bracket(8, B7, []), test_brackets(B7), gen_bracket(10, B8, []), test_brackets(B8), gen_bracket(10, B9, []), test_brackets(B9).
test_brackets(Goal) :- ( Goal = [] -> write('(empty)'); maplist(write, Goal)), ( balanced_brackets(Goal, []) -> writeln(' succeed') ; writeln(' failed') ).
% grammar of balanced brackets balanced_brackets --> [].
balanced_brackets --> ['['], balanced_brackets, [']'].
balanced_brackets --> ['[',']'], balanced_brackets.
% generator of random brackets
gen_bracket(0) --> [].
gen_bracket(N) --> {N1 is N - 1, R is random(2)}, bracket(R), gen_bracket(N1).
bracket(0) --> ['[']. bracket(1) --> [']']. </lang> Sample output :
?- balanced_brackets. [[ failed [[][ failed [[]] succeed [[][]] succeed [][[][ failed ][]][[[] failed [[[[]][] failed [[[[[][[]] failed []][[[][]] failed true .
Test with Rosetta examples :
?- rosetta_brackets. (empty) succeed [] succeed [][] succeed [[][]] succeed ][ failed ][][ failed []][[] failed true.
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>
Qi
<lang qi>(define balanced-brackets-0
[] 0 -> true [] _ -> false [#\[|R] Sum -> (balanced-brackets-0 R (+ Sum 1)) _ 0 -> false [_ |R] Sum -> (balanced-brackets-0 R (- Sum 1)))
(define balanced-brackets
"" -> true S -> (balanced-brackets-0 (explode (INTERN S)) 0))
(balanced-brackets "")
(balanced-brackets "[]") (balanced-brackets "[][]") (balanced-brackets "[[][]]")
(balanced-brackets "][") (balanced-brackets "][][") (balanced-brackets "[]][[]")
</lang>
R
<lang r>balanced <- function(str){
str <- strsplit(str, "")1 str <- ifelse(str=='[', 1, -1) all(cumsum(str) >= 0) && sum(str) == 0
}</lang>
Alternately, using perl 5.10-compatible regexps,
<lang r>balanced <- function(str) {
regexpr('^(\\[(?1)*\\])*$', str, perl=TRUE) > -1
}</lang>
To generate some some examples:
<lang R>rand.parens <- function(n) paste(permute(c(rep('[',n),rep(']',n))),collapse="")
as.data.frame(within(list(), {
parens <- replicate(10, rand.parens(sample.int(10,size=1))) balanced <- sapply(parens, balanced)
}))</lang>
Output: <lang r> balanced parens 1 FALSE ][][ 2 FALSE [][[]]][[]][]]][[[ 3 FALSE ][[][][]][][[] 4 FALSE ][][][][][][][ 5 TRUE [[[][]]][[[][][]]] 6 TRUE [] 7 FALSE ]][[][[] 8 FALSE []]]][[[]][[[] 9 TRUE [[[[][[][]]]]] 10 TRUE []</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]
Scheme
<lang scheme>(define (balanced-brackets string)
(define (b chars sum)
(cond ((and (null? chars) (= 0 sum))
#t)
((null? chars)
#f)
((char=? #\[ (car chars))
(b (cdr chars) (+ sum 1)))
((= sum 0)
#f)
(else
(b (cdr chars) (- sum 1)))))
(b (string->list string) 0))
(balanced-brackets "")
(balanced-brackets "[]") (balanced-brackets "[][]") (balanced-brackets "[[][]]")
(balanced-brackets "][") (balanced-brackets "][][") (balanced-brackets "[]][[]") </lang>
Seed7
<lang seed7>$ include "seed7_05.s7i";
const func string: generateBrackets (in integer: count) is func
result
var string: stri is "";
local
var integer: index is 0;
var integer: pos is 0;
var char: ch is ' ';
begin
stri := "[" mult count & "]" mult count;
for index range 1 to length(stri) do
pos := rand(1, length(stri));
ch := stri[index];
stri @:= [index] stri[pos];
stri @:= [pos] ch;
end for;
end func;
const func boolean: checkBrackets (in string: test) is func
result
var boolean: okay is TRUE;
local
var char: ch is ' ';
var integer: open is 0;
begin
for ch range test do
if ch = '[' then
incr(open);
elsif ch = ']' then
if open = 0 then
okay := FALSE;
else
decr(open);
end if;
end if;
end for;
okay := open = 0;
end func;
const proc: main is func
local
var integer: n is 0;
var integer: count is 0;
var string: stri is "";
begin
for n range 0 to 4 do
for count range 1 to 3 do
stri := generateBrackets(n);
writeln(stri <& ": " <& checkBrackets(stri));
end for;
end for;
end func;</lang>
Output:
: TRUE : TRUE : TRUE []: TRUE ][: FALSE ][: FALSE ][[]: FALSE [[]]: TRUE [[]]: TRUE [][][]: TRUE [[][]]: TRUE []]][[: FALSE [][][]][: FALSE [][][][]: TRUE ]][][[][: FALSE
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