Anonymous user
Balanced brackets: Difference between revisions
Added uBasic/4tH version
(→{{header|TypeScript}}: Added.) |
imported>Thebeez (Added uBasic/4tH version) |
||
(36 intermediate revisions by 19 users not shown) | |||
Line 19:
=={{header|11l}}==
{{trans|Python}}
<
V txt = [‘[’, ‘]’] * n
random:shuffle(&txt)
Line 37:
L(n) 0..9
V s = gen(n)
print(s‘’(‘ ’ * (20 - s.len))‘is ’(I is_balanced(s) {‘balanced’} E ‘not balanced’))</
{{out}}
<pre>
Line 53:
=={{header|360 Assembly}}==
<
BALANCE CSECT
USING BALANCE,R13 base register and savearea pointer
Line 153:
XDEC DS CL12
REGS
END BALANCE</
{{out}}
<pre>
Line 176:
19 [[[[[[][[[[[][][ ?
20 [[][[][] ?
</pre>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}
<syntaxhighlight lang AArch64 Assembly>
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program balencebrac64.s */
/************************************/
/* Constantes */
/************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeConstantesARM64.inc"
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessResult: .asciz "Expression : "
szMessBalenced: .asciz " balanced"
szMessNotBalenced: .asciz " not balanced"
szMessStart: .asciz "Program 64 bits start.\n"
szCarriageReturn: .asciz "\n"
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
sZoneConv: .skip 24 // conversion buffer
sBuffer: .skip 80
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: // entry of program
ldr x0,qAdrszMessStart
bl affichageMess
mov x0,0b111000 // bit 1 = open bracket bit 0 = close bracket
bl testBalanced
mov x0,0b110100
bl testBalanced
mov x0,0b11001001
bl testBalanced
mov x19,10 // number random test
1:
mov x0,1 // mini number
mov x1,10000 // maxi random number
bl extRandom // generate random number
bl testBalanced
subs x19,x19,1
bge 1b
100: // standard end of the program
mov x0, #0 // return code
mov x8,EXIT
svc #0 // perform the system call
qAdrszCarriageReturn: .quad szCarriageReturn
qAdrszMessResult: .quad szMessResult
qAdrszMessNotBalenced: .quad szMessNotBalenced
qAdrszMessBalenced: .quad szMessBalenced
qAdrszMessStart: .quad szMessStart
qAdrsBuffer: .quad sBuffer
/***************************************************/
/* routine to test expression */
/***************************************************/
/* x0 expression */
testBalanced:
stp x1,lr,[sp,-16]! // save registres
stp x2,x3,[sp,-16]! // save registres
ldr x1,qAdrsBuffer
bl isBalanced
cmp x0,0
ldr x3,qAdrszMessNotBalenced
ldr x4,qAdrszMessBalenced
csel x3,x3,x4,eq
mov x0,#4 // string number to display
ldr x1,qAdrszMessResult
ldr x2,qAdrsBuffer
ldr x4,qAdrszCarriageReturn
bl displayStrings // display message
100:
ldp x2,x3,[sp],16 // restaur registres
ldp x1,lr,[sp],16 // restaur registres
ret
/***************************************************/
/* control if expression is balenced */
/***************************************************/
/* x0 expression */
/* x1 buffer address */
/* x0 return 1 if balanced else zero */
isBalanced:
stp x1,lr,[sp,-16]! // save registres
stp x2,x3,[sp,-16]! // save registres
mov x3,63
clz x2,x0 // number of zeros on the left
sub x2,x3,x2 // so many useful numbers right
mov x4,1 // mask to test bit
lsl x4,x4,x2 // shift left begin expression
mov x3,0 // top if right bracket > left bracket
mov x7,0 // indice display buffer expression
mov x5,0 // counter brackets
1: // begin loop to test bits
tst x0,x4
beq 2f // bit = 0
mov x6,'(' // else bit = 1 -> open bracket
strb w6,[x1,x7] // store in buffer
add x7,x7,1 // increment indice
add x5,x5,1 // increment open bracket
b 3f
2: // bit = 0
mov x6,')' // close bracket
strb w6,[x1,x7] // store in buffer
add x7,x7,1 // increment indice
subs x5,x5,1 // decrement open bracket
bge 3f // if negative
mov x3,1 // top error
3:
lsr x4,x4,1 // shift mask right
cbnz x4,1b // and loop if not zero
strb wzr,[x1,x7] // zero final on buffer
cmp x5,0 // right bracket <> left bracket -> error
bne 4f
cmp x3,0 // in expression left bracket > right bracket
bne 4f
mov x0,1 // balanced
b 100f
4:
mov x0,0 // not balanced
100:
ldp x2,x3,[sp],16 // restaur registres
ldp x1,lr,[sp],16 // restaur registres
ret
/***************************************************/
/* display multi strings */
/* new version 24/05/2023 */
/***************************************************/
/* x0 contains number strings address */
/* x1 address string1 */
/* x2 address string2 */
/* x3 address string3 */
/* x4 address string4 */
/* x5 address string5 */
/* x6 address string5 */
/* x7 address string6 */
displayStrings: // INFO: displayStrings
stp x8,lr,[sp,-16]! // save registers
stp x2,fp,[sp,-16]! // save registers
add fp,sp,#32 // save paraméters address (4 registers saved * 8 bytes)
mov x8,x0 // save strings number
cmp x8,#0 // 0 string -> end
ble 100f
mov x0,x1 // string 1
bl affichageMess
cmp x8,#1 // number > 1
ble 100f
mov x0,x2
bl affichageMess
cmp x8,#2
ble 100f
mov x0,x3
bl affichageMess
cmp x8,#3
ble 100f
mov x0,x4
bl affichageMess
cmp x8,#4
ble 100f
mov x0,x5
bl affichageMess
cmp x8,#5
ble 100f
mov x0,x6
bl affichageMess
cmp x8,#6
ble 100f
mov x0,x7
bl affichageMess
100:
ldp x2,fp,[sp],16 // restaur registers
ldp x8,lr,[sp],16 // restaur registers
ret
/******************************************************************/
/* random number */
/******************************************************************/
/* x0 contains inferior value */
/* x1 contains maxi value */
/* x0 return random number */
extRandom:
stp x1,lr,[sp,-16]! // save registers
stp x2,x8,[sp,-16]! // save registers
stp x19,x20,[sp,-16]! // save registers
sub sp,sp,16 // reserve 16 octets on stack
mov x19,x0
add x20,x1,1
mov x0,sp // store result on stack
mov x1,8 // length 8 bytes
mov x2,0
mov x8,278 // call system Linux 64 bits Urandom
svc 0
mov x0,sp // load résult on stack
ldr x0,[x0]
sub x2,x20,x19 // calculation of the range of values
udiv x1,x0,x2 // calculation range modulo
msub x0,x1,x2,x0
add x0,x0,x19 // and add inferior value
100:
add sp,sp,16 // alignement stack
ldp x19,x20,[sp],16 // restaur 2 registers
ldp x2,x8,[sp],16 // restaur 2 registers
ldp x1,lr,[sp],16 // restaur 2 registers
ret // retour adresse lr x30
/***************************************************/
/* ROUTINES INCLUDE */
/***************************************************/
/* for this file see task include a file in language AArch64 assembly*/
.include "../includeARM64.inc"
</syntaxhighlight>
{{Out}}
<pre>
Program 64 bits start.
Expression : ((())) balanced
Expression : (()()) balanced
Expression : (())())( not balanced
Expression : ((()))))()))) not balanced
Expression : (()())())())) not balanced
Expression : ()(((()((()) not balanced
Expression : ())()(()())() not balanced
Expression : ())))((()))((( not balanced
Expression : (())()())(() not balanced
Expression : ())()))))(()( not balanced
Expression : ())()(())(()( not balanced
Expression : ())(()(()())) not balanced
Expression : ((()))()))))) not balanced
Expression : (()))((()))( not balanced
</pre>
=={{header|ABAP}}==
<syntaxhighlight lang="abap">
CLASS lcl_balanced_brackets DEFINITION.
PUBLIC SECTION.
Line 276 ⟶ 518:
cl_demo_output=>display( ).
</syntaxhighlight>
{{out}}
Line 303 ⟶ 545:
=={{header|Action!}}==
<
BYTE i,half
Line 374 ⟶ 616:
PrintE("balanced")
OD
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Balanced_brackets.png Screenshot from Atari 8-bit computer]
Line 395 ⟶ 637:
Using #HASH-OFF
</pre>
<syntaxhighlight lang="acurity architect">
FUNCTION bBRACKETS_MATCH(zStringWithBrackets: STRING): STRING
VAR sCount: SHORT
Line 415 ⟶ 657:
RETURN zOK
ENDFUNCTION
</syntaxhighlight>
{{out}}
<pre>
Line 426 ⟶ 668:
=={{header|Ada}}==
brackets.adb:
<
with Ada.Text_IO;
with Ada.Strings.Fixed;
Line 482 ⟶ 724:
end loop;
end loop;
end Brackets;</
Output:
Line 503 ⟶ 745:
=={{header|Aime}}==
<
{
integer b, i;
Line 537 ⟶ 779:
0;
}</
Sample output:
<pre> is balanced
Line 552 ⟶ 794:
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.win32}}
<
# each type of brackets is speccified in length #
PROC get brackets = ( INT length ) STRING:
Line 614 ⟶ 856:
test check brackets( get brackets( length ) )
OD
OD</
{{out}}
<pre>
Line 642 ⟶ 884:
]][][]]][]][][]][[[[[[][: not ok
]]][][][]][][[]][[[][][[: not ok
</pre>
=={{header|Amazing Hopper}}==
<syntaxhighlight lang="c">
#include <basico.h>
algoritmo
braizq="[", brader="]" // bug de Hopper :(
largo de datos=0
preparar datos (DATA_BRACKET)
obtener tamaño de datos, menos '1', guardar en 'largo de datos'
iterar
bra="", obtener dato, guardar en 'bra'
i=1, b=0, error_pos=""
iterar grupo( ++i, #( i<=len(bra) && is not neg (b) ),\
#( b += ((bra[i]==braizq) - (bra[i]==brader)) )\
#( error_pos = cat(replicate(" ",i-1),"^\n") ) )
solo si ( #(is pos(b)),\
#( error_pos=cat(cat(" ",error_pos),"(missing closed bracket)\n\n")))
solo si ( #(is neg(b)),\
#( error_pos=cat(error_pos,"(extra closed bracket)\n\n")))
imprimir ( #( rpad(" ",40,bra) ), ": ", \
solo si (b, "un"), "balanced\n",\
solo si (b, error_pos) )
mientras ' largo de datos-- '
terminar
subrutinas
DATA_BRACKET:
datos ("","[ [ ] [ [[] ][] ] [[]] ]","[[ ][[[ ][ ]]",\
"[][][[]]][","][[]][] [[[]]] [][]","[][] [][][[]]",\
"[ a-b * [c/d] + [[10 * sin 30 ]-1] ]",\
"[ a-b * [c/d] + [[10 * sin 30 ]]-1] ]")
back
</syntaxhighlight>
{{out}}
<pre>
: balanced
[ [ ] [ [[] ][] ] [[]] ] : balanced
[[ ][[[ ][ ]] : unbalanced
^
(missing closed bracket)
[][][[]]][ : unbalanced
^
(extra closed bracket)
][[]][] [[[]]] [][] : unbalanced
^
(extra closed bracket)
[][] [][][[]] : balanced
[ a-b * [c/d] + [[10 * sin 30 ]-1] ] : balanced
[ a-b * [c/d] + [[10 * sin 30 ]]-1] ] : unbalanced
^
(extra closed bracket)
</pre>
Line 649 ⟶ 958:
<br clear=both>
==={{header|Java}}===
<syntaxhighlight lang="text">
grammar balancedBrackets ;
Line 669 ⟶ 978:
NEWLINE : '\r'? '\n'
;
</syntaxhighlight>
Produces:
<pre>
Line 694 ⟶ 1,003:
and a function to check whether a given string of brackets is balanced.
<
bal ← (((|≡⊢)+\) ∧ 0=+/)(+⌿1 ¯1×[1]'[]'∘.=⊢)</
Sample run for 0..N..10:
<
: Good
[]: Good
Line 710 ⟶ 1,019:
[[][[]]][[[[]]]]: Good
[[[]][[[[][]][]]]]: Good
]][][][][[][][]][[[]: Bad</
=={{header|AppleScript}}==
Line 717 ⟶ 1,026:
(ES6 functionally composed version)
<
-- Zero-based index of the first problem (-1 if none found):
Line 899 ⟶ 1,208:
end script
end if
end mReturn</
'''Sample output:'''
<pre>'][' problem
Line 914 ⟶ 1,223:
=={{header|ARM Assembly}}==
<syntaxhighlight lang="arm_assembly">
.data
Line 974 ⟶ 1,283:
mov pc, lr
</syntaxhighlight>
=={{header|Arturo}}==
<
cnt: 0
Line 1,000 ⟶ 1,309:
if? isBalanced str -> print " OK"
else -> print " Not OK"
]</
{{out}}
Line 1,016 ⟶ 1,325:
=={{header|AutoHotkey}}==
<
Loop, 5
{
Line 1,047 ⟶ 1,356:
}
Return "OK"
}</
Output:
<pre>
Line 1,063 ⟶ 1,372:
A second example repeatedly replacing []:
<
{
B = %A_Index%
Line 1,085 ⟶ 1,394:
StringReplace, Str, Str,[],,All
Return Str ? "False" : "True"
}</
Sample output:
<pre>
Line 1,101 ⟶ 1,410:
=={{header|AutoIt}}==
<syntaxhighlight lang="autoit">
#include <Array.au3>
Local $Array[1]
Line 1,130 ⟶ 1,439:
Return 1
EndFunc
</syntaxhighlight>
=={{header|AWK}}==
<
BEGIN {
print isbb("[]")
Line 1,155 ⟶ 1,464:
return (s==0)
}
</syntaxhighlight>
Output:
<pre>1
Line 1,165 ⟶ 1,474:
=={{header|BaCon}}==
<
str$ = ""
Line 1,187 ⟶ 1,496:
PRINT "BAD: ", str$
ENDIF
NEXT</
{{out}}
<pre>OK:
Line 1,202 ⟶ 1,511:
=={{header|BASIC}}==
{{works with|QBasic}}
<syntaxhighlight lang="qbasic">DECLARE FUNCTION checkBrackets% (brackets AS STRING)
DECLARE FUNCTION generator$ (length AS INTEGER)
Line 1,259 ⟶ 1,567:
NEXT
generator$ = xx$
END FUNCTION</
{{out}}
<pre> [][[][][]] OK
][[[]] NOT OK
[][] OK
Line 1,273 ⟶ 1,580:
][][[[]] NOT OK
][[]][ NOT OK
OK</pre>
==={{header|Applesoft BASIC}}===
The [[#MSX_BASIC|MSX BASIC]] solution works without any changes.
==={{header|BASIC256}}===
{{trans|Yabasic}}
<syntaxhighlight lang="basic256">s$ = "[[]][]"
print s$; " = ";
if not check_brackets(s$) then print "not ";
print "ok"
end
function check_brackets(s$)
level = 0
for i = 1 to length(s$)
c$ = mid(s$, i, 1)
begin case
case c$ = "["
level = level + 1
case c$ = "]"
level = level - 1
if level < 0 then exit for
end case
next i
return level = 0
end function</syntaxhighlight>
==={{header|Chipmunk Basic}}===
The [[#MSX_BASIC|MSX BASIC]] solution works without any changes.
==={{header|Commodore BASIC}}===
Based on ZX Spectrum BASIC implementation
<
20 FOR N=1 TO 7
30 READ S$
Line 1,297 ⟶ 1,634:
1090 PRINT "NOT OK"
1100 RETURN
2000 DATA , [], ][, [][], ][][, [[][]], []][[]</
==={{header|GW-BASIC}}===
{{works with|PC-BASIC|any}}
{{works with|BASICA}}
The [[#MSX_BASIC|MSX BASIC]] solution works without any changes.
==={{header|
Based on Commodore BASIC implementation
{{works with|MSX BASIC|any}}
{{works with|Applesoft BASIC}}
{{works with|BASICA}}
{{works with|Chipmunk Basic}}
{{works with|GW-BASIC}}
{{works with|PC-BASIC|any}}
{{works with|QBasic}}
<syntaxhighlight lang="qbasic">100 CLS : rem 10 HOME for Applesoft BASIC
110 FOR N = 1 TO 7
120 READ S$
130 IF S$ = "" THEN PRINT"(EMPTY)";: GOTO 150
140 PRINT S$;
150 PRINT TAB(9);
160 GOSUB 190
170 NEXT N
180 END
190 S = 0
200 FOR K = 1 TO LEN(S$)
210 C$ = MID$(S$,K,1)
220 IF C$ = "[" THEN S = S+1
230 IF C$ = "]" THEN S = S-1
240 IF S < 0 THEN PRINT "NOT OK": RETURN
250 NEXT K
260 IF S = 0 THEN PRINT " OK": RETURN
270 PRINT "NOT OK"
280 RETURN
290 DATA "", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]"</syntaxhighlight>
{{out}}
<pre>(EMPTY) OK
[] OK
][ NOT OK
[][] OK
][][ NOT OK
[[][]] OK
[]][[] NOT OK</pre>
==={{header|True BASIC}}===
{{trans|Run BASIC}}
<syntaxhighlight lang="qbasic">DIM brk$(10)
LET brk$(1) = "[[[][]]]"
LET brk$(2) = "[[[]][[[][[][]]]]]"
LET brk$(3) = "][][]][["
LET brk$(4) = "[][][]"
LET brk$(5) = "[][]][]][[]]][[["
LET brk$(6) = "]][[[[]]]][]]][[[["
LET brk$(7) = "[[][[[]]][]]"
LET brk$(8) = "[]][][][[[]]"
LET brk$(9) = "][]][["
LET brk$(10) = "[]][][][[]"
FOR i = 1 TO 7
IF x > 0 THEN LET b$ = (b$)[1:x-1] & (b$)[x+2:maxnum]
IF
ELSE
PRINT
PRINT brk$(i)
NEXT i
END</syntaxhighlight>
==={{header|uBasic/4tH}}===
<syntaxhighlight lang="qbasic">@(0) := "[]][][][[]"
@(1) := "[[[][]]]"
@(2) := "[[[]][[[][[][]]]]]"
@(3) := "][][]][["
@(4) := "[][][]"
@(5) := "[][]][]][[]]][[["
@(6) := "]][[[[]]]][]]][[[["
@(7) := "[[][[[]]][]]"
@(8) := "[]][][][[[]]"
@(9) := "][]][["
For x = 0 To 9
Print Using "(_#)";x,Show (@(x));Tab (30);
Do While (Set (a, Find(@(x), "[]")) < 0) = 0
@(x) = Join (Clip (@(x), Len (@(x)) - a), Chop (@(x), a + 2))
Loop
Print "is";Show (Iif (Len (@(x))," not "," "));"balanced"
Next</syntaxhighlight>
{{Out}}
<pre>( 0) []][][][[] is not balanced
( 1) [[[][]]] is balanced
( 2) [[[]][[[][[][]]]]] is balanced
( 3) ][][]][[ is not balanced
( 4) [][][] is balanced
( 5) [][]][]][[]]][[[ is not balanced
( 6) ]][[[[]]]][]]][[[[ is not balanced
( 7) [[][[[]]][]] is balanced
( 8) []][][][[[]] is not balanced
( 9) ][]][[ is not balanced
0 OK, 0:472 </pre>
=={{header|Batch File}}==
Uses the rewrite rule <code>"[]" -> null</code> to check if brackets are balanced.
<
:: Batch File Implementation
Line 1,379 ⟶ 1,796:
set "old=%new%"
set "new=%old:[]=%"
goto check_loop</
{{out}}
<pre>[][][[[[]]][]]]][[][ is NOT Balanced.
Line 1,404 ⟶ 1,821:
=={{header|BBC BASIC}}==
<
test$=FNgenerate(RND(10))
PRINT "Bracket string ";test$;" is ";FNvalid(test$)
Line 1,432 ⟶ 1,849:
IF count%<0 THEN ="not OK."
NEXT x%
="OK."</
<pre>Bracket string [[[][]]] is OK.
Bracket string [[[]][[[][[][]]]]] is OK.
Line 1,447 ⟶ 1,864:
{{works with|befungee}}
This code implements the second part of the task: it reads from standard input an arbitrary string of opening and closing brackets, and checks whether it's balanced or not.
<
> ~ : 25*- #v_ $ | > 25*, @
> "KO" ,, ^
Line 1,453 ⟶ 1,870:
> \ : 1991+*+- #v_v
\ $
^ < <$<</
=={{header|BQN}}==
Line 1,462 ⟶ 1,879:
This allows for a particular simple implementation:
<
Bal ← {
Mul ← {a‿b𝕊x‿y: ⟨a+0⌈x-b, y+0⌈b-x⟩}
0‿0 ≡ 0‿0("]["⊸=⊸Mul)´𝕩
}</
{{out}}
Line 1,480 ⟶ 1,897:
=={{header|Bracmat}}==
Bracmat has no 'random' function, so the shuffle is a bit improvised. A variable <code>someNumber</code> is initialised with a big number is repeatedly divided by the number of '['s in the test string until zero. The remainders are used as index to partition and swap the first half of the test string. Then the second half and first half are also swapped. The test whether the test string is balanced is simple, but not very efficient.
<
& ( generate
= a j m n z N S someNumber
Line 1,506 ⟶ 1,923:
& !L+1:<11:?L
)
);</
Output:
<pre>:Balanced
Line 1,521 ⟶ 1,938:
=={{header|Brat}}==
<
brackets = []
balanced = true
Line 1,551 ⟶ 1,968:
{ p "#{test} is balanced" }
{ p "#{test} is not balanced" }
}</
Output:
Line 1,566 ⟶ 1,983:
=={{header|C}}==
<
#include<stdlib.h>
#include<string.h>
Line 1,608 ⟶ 2,025:
while(n<9) doSeq(n++);
return 0;
}</
'[]': True
']][[': False
Line 1,616 ⟶ 2,033:
']]]][[[]][[[': False
']]]]]][][[[[[[': False
'[][]][[][[[]]][]': False</
=={{header|C sharp|C#}}==
<
using System.Linq;
Line 1,660 ⟶ 2,077:
}
}
}</
Sample output:
<pre>"" is balanced.
Line 1,671 ⟶ 2,088:
"[]]][][]][[][[" is not balanced.
"[]]][]]][[][[][[" is not balanced.</pre>
<
// simple solution
string input = Console.ReadLine();
Line 1,696 ⟶ 2,113:
Console.WriteLine("Not Okay");
</syntaxhighlight>
=={{header|C++}}==
<
#include <iostream>
#include <string>
Line 1,731 ⟶ 2,148:
std::cout << (balanced(s) ? " ok: " : "bad: ") << s << "\n";
}
}</
Output:
<pre> ok:
Line 1,745 ⟶ 2,162:
=={{header|Ceylon}}==
<
platformRandom,
Random
Line 1,771 ⟶ 2,188:
ints.filter((i) => i != 0)
.scan(0)(plus<Integer>)
.every((i) => i >= 0);</
Output:
Line 1,788 ⟶ 2,205:
=={{header|Clojure}}==
<
(->> (concat (repeat n \[) (repeat n \]))
shuffle
Line 1,801 ⟶ 2,218:
(when (= (peek stack) \[)
(recur coll (pop stack))))
(zero? (count stack)))))</
There are other ways to express the <code>balanced?</code> function.
* We can use <code>reduce</code> to consume the sequence:
:<
(empty?
(reduce
Line 1,816 ⟶ 2,233:
(reduced [:UNDERFLOW]))))
'()
s)))</
* Only <code>[</code>s are put on the stack. We can just count the unmatched ones.
:<
(let [opens-closes (->> s
(map {\[ 1, \] -1})
(reductions + 0))]
(and (not-any? neg? opens-closes) (zero? (last opens-closes))))) </
Output:
Line 1,843 ⟶ 2,260:
=={{header|CLU}}==
<
% "misc.lib" that comes with PCLU.
Line 1,893 ⟶ 2,310:
end
end
end start_up</
{{out}}
<pre>"": balanced
Line 1,909 ⟶ 2,326:
=={{header|COBOL}}==
{{works with|OpenCOBOL}}
<
PROGRAM-ID. test-balanced-brackets.
Line 2,006 ⟶ 2,423:
.
END PROGRAM check-if-balanced.</
=={{header|CoffeeScript}}==
<
isBalanced = (brackets) ->
openCount = 0
Line 2,025 ⟶ 2,442:
for brackets in bracketsCombinations 4
console.log brackets, isBalanced brackets
</syntaxhighlight>
output
<syntaxhighlight lang="text">
> coffee balanced.coffee
[[[[ false
Line 2,045 ⟶ 2,462:
]]][ false
]]]] false
</syntaxhighlight>
=={{header|Common Lisp}}==
<
(defun string-of-brackets (n)
(let* ((len (* 2 n))
Line 2,076 ⟶ 2,493:
(let ((s (string-of-brackets i)))
(format t "~3A: ~A~%" (balancedp s) s))))
</syntaxhighlight>
Output:
Line 2,096 ⟶ 2,513:
=={{header|Component Pascal}}==
BlackBox Component Builder
<
MODULE Brackets;
IMPORT StdLog, Args, Stacks (* See Task Stacks *);
Line 2,157 ⟶ 2,574:
END Brackets.
</syntaxhighlight>
Execute: ^Q Brackets.Do [] [][] [[][]] ][ ][][ []][[]~<br/>
Output:
Line 2,170 ⟶ 2,587:
=={{header|Crystal}}==
<
(['[',']'] * n).shuffle.join # Implicit return
end
Line 2,195 ⟶ 2,612:
str = generate(i)
puts "#{str}: #{is_balanced(str)}"
end</
Output:
Line 2,213 ⟶ 2,630:
===Standard Version===
D standard library has a [http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html#balancedParens function] for this.
<
void main() {
Line 2,220 ⟶ 2,637:
writeln(s.balancedParens('[', ']') ? " OK: " : "bad: ", s);
}
}</
{{out}}
<pre> OK: []
Line 2,233 ⟶ 2,650:
===Imperative Version===
{{trans|Raku}}
<
bool isBalanced(in string txt) pure nothrow {
Line 2,255 ⟶ 2,672:
writeln(s.isBalanced ? " OK " : "Bad ", s);
}
}</
The output is similar.
===Functional Style===
{{trans|Haskell}}
<
bool isBalanced(in string s, in char[2] pars="[]") pure nothrow @safe @nogc {
Line 2,278 ⟶ 2,695:
writeln(s.isBalanced ? " OK " : "Bad ", s);
}
}</
=={{header|Delphi}}==
<
var BracketsStr : string;
Line 2,312 ⟶ 2,729:
writeln(BracketsStr+': not OK');
end;
end;</
<pre>
Line 2,327 ⟶ 2,744:
=={{header|Déjà Vu}}==
<
swap 0
for c in chars:
Line 2,345 ⟶ 2,762:
!. matching? "]["
!. matching? "][]["
!. matching? "[]][[]"</
{{out}}
<pre>true
Line 2,354 ⟶ 2,771:
false
false</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
func balanced code$ .
for i to len code$
h$ = substr code$ i 1
if h$ = "["
br += 1
elif h$ = "]"
br -= 1
.
if br < 0
return 0
.
.
return if br = 0
.
repeat
inp$ = input
until inp$ = "eof"
print inp$ & "\t" & balanced inp$
.
#
input_data
[]
[][]
[[][]]
][
][][
[]][[]
eof
</syntaxhighlight>
=={{header|EchoLisp}}==
<
(define (balance str)
(for/fold (closed 0) ((par str))
Line 2,385 ⟶ 2,835:
❌ "[[][]]]["
</syntaxhighlight>
=={{header|Ecstasy}}==
<syntaxhighlight lang="java">
module BalancedBrackets {
Boolean balanced(String text) {
Int depth = 0;
for (Char ch : text) {
switch (ch, depth) {
case ('[', _):
++depth;
break;
case (']', 0):
return False;
case (']', _):
--depth;
break;
}
}
return depth==0;
}
@Inject Console console;
void run() {
String[] tests =
[
"[]",
"[][]",
"[]][[]",
"[[[]][]]",
"][[[[]][]]",
"[[[]][[]][]]",
"]][[]][[[[][]]",
"[[]]]][]][[][[[]",
];
Int longest = tests.map(s -> s.size).reduce(0, (max, len) -> max.maxOf(len));
for (String test : tests) {
console.print($"{test}{' ' * (longest-test.size)} {balanced(test) ? "OK" : "NOT OK"}");
}
}
}
</syntaxhighlight>
{{out}}
<pre>
[] OK
[][] OK
[]][[] NOT OK
[[[]][]] OK
][[[[]][]] NOT OK
[[[]][[]][]] OK
]][[]][[[[][]] NOT OK
[[]]]][]][[][[[] NOT OK
</pre>
=={{header|Elena}}==
ELENA
<syntaxhighlight lang="elena">// Generate a string with N opening brackets ("[") and N 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.
import system'routines;
import extensions;
import extensions'text;
Line 2,395 ⟶ 2,902:
randomBrackets(len)
{
}
extension op
{
}
public program()
{
}</
{{out}}
<pre>
Line 2,452 ⟶ 2,959:
{{trans|Erlang}}
{{works with|Elixir|1.1}}
<
def task do
Enum.each(0..5, fn n ->
Line 2,478 ⟶ 2,985:
end
Balanced_brackets.task</
{{out}}
Line 2,491 ⟶ 2,998:
=={{header|Erlang}}==
<syntaxhighlight lang="erlang">
-module( balanced_brackets ).
-export( [generate/1, is_balanced/1, task/0] ).
Line 2,521 ⟶ 3,028:
task_balanced( true ) -> "OK";
task_balanced( false ) -> "NOT OK".
</syntaxhighlight>
{{out}}
<pre>
Line 2,534 ⟶ 3,041:
=={{header|Euphoria}}==
<
integer level
level = 0
Line 2,578 ⟶ 3,085:
puts(1," NOT OK\n")
end if
end for</
Sample output:
Line 2,600 ⟶ 3,107:
{{Works with|Office 365 betas 2021}}
<
=LAMBDA(bracketPair,
LAMBDA(s,
Line 2,685 ⟶ 3,192:
)
)
)</
and also assuming the following generic bindings in the Name Manager for the WorkBook:
<
=LAMBDA(xs,
LAMBDA(ys,
Line 2,798 ⟶ 3,305:
)
)
)</
{{Out}}
Line 2,913 ⟶ 3,420:
=={{header|F_Sharp|F#}}==
<
let rec loop count = function
| ']'::_ when count = 0 -> false
Line 2,934 ⟶ 3,441:
for n in 1..10 do
let s = generate n
printfn "\"%s\" is balanced: %b" s (isBalanced s)</
Output:
Line 2,949 ⟶ 3,456:
=={{header|Factor}}==
<syntaxhighlight lang="factor">USING: combinators formatting kernel math random sequences strings ;
IN: rosetta-code.balanced-brackets
: balanced? ( str -- ? )
0 swap [
{
{ CHAR: [ [ 1 + t ] }
{ CHAR: ] [ 1 - dup 0 >= ] }
[ drop t ]
} case
] all? swap zero? and ;
: bracket-pairs ( n -- str )
[ "[]" ] replicate "" concat-as ;
: balanced-brackets-main ( -- )
5 bracket-pairs randomize dup balanced? "" "not " ?
"String \"%s\" is %sbalanced.\n" printf ;
MAIN: balanced-brackets-main</syntaxhighlight>
The code below implements only the second part of the task: it reads from standard input an arbitrary string of opening and closing brackets, and checks whether it's balanced or not. Unlike the solution above, this one uses local variables.
<syntaxhighlight lang="factor">USING: io formatting locals kernel math sequences unicode.case ;
IN: balanced-brackets
Line 2,971 ⟶ 3,499:
readln
balanced</
=={{header|Fantom}}==
<
class Main
{
Line 3,039 ⟶ 3,543:
}
}
</syntaxhighlight>
Output (for n=3):
Line 3,067 ⟶ 3,571:
=={{header|Forth}}==
{{works with|4tH|3.61.1}}
<
include lib/ctos.4th ( n -- a 1)
Line 3,089 ⟶ 3,593:
; \ evaluate string and print result
make[] eval[]</
'''Examples''':<pre>[][[]] OK
[[[[]][[ NOT OK
Line 3,105 ⟶ 3,609:
=={{header|Fortran}}==
Please see the compilation and program execution result as comments at the top of this source:
<
! $ gfortran -g -O0 -std=f2008 -Wall f.f08 -o f.exe
! $ ./f
Line 3,203 ⟶ 3,707:
end subroutine generate
end program balanced_brackets
</syntaxhighlight>
=={{header|FreeBASIC}}==
<
Function isBalanced(s As String) As Boolean
Line 3,250 ⟶ 3,754:
Print
Print "Press any key to quit"
Sleep</
Sample output (last 7 lines random) :
{{out}}
Line 3,268 ⟶ 3,772:
][[[]][] NOT OK
[][[[[][ NOT OK
</pre>
=={{header|FutureBasic}}==
Filters out non-bracket characters prior to evaluation.
<syntaxhighlight lang="futurebasic">
include "NSLog.incl"
local fn BracketBalance( strWithBracket as CFStringRef ) as CFStringRef
NSInteger i, bracketTracker = 0
CFStringRef result
CFCharacterSetRef bracketSet = fn CharacterSetWithCharactersInString( @"[]" )
CFCharacterSetRef bracketsOnlySet = fn CharacterSetInvertedSet( bracketSet )
CFArrayRef trimmedSArray = fn StringComponentsSeparatedByCharactersInSet( strWithBracket, bracketsOnlySet )
CFStringRef trimmedStr = fn ArrayComponentsJoinedByString( trimmedSArray, @"" )
NSUInteger strLen = len( trimmedStr )
// Empty string, no brackets
if ( strLen == 0 ) then result = @"No brackets" : exit fn
// String with odd number of brackets is unbalanced
if ( strLen mod 2 ) then result = @"Unbalanced" : exit fn
for i = 0 to strLen - 1
CFStringRef bracket = fn StringWithFormat( @"%C", fn StringCharacterAtIndex( trimmedStr, i ) )
if fn StringisEqual( bracket, @"[" ) then bracketTracker++
if fn StringisEqual( bracket, @"]" ) then bracketTracker--
if bracketTracker < 0 then result = @"Unbalanced" : break
next
if bracketTracker == 0 then result = @"Balanced"
end fn = result
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"" ) ), @"" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[" ) ), @"[" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"]" ) ), @"]" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[]" ) ), @"[]" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[[]" ) ), @"[[]" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[]]" ) ), @"[]]" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[][]" ) ), @"[][]" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"][" ) ), @"][" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"][][" ) ), @"][][" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[[]][][][[][]]" ) ), @"[[]][][][[][]]" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"][[]][][][]]][[" ) ), @"][[]][][][]]][[" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[[[abc]][[d]]]]]" ) ), @"[[[abc]][[def]]]]]" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[[[abc]]][[[[[d]]]]]" ) ), @"[[[abc]]][[[[[def]]]]]" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"[][abc]]][[[[[d]]]]]" ) ), @"[][abc]]][[[[[def]]]]]" )
NSLog( @"%12s: %@", fn StringUTF8String( fn BracketBalance( @"The quick brown fox" ) ), @"The quick brown fox" )
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
No brackets:
Unbalanced: [
Unbalanced: ]
Balanced: []
Unbalanced: [[]
Unbalanced: []]
Balanced: [][]
Unbalanced: ][
Unbalanced: ][][
Balanced: [[]][][][[][]]
Unbalanced: ][[]][][][]]][[
Unbalanced: [[[abc]][[def]]]]]
Balanced: [[[abc]]][[[[[def]]]]]
Unbalanced: [][abc]]][[[[[def]]]]]
No brackets: The quick brown fox
</pre>
=={{header|Gambas}}==
'''[https://gambas-playground.proko.eu/?gist=8960fb267af43f0549d2cfe04288a2d4 Click this link to run this code]'''
<
siNumberOfBrackets As Short = 20 'Maximum amount of brackets in a line
Line 3,344 ⟶ 3,916:
Return sBrk 'Return the sBrk array
End</
Output:
<pre>
Line 3,366 ⟶ 3,938:
=={{header|GAP}}==
<
local c, r;
r := 0;
Line 3,401 ⟶ 3,973:
Balanced("[[[]][]]]");
# false</
=={{header|GDScript}}==
{{works with|Godot|4.0}}
<syntaxhighlight lang="gdscript">
extends MainLoop
func generate_brackets(n: int) -> String:
var brackets: Array[String] = []
# Add opening and closing brackets
brackets.resize(2*n)
for i in range(0, 2*n, 2):
brackets[i] = "["
brackets[i+1] = "]"
brackets.shuffle()
return "".join(brackets)
func is_balanced(str: String) -> bool:
var unclosed_brackets := 0
for c in str:
match c:
"[":
unclosed_brackets += 1
"]":
if unclosed_brackets == 0:
return false
unclosed_brackets -= 1
_:
return false
return unclosed_brackets == 0
func _process(_delta: float) -> bool:
randomize()
for i in range(6):
var bracket_string := generate_brackets(i)
if is_balanced(bracket_string):
print("%sOK" % bracket_string.rpad(13))
else:
print("%sNOT OK" % bracket_string.rpad(11))
return true # Exit
</syntaxhighlight>
=={{header|Go}}==
<
import (
Line 3,457 ⟶ 4,075:
}
testBalanced("()")
}</
Output:
<pre>
Line 3,475 ⟶ 4,093:
=={{header|Groovy}}==
Generate Arbitrary String of Bracket Pairs:
<
def factorial = { (it > 1) ? (2..it).inject(1) { i, j -> i*j } : 1 }
Line 3,495 ⟶ 4,113:
def p = random.nextInt(factorial(n*2))
makePermutation(base, p)
}</
Check Balance of Bracket String:
<
if (brackets == null || brackets.empty) return depth == 0
switch (brackets[0]) {
Line 3,508 ⟶ 4,126:
return brackets.size() == 1 ? depth == 0 : balancedBrackets(brackets[1..-1], depth)
}
}</
Test:
<
(0..100).each {
(0..8).each { r ->
Line 3,523 ⟶ 4,141:
def bal = balancedBrackets(it) ? "balanced: " : "unbalanced: "
println "${bal} ${it}"
}</
Output:
Line 3,722 ⟶ 4,340:
=={{header|Haskell}}==
The simplest solution exploits the idea of stack-based automaton, which could be implemented by a fold.
<
isMatching :: String -> Bool
isMatching = null . foldl aut []
Line 3,729 ⟶ 4,347:
-- aut ('{':s) '}' = s -- automaton could be extended
aut s x = x:s
</syntaxhighlight>
This generates an infinite stream of correct balanced brackets expressions:
<
$ [1.. ] >>= (`replicateM` "[]{}") </
<pre>λ> take 10 brackets
["[]","{}","[[]]","[][]","[]{}","[{}]","{[]}","{{}}","{}[]","{}{}"]</pre>
Line 3,740 ⟶ 4,358:
In case the index of unmatched opening bracket is need to be found, following solution is suitable.
<
import Control.Monad
import System.Random
Line 3,771 ⟶ 4,389:
let bs = cycle "[]"
rs <- replicateM 10 newStdGen
zipWithM_ (\n r -> check $ shuffle (take n bs) r) [0,2 ..] rs</
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.
<
( shuffle
) where
Line 3,802 ⟶ 4,420:
do v <- V.unsafeThaw $ V.fromList xs
mapM_ (uncurry $ M.swap v) $ pairs 0 (M.length v - 1) r
V.unsafeFreeze v</
Here's some sample output.
<pre>
Line 3,827 ⟶ 4,445:
and '''scanl''' also yields a simple fit when we want the index of the tipping point:
<
import Data.List (findIndex, replicate, scanl)
import Data.List.Split (chunksOf)
Line 3,833 ⟶ 4,451:
-------------------- BALANCED BRACKETS -------------------
nesting :: String -> [Int]
nesting = tail . scanl (flip level) 0
where
level '[' = succ
level ']' = pred
level _ = id
bracketProblemIndex :: String -> Maybe Int
Line 3,843 ⟶ 4,469:
| otherwise = Nothing
--------------------------- TEST -------------------------
Line 3,866 ⟶ 4,486:
bracket :: Int -> Char
bracket 0 = '['
bracket _ = ']'</
{{Out}}
<pre>]][]][: Unmatched
Line 3,891 ⟶ 4,511:
=={{header|Icon}} and {{header|Unicon}}==
<
every s := genbs(!arglist) do
write(image(s), if isbalanced(s) then " is balanced." else " is unbalanced")
Line 3,905 ⟶ 4,525:
every !s := ?s # shuffle
return s
end</
Output:<pre>
Line 3,923 ⟶ 4,543:
=={{header|J}}==
'''Solution''': <
checkBalanced =: _1 -.@e. bracketDepth
genBracketPairs =: (?~@# { ])@#"0 1&'[]' NB. bracket pairs in arbitrary order</
'''Examples''':<
OK
][ bad
Line 3,936 ⟶ 4,556:
[[]][[][][]][] OK
]]]][[][][[[[]][ bad
[]]][][][[[[]][[]] bad</
'''Comments''': This task highlights the versatility and usefulness of J's scanning modifiers, <code>/</code> and <code>\</code>.
Line 3,943 ⟶ 4,563:
=={{header|Java}}==
{{works with|Java|1.5+}}
<
public static boolean hasBalancedBrackets(String str) {
Line 3,991 ⟶ 4,611:
}
}
}</
Sample output (generate uses random numbers, so it should not be the same every time):
<pre>: true
Line 4,011 ⟶ 4,631:
=== Extended ===
<
import java.util.Deque;
Line 4,074 ⟶ 4,694:
}
}
}</
{{out}}
<pre>With areSquareBracketsBalanced:
Line 4,101 ⟶ 4,721:
====Iterative====
<
var a = str.split(''), b, c = a.length, d
while (c) b = Math.random() * c-- | 0, d = a[c], a[c] = a[b], a[b] = d
Line 4,117 ⟶ 4,737:
var N = Math.random() * 10 | 0, bs = shuffle('['.repeat(N) + ']'.repeat(N))
console.log('"' + bs + '" is ' + (isBalanced(bs) ? '' : 'un') + 'balanced')
}</
Sample output:
Line 4,144 ⟶ 4,764:
==== Another solution ====
{{works with|Node.js}}
<syntaxhighlight lang="javascript">
console.log("Supplied examples");
var tests = ["", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]"];
Line 4,201 ⟶ 4,821:
return generated;
}
</syntaxhighlight>
{{out}}
<pre>
Line 4,229 ⟶ 4,849:
====Functional====
With visual indication of where the balance fails:
<
'use strict';
Line 4,333 ⟶ 4,953:
// ---
return main();
})();</
{{Out}}
<pre>'' OK
Line 4,346 ⟶ 4,966:
']]][[][][][]' problem
^</pre>
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq.'''
In this entry, two solutions are given: the first uses
an external source of entropy and jq's `until` control structure;
the second uses a low-entropy PRNG based on jq's `now`,
and `gsub/2.`
===High entropy solution using `until`===
<syntaxhighlight lang=bash>
< /dev/random tr -cd '0-9' | fold -w 1 | jq -Mcnr '
# Output: a PRN in range(0;$n) where $n is .
def prn:
if . == 1 then 0
else . as $n
| (($n-1)|tostring|length) as $w
| [limit($w; inputs)] | join("") | tonumber
| if . < $n then . else ($n | prn) end
end;
def prb: 2 | prn == 0;
def balanced:
{array: explode, parity: 0}
| until( .result | type == "boolean";
if .array == [] then .result = (.parity == 0)
else .parity += (.array[0] | if . == 91 then 1 else -1 end)
| if .parity < 0 then .result = false
else .array |= .[1:]
end
end ).result ;
def task($n):
if $n%2 == 1 then null
else [ (range(0; $n) | if prb then "[" else "]" end) // ""]
| add
| "\(.): \(balanced)"
end;
task(0),
task(2),
(range(0;10) | task(4))
</syntaxhighlight>
{{output}}
<pre>
: true
[[: false
[][[: false
][[[: false
]][[: false
[[]]: true
]][[: false
][[[: false
[[[[: false
[][[: false
][[[: false
[]][: false
</pre>
===Low entropy solution with `gsub`===
<syntaxhighlight lang=jq>
def prb: (now|tostring[-1:] | tonumber) % 2 == 0;
def balanced:
if length==0 then true
elif .[:1] == "]" then false
else test("[[][]]") and (gsub("[[][]]"; "") | balanced)
end;
def task($n):
if $n%2 == 1 then null
else
(reduce range(0; $n) as $i ("";
. + (if prb then "[" else "]" end) ))
| "\(.): \(balanced)"
end;
task(0),
task(2),
(range(0;10) | task(4))
</syntaxhighlight>
{{output}}
Similar to above.
=={{header|Julia}}==
<
function balancedbrackets(str::AbstractString)
Line 4,363 ⟶ 5,067:
for (test, pass) in map(x -> (x, balancedbrackets(x)), collect(brackets(i) for i = 0:8))
@printf("%22s%10s\n", test, pass ? "pass" : "fail")
end</
{{out}}
Line 4,377 ⟶ 5,081:
'''One-line version''':
<
=={{header|K}}==
<syntaxhighlight lang="k">
gen_brackets:{"[]"@x _draw 2}
check:{r:(-1;1)@"["=x; *(0=+/cs<'0)&(0=-1#cs:+\r)}
Line 4,395 ⟶ 5,099:
("][[][[]]][[]]]][][";0)
("]][[[[]]]][][][[]]]]";0))
</syntaxhighlight>
=={{header|Klingphix}}==
<syntaxhighlight lang="text">"[[]][]]"
%acc 0 !acc
Line 4,415 ⟶ 5,119:
print
" " input</
=={{header|Kotlin}}==
{{trans|FreeBASIC}}
<
fun isBalanced(s: String): Boolean {
Line 4,450 ⟶ 5,154:
println("$s " + if (isBalanced(s)) "OK" else "NOT OK")
}
}</
Sample output (last 7 lines random) :
{{out}}
Line 4,474 ⟶ 5,178:
=={{header|L++}}==
<
(defn bool balanced (std::string s)
Line 4,488 ⟶ 5,192:
(pr std::boolalpha)
(foreach x tests
(prn x "\t" (balanced x))))</
=={{header|Lasso}}==
<
local(out) = array
Line 4,512 ⟶ 5,216:
with i in 1 to 10
let input = randomparens(#i)
select #input + ' = ' + validateparens(#input)</
{{out}}
Line 4,526 ⟶ 5,230:
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
print "Supplied examples"
for i =1 to 7
Line 4,589 ⟶ 5,293:
end
</syntaxhighlight>
Supplied examples
The string '' is OK.
Line 4,612 ⟶ 5,316:
=={{header|Lua}}==
<syntaxhighlight lang="lua">
function isBalanced(s)
--Lua pattern matching has a 'balanced' pattern that matches sets of balanced characters.
Line 4,633 ⟶ 5,337:
print(RS)
print(isBalanced(RS))
</syntaxhighlight>
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
module Balanced_brackets{
// Generate a string with N opening brackets [ and with N closing brackets ], in some arbitrary order.
function randomBrackets(max as long) {
if max<1 then max=1
def putbracket()=mid$("[[[[]]",random(1,6),1)
dim a(random(1, max)) as string<<putbracket()
=a()#str$("")
}
// 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.
function check(s as string) {
long i, level
for i=1 to len(s)
if mid$(s,i,1)="[" then level++ else level--
if level<0 then exit for
next
=level=0
}
string k
boolean m
do
k=randomBrackets(10)
m=check(k)
print k;@(12);": ";if$(m->"OK", "NOT OK")
until m
}
Balanced_brackets
</syntaxhighlight>
{{out}}
<pre>
[[[] : NOT OK
[[][]] : OK
</pre>
=={{header|Maple}}==
This functionality is provided by Maple.
<syntaxhighlight lang="maple">
> use StringTools in
> IsBalanced( "", "[", "]" );
Line 4,669 ⟶ 5,409:
false
</syntaxhighlight>
Furthermore, Maple can check whether multiple fences are balanced in the same string.
<syntaxhighlight lang="maple">
> StringTools:-IsBalanced( "[()()]", "[(", "])" );
true
</syntaxhighlight>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
gen[n_] := RandomSample[Table[{1, -1}, {n}] // Flatten]
Line 4,689 ⟶ 5,429:
Print[str <> If[match[lst, 0],
" is balanced.",
" is not balanced."]])</
=={{header|MATLAB}} / {{header|Octave}}==
<
t = cumsum((s=='[') - (s==']'));
x = all(t>=0) && (t(end)==0);
end;
</syntaxhighlight>
Output:
<pre>
Line 4,715 ⟶ 5,455:
=={{header|Maxima}}==
<
[n: slength(s), r: 0, c],
catch(
Line 4,745 ⟶ 5,485:
brack("[[[]][]]]");
false</
=={{header|Mercury}}==
<syntaxhighlight lang="mercury">
:- module balancedbrackets.
:- interface.
Line 4,789 ⟶ 5,529:
; print(" is unbalanced\n", !IO)
).
</syntaxhighlight>
=={{header|MiniScript}}==
Line 4,795 ⟶ 5,535:
We start by defining a function:
<
level = 0
for c in str
Line 4,803 ⟶ 5,543:
end for
return level == 0
end function</
We can evaluate the example strings with this code:
<
"",
"[]",
Line 4,821 ⟶ 5,561:
if balanced then outcome = "is OK" else outcome = "NOT OK"
print """" + str + """ " + outcome
end for</
{{out}}
Line 4,836 ⟶ 5,576:
{{works with|TopSpeed (JPI) Modula-2 under DOSBox-X}}
An interesting point is how to ensure that all strings of N left plus N right brackets are equally likely. The program below shows one way of doing this.
<
MODULE Brackets;
IMPORT IO, Lib;
Line 4,884 ⟶ 5,624:
END;
END Brackets.
</syntaxhighlight>
{{out}}
<pre>
Line 4,901 ⟶ 5,641:
=={{header|Nanoquery}}==
{{trans|Python}}
<
def gen(N)
Line 4,933 ⟶ 5,673:
println format("%-22s is not balanced", txt)
end
end</
{{out}}
<pre> is balanced
Line 4,948 ⟶ 5,688:
=={{header|Nim}}==
<
from random import random, randomize, shuffle
from strutils import repeat
Line 4,972 ⟶ 5,712:
for n in 0..9:
let s = gen(n)
echo "'", s, "' is ", (if balanced(s): "balanced" else: "not balanced")</
Output:
<pre>'' is balanced
Line 4,984 ⟶ 5,724:
'][[][]]]][[[[][]' is not balanced
'][][][][][[][[]]][' is not balanced</pre>
=={{header|Nu}}==
<syntaxhighlight lang="nu">
def gen_brackets [n: int] { 1..$in | each {["[" "]"]} | flatten | shuffle | str join }
def check_brackets [] {
split chars | reduce --fold 0 {|x, d|
if ($d < 0) {-1} else {
$d + (if ($x == "[") {1} else {-1})
}
} | $in > -1
}
1..10 | each {gen_brackets $in | {brackets: $in, valid: ($in | check_brackets)}} | print
</syntaxhighlight>
{{out}}
<pre>
╭───┬──────────────────────┬───────╮
│ # │ brackets │ valid │
├───┼──────────────────────┼───────┤
│ 0 │ ][ │ false │
│ 1 │ []][ │ false │
│ 2 │ [[][]] │ true │
│ 3 │ [[[][]]] │ true │
│ 4 │ ]]][[[[][] │ false │
│ 5 │ [][][][[[]]] │ true │
│ 6 │ ]]]]][]][[[[[[ │ false │
│ 7 │ ][[][]]]][[][[[] │ false │
│ 8 │ []]]][][][[][]][[[ │ false │
│ 9 │ ][][][[[[[]]]][[]][] │ false │
╰───┴──────────────────────┴───────╯
</pre>
=={{header|Oberon-2}}==
{{works with|oo2c version 2}}
<
MODULE BalancedBrackets;
IMPORT
Line 5,090 ⟶ 5,863:
Do
END BalancedBrackets.
</syntaxhighlight>
{{out}}
<pre>
Line 5,102 ⟶ 5,875:
=={{header|Objeck}}==
<
bundle Default {
class Balanced {
Line 5,135 ⟶ 5,908:
}
}
</syntaxhighlight>
<pre>
: true
Line 5,148 ⟶ 5,921:
=={{header|OCaml}}==
<
let rec aux i acc =
if i <= 0 then acc else
Line 5,172 ⟶ 5,945:
List.iter print_char brk;
Printf.printf " %B\n" (is_balanced brk);
;;</
<pre>
Line 5,183 ⟶ 5,956:
=={{header|Oforth}}==
<
| c |
0 self forEach: c [
Line 5,193 ⟶ 5,966:
: genBrackets(n)
"" #[ "[" "]" 2 rand 2 == ifTrue: [ swap ] rot + swap + ] times(n) ;</
{{out}}
Line 5,211 ⟶ 5,984:
=={{header|ooRexx}}==
<syntaxhighlight lang="oorexx">
tests = .array~of("", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]")
Line 5,259 ⟶ 6,032:
end
return answer~string
</syntaxhighlight>
Sample output (uses randomly generated groupings, so it should be different on each run):
<pre>
Line 5,280 ⟶ 6,053:
=={{header|OxygenBasic}}==
<
'=======================================
sys co, le=len s
Line 5,307 ⟶ 6,080:
print CheckBrackets "[][]"'1
print CheckBrackets "][" '0
</syntaxhighlight>
=={{header|PARI/GP}}==
<
my(n=0,v=Vecsmall(s));
for(i=1,#v,
Line 5,322 ⟶ 6,095:
};
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")))</
=={{header|Pascal}}==
Line 5,331 ⟶ 6,104:
Idiomatic solution, using a regex that performs subpattern recursion ''(works with Perl 5.10 and newer)'':
<
my $n = shift;
my $str = '[' x $n;
Line 5,345 ⟶ 6,118:
my $input = generate($_);
print balanced($input) ? " ok:" : "bad:", " '$input'\n";
}</
{{out}}
Line 5,362 ⟶ 6,135:
If input strings are allowed to contain unrelated characters, this can be extended to:
<
shift =~ /^ ( [^\[\]]++ | \[ (?1)* \] )* $/x;
}</
<code>Regexp::Common::balanced</code> can give such a regexp too (
<
sub balanced {
return shift =~
}
</syntaxhighlight>
Alternative implementation, using straightforward depth counting:
<
my $depth = 0;
for (split //, shift) {
Line 5,383 ⟶ 6,156:
}
return !$depth
}</
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">check_brackets</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
Line 5,409 ⟶ 6,182:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
{{out}}
<pre>
Line 5,435 ⟶ 6,208:
=={{header|Phixmonti}}==
<
0 var acc
Line 5,451 ⟶ 6,224:
" is OK"
endif
print</
=={{header|PHP}}==
The sample is given as unix shell script, you need to have ''php-cli'' (or what your package manager calls it) installed.
<
<?php
Line 5,489 ⟶ 6,262:
printf("%s\t%s%s", $s, printbool(isbalanced($s)), PHP_EOL);
}
</syntaxhighlight>
Sample run:
<pre>
Line 5,507 ⟶ 6,280:
=={{header|Picat}}==
===Foreach loop===
<
tests(Tests),
member(Test,Tests),
Line 5,531 ⟶ 6,304:
"][][", "[]][[]", "[][][][][][][][][][]",
"[[[[[[[]]]]]]]", "[[[[[[[]]]]]]",
"[][[]][]","[[][]][]", "[][][[]][]"]).</
{{out}}
Line 5,550 ⟶ 6,323:
===DCG===
Here is an implementation using DCG (Definite Clause Grammars).
<
tests(Tests),
foreach(Test in Tests)
Line 5,564 ⟶ 6,337:
balanced --> "".
balanced --> "[", balanced, "]", balanced.</
=={{header|PicoLisp}}==
<
(de generateBrackets (N)
Line 5,583 ⟶ 6,356:
(for N 10
(prinl (if (checkBrackets (prin (generateBrackets N))) " OK" "not OK")) )</
Output:
<pre>[] OK
Line 5,597 ⟶ 6,370:
=={{header|PL/I}}==
<
cb: Proc Options(main);
/* PL/I program to check for balanced brackets [] ********************
Line 5,658 ⟶ 6,431:
End;
End;</
Output:
<pre> balanced ''
Line 5,689 ⟶ 6,462:
=={{header|PowerShell}}==
{{works with|PowerShell|2}}
<syntaxhighlight lang="powershell">
function Get-BalanceStatus ( $String )
{
Line 5,708 ⟶ 6,481:
return $Status
}
</syntaxhighlight>
<syntaxhighlight lang="powershell">
# Test
$Strings = @( "" )
Line 5,718 ⟶ 6,491:
$String.PadRight( 12, " " ) + (Get-BalanceStatus $String)
}
</syntaxhighlight>
{{out}}
<pre>
Line 5,731 ⟶ 6,504:
===PowerShell (Regex Version)===
<syntaxhighlight lang="powershell">
function Test-BalancedBracket
{
Line 5,789 ⟶ 6,562:
"{0}: {1}" -f $s.PadRight(8), "$(if (Test-BalancedBracket Brace $s) {'Is balanced.'} else {'Is not balanced.'})"
}
</syntaxhighlight>
{{Out}}
<pre>
Line 5,803 ⟶ 6,576:
=={{header|Prolog}}==
DCG are very usefull for this kind of exercice !
<
test_brackets([]),
test_brackets(['[',']']),
Line 5,855 ⟶ 6,628:
bracket(0) --> ['['].
bracket(1) --> [']'].
</syntaxhighlight>
Sample output :
<pre> ?- balanced_brackets.
Line 5,882 ⟶ 6,655:
=={{header|PureBasic}}==
<
For i=1 To N
sample$+"[]"
Line 5,925 ⟶ 6,698:
PrintN(" is not balanced")
EndIf
Next</
Output sample
<pre>
Line 5,937 ⟶ 6,710:
=={{header|Python}}==
===Procedural===
<
... txt = ['[', ']'] * N
... random.shuffle( txt )
Line 5,963 ⟶ 6,736:
'[[]]]]][]][[[[' is not balanced
'[[[[]][]]][[][]]' is balanced
'][[][[]]][]]][[[[]' is not balanced</
=== Functional ===
Line 5,969 ⟶ 6,742:
Rather than explicitly track the count, we can just write the per-element test and use stdlib functions to turn it into a whole-sequence test. It's straightforwardly declarative, and hard to get wrong, but whether it's actually easier to understand depends on how familiar the reader is with thinking in `itertools` style.
<
>>> from random import shuffle
>>> def gen(n):
Line 5,992 ⟶ 6,765:
'][]][][[]][[][' is not balanced
'][[]]][][[]][[[]' is not balanced
'][[][[]]]][[[]][][' is not balanced</
=== Array Programming ===
Line 5,998 ⟶ 6,771:
The numpy library gives us a way to write just the elementwise tests and automatically turn them into whole-sequence tests, although it can be a bit clumsy to use for character rather than numeric operations. The simplicity of the final expression probably doesn't make up for all that extra clumsiness in this case.
<
>>> from random import shuffle
>>> def gen(n):
Line 6,022 ⟶ 6,795:
'[][[[]][[]]][]' is balanced
'[[][][[]]][[[]]]' is balanced
'][]][][[]][]][][[[' is not balanced</
=={{header|Qi}}==
<
[] 0 -> true
[] _ -> false
Line 6,048 ⟶ 6,821:
(balanced-brackets "[]][[]")
</syntaxhighlight>
=={{header|Quackery}}==
<
swap
char ] swap of
Line 6,072 ⟶ 6,845:
[ say "un" ]
say "balanced."
cr ]</
{{out}}
Line 6,091 ⟶ 6,864:
=={{header|R}}==
<
str <- strsplit(str, "")[[1]]
str <- ifelse(str=='[', 1, -1)
all(cumsum(str) >= 0) && sum(str) == 0
}</
Alternately, using perl 5.10-compatible regexps,
<
regexpr('^(\\[(?1)*\\])*$', str, perl=TRUE) > -1
}</
To generate some some examples:
<
as.data.frame(within(list(), {
parens <- replicate(10, rand.parens(sample.int(10,size=1)))
balanced <- sapply(parens, balanced)
}))</
Output:
<
1 FALSE ][][
2 FALSE [][[]]][[]][]]][[[
Line 6,123 ⟶ 6,896:
8 FALSE []]]][[[]][[[]
9 TRUE [[[[][[][]]]]]
10 TRUE []</
=={{header|Racket}}==
<syntaxhighlight lang="racket">
#lang racket
Line 6,145 ⟶ 6,918:
(for ([n 10]) (try n))
</syntaxhighlight>
=={{header|Raku}}==
Line 6,154 ⟶ 6,927:
{{works with|Rakudo|2015.12}}
<syntaxhighlight lang="raku"
my $l = 0;
for $s.comb {
Line 6,170 ⟶ 6,943:
my $n = prompt "Number of brackets";
my $s = (<[ ]> xx $n).flat.pick(*).join;
say "$s {balanced($s) ?? "is" !! "is not"} well-balanced"</
===FP oriented===
Here's a more idiomatic solution using a hyperoperator to compare all the characters to a backslash (which is between the brackets in ASCII), a triangle reduction to return the running sum, a <tt>given</tt> to make that list the topic, and then a topicalized junction and a topicalized subscript to test the criteria for balance.
<syntaxhighlight lang="raku"
.none < 0 and .[*-1] == 0
given ([\+] '\\' «leg« $s.comb).cache;
Line 6,181 ⟶ 6,954:
my $n = prompt "Number of bracket pairs: ";
my $s = <[ ]>.roll($n*2).join;
say "$s { balanced($s) ?? "is" !! "is not" } well-balanced"</
===String munging===
Of course, a Perl 5 programmer might just remove as many inner balanced pairs as possible and then see what's left.
{{works with|Rakudo|2015.12}}
<syntaxhighlight lang="raku"
Nil while s:g/'[]'//;
$_ eq '';
Line 6,193 ⟶ 6,966:
my $n = prompt "Number of bracket pairs: ";
my $s = <[ ]>.roll($n*2).join;
say "$s is", ' not' x not balanced($s), " well-balanced";</
===Parsing with a grammar===
{{works with|Rakudo|2015.12}}
<syntaxhighlight lang="raku"
my $n = prompt "Number of bracket pairs: ";
my $s = ('[' xx $n, ']' xx $n).flat.pick(*).join;
say "$s { BalBrack.parse($s) ?? "is" !! "is not" } well-balanced";</
=={{header|Red}}==
<
balanced-brackets: [#"[" any balanced-brackets #"]"]
rule: [any balanced-brackets end]
Line 6,225 ⟶ 6,998:
str: random copy/part "[][][][][][][][][][]" i * 2
print [mold str "is" either balanced? str ["balanced"]["unbalanced"]]
]</
=={{header|REXX}}==
===with 40 examples===
<
parse arg seed . /*obtain optional argument from the CL.*/
if datatype(seed,'W') then call random ,,seed /*if specified, then use as RANDOM seed*/
Line 6,267 ⟶ 7,040:
else do; !=!-1; if !<0 then return 0; end
end /*j*/
return !==0 /* [↑] "!" is the nested ][ counter.*/</
'''output''' using the (some internal, others random) expressions:
<pre>
Line 6,313 ⟶ 7,086:
===with examples + 30 permutations===
<
/*REXX program to check for balanced brackets [] **********************
* test strings and random string generation copied from Version 1
Line 6,381 ⟶ 7,154:
end
return nest=0 /* nest=0 -> balanced */
</syntaxhighlight>
{{out}}
<pre>
Line 6,430 ⟶ 7,203:
Naturally, each of the one hundred thousand character strings aren't displayed (for balanced/not-balanced),
<br>but a count is displayed, as anyone can generate the same strings in other languages and compare results.
<
bals=0
#=0; do j=1 until L>20 /*generate lots of bracket permutations*/
Line 6,450 ⟶ 7,223:
/*──────────────────────────────────────────────────────────────────────────────────────*/
countStr: procedure; parse arg n,h,s; if s=='' then s=1; w=length(n)
do r=0 until _==0; _=pos(n,h,s); s=_+w; end; return r</
'''output''' when using the default input:
<pre>
Line 6,457 ⟶ 7,230:
=={{header|Ring}}==
<
nr = 0
while nr < 10
Line 6,484 ⟶ 7,257:
next
return "ok."
</syntaxhighlight>
Output:
<pre>
Line 6,497 ⟶ 7,270:
bracket string [[]] is ok.
bracket string ]]]][]]]]]]]]] is not ok.
</pre>
=={{header|RPL}}==
{{works with|Halcyon Calc|4.2.7}}
≪
1 OVER SIZE
'''WHILE''' DUP2 * 0 > '''REPEAT'''
3 PICK OVER DUP SUB
'''IF''' "[]" SWAP POS '''THEN'''
LAST 2 * 3 - ROT + SWAP '''END'''
1 -
'''END''' DROP
1 SAME "" "Not " '''IFTE''' "OK" +
≫ ''''BALBKT'''' STO
≪ { "" "[]" "[][]" "[[][]]" "][" "][][" "[]][[]" } → ts
≪
1 ts SIZE '''FOR''' j
ts j GET '''BALBKT''' " → " SWAP + + '''NEXT'''
≫ ≫ ''''TASK'''' STO
{{out}}
<pre>
" → OK"
"[] → OK"
"[][] → OK"
"[[][]] → OK"
"][ → Not OK"
"][][ → Not OK"
"[]][[] → Not OK"
</pre>
Line 6,502 ⟶ 7,304:
{{trans|D}}
{{works with|Ruby|1.9}}
<
(?<bb> # begin capture group <bb>
\[ # literal [
Line 6,518 ⟶ 7,320:
t = s.gsub(/[^\[\]]/, "")
puts (t =~ re ? " OK: " : "bad: ") + s
end</
One output: <pre>
Line 6,537 ⟶ 7,339:
=={{header|Run BASIC}}==
<
brk$(1) = "[[[][]]]"
brk$(2) = "[[[]][[[][[][]]]]]"
Line 6,557 ⟶ 7,359:
if trim$(b$) = "" then print " OK "; else print "Not OK ";
print brk$(i)
next i</
One output: <pre> OK
Line 6,575 ⟶ 7,377:
{{libheader|rand}}
<
trait Balanced {
Line 6,614 ⟶ 7,416:
println!("{} {}", brackets, brackets.is_balanced())
}
}</
Output: <pre>
true
Line 6,634 ⟶ 7,436:
=== Scala Version 1 ===
{{works with|Scala|2.9.1}}
<
import scala.util.Random
Line 6,669 ⟶ 7,471:
println("\n"+"check all permutations of given length:")
(1 to 5).map(generate(_)).flatten.map(s=>Pair(s,checkBalance(s))).foreach(p=>println((if(p._2) "balanced: " else "unbalanced: ")+p._1))
}</
<pre style="height:30ex;overflow:scroll">arbitrary random order:
Line 7,045 ⟶ 7,847:
=== Scala Version 2 ===
{{works with|Scala|2.10.1}}
<
object BalancedBracketsApp extends App {
Line 7,072 ⟶ 7,874:
}
}</
Alternate implementation of "isBalanced" using tail-recursion instead of var and return:
<
import scala.annotation.tailrec
Line 7,095 ⟶ 7,897:
isBalanced(rest, newBalance)
}
</syntaxhighlight>
Slightly modified implementation of "isBalanced" using tail-recursion
{{works with|Scala|2.11.7}}
<
@scala.annotation.tailrec
final def isBalanced(
Line 7,118 ⟶ 7,920:
}
}
</syntaxhighlight>
Sample output:
Line 7,135 ⟶ 7,937:
=={{header|Scheme}}==
<
(define (b chars sum)
(cond ((< sum 0)
Line 7,160 ⟶ 7,962:
(balanced-brackets "][][")
(balanced-brackets "[]][[]")
</syntaxhighlight>
=={{header|Scilab}}==
{{trans|MATLAB}}
<syntaxhighlight lang="text">function varargout=isbb(s)
st=strsplit(s);
t=cumsum((st=='[')-(st==']'));
balanced=and(t>=0) & t(length(t))==0;
varargout=list(balanced)
endfunction</
{{out}}
The following code was used to generate random strings of length 5, 16, and 22 chars. It also displays the generated string, and the output (true of false) of <code>isbb()</code>.
<syntaxhighlight lang="text">for j=[5 16 22]
s=[];
for i=1:j
Line 7,185 ⟶ 7,987:
x=isbb(s);
disp(x);
end</
Console output:
<pre> ][]][
Line 7,200 ⟶ 8,002:
=={{header|Seed7}}==
<
const func string: generateBrackets (in integer: count) is func
Line 7,252 ⟶ 8,054:
end for;
end for;
end func;</
Output:
Line 7,273 ⟶ 8,075:
</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program balanced_brackets;
setrandom(0);
loop for length in [1..10] do
s := generate length;
print(balanced s, s);
end loop;
op generate(n);
s := "["*n + "]"*n;
loop for i in [n*2, n*2-1..2] do
j := 1 + random(i - 1);
[s(i), s(j)] := [s(j), s(i)];
end loop;
return s;
end op;
op balanced(s);
depth := 0;
loop for c in s do
case c of
("["):
depth +:= 1;
("]"):
depth -:= 1;
if depth<0 then return false; end if;
end case;
end loop;
return depth = 0;
end op;
end program;</syntaxhighlight>
{{out}}
<pre>#F ][
#F ]][[
#T [[]][]
#F [[]]][][
#F ][[][][]][
#F ]][]]]][[[[[
#F ]]][[]]][[[[[]
#T [[][][[][[]][]]]
#F []][[]]]][][][[][[
#F []][]]][]][][[[][[][</pre>
=={{header|Sidef}}==
<
var depth = 0
Line 7,287 ⟶ 8,132:
for str [']','[','[[]','][]','[[]]','[[]]]][][]]','x[ y [ [] z ]][ 1 ][]abcd'] {
printf("%sbalanced\t: %s\n", balanced(str) ? "" : "NOT ", str)
}</
{{out}}
Line 7,301 ⟶ 8,146:
=={{header|Simula}}==
<
INTEGER U;
U := ININT;
Line 7,346 ⟶ 8,191:
END;
END</
{{in}}
<pre>710</pre>
Line 7,396 ⟶ 8,241:
{{works with|PolyML}}
<
and checkBrackets 0 [] = true
| checkBrackets _ [] = false
Line 7,402 ⟶ 8,247:
| checkBrackets counter (#"["::rest) = checkBrackets (counter + 1) rest
| checkBrackets counter (#"]"::rest) = checkBrackets (counter - 1) rest
| checkBrackets counter (_::rest) = checkBrackets counter rest</
An example of usage
<
List.app print
(List.map
Line 7,416 ⟶ 8,261:
(* A set of strings to test *)
["", "[]", "[][]", "[[][]]", "][", "][][", "[]][[]"]
)</
Output:
Line 7,431 ⟶ 8,276:
=={{header|Stata}}==
<
function random_brackets(n) {
return(invtokens(("[","]")[runiformint(1,2*n,1,2)],""))
Line 7,442 ⟶ 8,287:
return(all(a:>=0) & a[n]==0)
}
end</
'''Test'''
Line 7,469 ⟶ 8,314:
Checks balance function:
<
func isBal(str: String) -> Bool {
Line 7,478 ⟶ 8,323:
}
</
isBal("[[[]]]") // true
isBal("[]][[]") // false
</
func randBrack(n: Int) -> String {
Line 7,499 ⟶ 8,344:
}
</
randBrack(2) // "]][["
</
func randIsBal(n: Int) {
Line 7,518 ⟶ 8,363:
randIsBal(4)
</
// ][ is unbalanced
Line 7,526 ⟶ 8,371:
// []][[] is unbalanced
//
// [][][[]] is balanced</
=={{header|Tcl}}==
<
if {!$n} return
set l [lrepeat $n "\[" "\]"]
Line 7,556 ⟶ 8,401:
set s [generate $i]
puts "\"$s\"\t-> [expr {[balanced $s] ? {OK} : {NOT OK}}]"
}</
Sample output:
<pre>
Line 7,577 ⟶ 8,422:
===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 <math>n</math> times, which might be done like this:
<
set s ""
for {set i 0} {$i < $n} {incr i} {
Line 7,584 ⟶ 8,429:
}
return $s
}</
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).
Line 7,591 ⟶ 8,436:
Generation program in Unix TMG:
<
loop: parse(render) [--n>0?]/done loop;
render: random(i, 15) [i = (i+1)*2] loop2 = { 1 * };
Line 7,609 ⟶ 8,454:
>>;
n: 0; i: 0; b: 0; seed: 0;</
Sample output:
Line 7,619 ⟶ 8,464:
Analysis can be done easily using grammar specification, rather than counting brackets:
<
corr: brkts * = { < OK: > 1 * };
brkts: brkt/null brkts = { 2 1 };
Line 7,629 ⟶ 8,474:
nonl: !<<
>>;</
Sample output:
Line 7,642 ⟶ 8,487:
=={{header|TUSCRIPT}}==
<
$$ MODE TUSCRIPT
Line 7,672 ⟶ 8,517:
PRINT b," ",status
ENDLOOP
</syntaxhighlight>
Output:
<pre>
Line 7,692 ⟶ 8,537:
=={{header|TXR}}==
<
@(do (defvar r (make-random-state nil))
Line 7,714 ⟶ 8,559:
@{parens 15} @{matched 15} @{mismatched 15}
@ (end)
@(end)</
The recursive pattern function <code>@(paren)</code> gives rise to a grammar which matches parentheses:
Line 7,751 ⟶ 8,596:
== {{header|TypeScript}} ==
{{trans|JavaScript}}
<
function isStringBalanced(str: string): bool {
Line 7,795 ⟶ 8,640:
console.log(`The string '${test}' is ${(isStringBalanced(test) ? "OK." : "not OK.")}`);
}
</syntaxhighlight>
{{out}}
<pre>
Line 7,822 ⟶ 8,667:
=={{header|UNIX Shell}}==
{{works with|bash}}
<
local b=()
local i j tmp
Line 7,859 ⟶ 8,704:
balanced "$test" && result=OK || result="NOT OK"
printf "%s\t%s\n" "$test" "$result"
done</
{{output}}
Line 7,876 ⟶ 8,721:
=={{header|Ursala}}==
<
#import nat
Line 7,883 ⟶ 8,728:
#cast %bm
main = ^(2-$'[]'*,balanced)* eql@ZFiFX*~ iota64</
output:
<pre><
Line 7,903 ⟶ 8,748:
=={{header|VBA}}==
<syntaxhighlight lang="vb">
Public Function checkBrackets(s As String) As Boolean
'function checks strings for balanced brackets
Line 7,970 ⟶ 8,815:
Next
End Sub
</syntaxhighlight>
sample output:
Line 7,987 ⟶ 8,832:
"]][][[[][]]][][[][][": Not OK
</pre>
=={{header|VBScript}}==
<
sequence = Generate_Sequence(n)
WScript.Echo sequence & " is " & Check_Balance(sequence) & "."
Line 8,025 ⟶ 8,869:
Check_Balance = "Balanced"
End If
End Function</
{{out}}
Line 8,042 ⟶ 8,886:
Antother version not using libraries. The generator works as intended (more difficult to do than the checking)
<syntaxhighlight lang="vb">
option explicit
Line 8,083 ⟶ 8,927:
& s & vbtab & " Checks as " & iif(bb,"","un")&"balanced"
next
</syntaxhighlight>
Sample run
<pre>
Line 8,099 ⟶ 8,943:
=={{header|Visual Basic .NET}}==
<
Private rand As New Random
Line 8,142 ⟶ 8,986:
Return numOpen = numClosed
End Function
End Module</
{{out}}
Line 8,158 ⟶ 9,002:
</pre>
=={{header|V (Vlang)}}==
<syntaxhighlight lang="v (vlang)">import datatypes as dt
fn is_valid(bracket string) bool {
Line 8,182 ⟶ 9,026:
println('$b ${is_valid(b)}')
}
}</
{{out}}
Line 8,198 ⟶ 9,042:
=={{header|Wren}}==
{{trans|Kotlin}}
<
var isBalanced = Fn.new { |s|
Line 8,227 ⟶ 9,071:
for (j in 1..8) s = s + ((rand.int(2) == 0) ? "[" : "]")
System.print("%(s) %(isBalanced.call(s) ? "OK" : "NOT OK")")
}</
{{out}}
Line 8,251 ⟶ 9,095:
=={{header|X86 Assembly}}==
<syntaxhighlight lang="x86assembly">
section .data
Line 8,318 ⟶ 9,162:
syscall
ret
</syntaxhighlight>
=={{header|XBasic}}==
{{trans|JavaScript}}
{{works with|Windows XBasic}}
<
PROGRAM "balancedbrackets"
VERSION "0.001"
Line 8,422 ⟶ 9,266:
END PROGRAM
</syntaxhighlight>
{{out}}
<pre>
Line 8,448 ⟶ 9,292:
=={{header|XBS}}==
<
func GenerateString(Amount:number=4):string{
set Result:string = "";
Line 8,464 ⟶ 9,308:
set s = GenerateString(math.random(2,4)*2);
log(`{s}: {IsBalanced(s)}`);
}</
{{out}}
<pre>
Line 8,480 ⟶ 9,324:
=={{header|XPL0}}==
<
int N, I, C, Nest;
Line 8,505 ⟶ 9,349:
Text(0,"OK
");
]</
Example output:
Line 8,517 ⟶ 9,361:
=={{header|Ya}}==
<
// all types are prefixed by `
Line 8,553 ⟶ 9,397:
//@Std/StdIO/ is used here to use Print function; else it maybe changed to Use @Std/StdIO at global level before this For loop
@Std/StdIO/Print(; "%s : %s\n" ;`Char[=] \brackets = MakeNew_[]s(10) /* all bracket strings are of length 10 */; AreBalanced(brackets) ? "Ok" : "bad")
// note that starting arg of Print is missed by using ';' - default arg value is allowed to use for any arg, even if next args are written</
=={{header|Yabasic}}==
<
local level, i
Line 8,573 ⟶ 9,417:
if not check_brackets(s$) print "not ";
print "ok"</
=={{header|zkl}}==
<
The span method finds the start and length of a balanced span. This algorithm assumes the string only contains brackets; a matched span is chopped off the front of the string and a new balanced span is searched for. Stops when the string is empty or unbalanced (span returns Void).
<pre>
Line 8,597 ⟶ 9,441:
=={{header|ZX Spectrum Basic}}==
{{trans|AWK}}
<
20 READ s$
25 PRINT "The sequence ";s$;" is ";
Line 8,614 ⟶ 9,458:
1100 RETURN
2000 DATA "[]","][","][][","[][]","[][][]","[]][[]","[[[[[]]]]][][][]][]["
</syntaxhighlight>
{{omit from|GUISS}}
|