Balanced brackets: Difference between revisions
m
syntax highlighting fixup automation
(→{{header|TypeScript}}: Added.) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
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 179:
=={{header|ABAP}}==
<
CLASS lcl_balanced_brackets DEFINITION.
PUBLIC SECTION.
Line 276:
cl_demo_output=>display( ).
</syntaxhighlight>
{{out}}
Line 303:
=={{header|Action!}}==
<
BYTE i,half
Line 374:
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:
Using #HASH-OFF
</pre>
<
FUNCTION bBRACKETS_MATCH(zStringWithBrackets: STRING): STRING
VAR sCount: SHORT
Line 415:
RETURN zOK
ENDFUNCTION
</syntaxhighlight>
{{out}}
<pre>
Line 426:
=={{header|Ada}}==
brackets.adb:
<
with Ada.Text_IO;
with Ada.Strings.Fixed;
Line 482:
end loop;
end loop;
end Brackets;</
Output:
Line 503:
=={{header|Aime}}==
<
{
integer b, i;
Line 537:
0;
}</
Sample output:
<pre> is balanced
Line 552:
=={{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:
test check brackets( get brackets( length ) )
OD
OD</
{{out}}
<pre>
Line 649:
<br clear=both>
==={{header|Java}}===
<syntaxhighlight lang=text>
grammar balancedBrackets ;
Line 669:
NEWLINE : '\r'? '\n'
;
</syntaxhighlight>
Produces:
<pre>
Line 694:
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:
[[][[]]][[[[]]]]: Good
[[[]][[[[][]][]]]]: Good
]][][][][[][][]][[[]: Bad</
=={{header|AppleScript}}==
Line 717:
(ES6 functionally composed version)
<
-- Zero-based index of the first problem (-1 if none found):
Line 899:
end script
end if
end mReturn</
'''Sample output:'''
<pre>'][' problem
Line 914:
=={{header|ARM Assembly}}==
<
.data
Line 974:
mov pc, lr
</syntaxhighlight>
=={{header|Arturo}}==
<
cnt: 0
Line 1,000:
if? isBalanced str -> print " OK"
else -> print " Not OK"
]</
{{out}}
Line 1,016:
=={{header|AutoHotkey}}==
<
Loop, 5
{
Line 1,047:
}
Return "OK"
}</
Output:
<pre>
Line 1,063:
A second example repeatedly replacing []:
<
{
B = %A_Index%
Line 1,085:
StringReplace, Str, Str,[],,All
Return Str ? "False" : "True"
}</
Sample output:
<pre>
Line 1,101:
=={{header|AutoIt}}==
<
#include <Array.au3>
Local $Array[1]
Line 1,130:
Return 1
EndFunc
</syntaxhighlight>
=={{header|AWK}}==
<
BEGIN {
print isbb("[]")
Line 1,155:
return (s==0)
}
</syntaxhighlight>
Output:
<pre>1
Line 1,165:
=={{header|BaCon}}==
<
str$ = ""
Line 1,187:
PRINT "BAD: ", str$
ENDIF
NEXT</
{{out}}
<pre>OK:
Line 1,203:
{{works with|QBasic}}
<
DECLARE FUNCTION generator$ (length AS INTEGER)
Line 1,259:
NEXT
generator$ = xx$
END FUNCTION</
Sample output:
Line 1,277:
==={{header|Commodore BASIC}}===
Based on ZX Spectrum BASIC implementation
<
20 FOR N=1 TO 7
30 READ S$
Line 1,297:
1090 PRINT "NOT OK"
1100 RETURN
2000 DATA , [], ][, [][], ][][, [[][]], []][[]</
=={{header|BASIC256}}==
{{trans|Yabasic}}
<
print s$; " = ";
Line 1,322:
next i
return level = 0
end function</
=={{header|Batch File}}==
Uses the rewrite rule <code>"[]" -> null</code> to check if brackets are balanced.
<
:: Batch File Implementation
Line 1,379:
set "old=%new%"
set "new=%old:[]=%"
goto check_loop</
{{out}}
<pre>[][][[[[]]][]]]][[][ is NOT Balanced.
Line 1,404:
=={{header|BBC BASIC}}==
<
test$=FNgenerate(RND(10))
PRINT "Bracket string ";test$;" is ";FNvalid(test$)
Line 1,432:
IF count%<0 THEN ="not OK."
NEXT x%
="OK."</
<pre>Bracket string [[[][]]] is OK.
Bracket string [[[]][[[][[][]]]]] is OK.
Line 1,447:
{{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:
> \ : 1991+*+- #v_v
\ $
^ < <$<</
=={{header|BQN}}==
Line 1,462:
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:
=={{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:
& !L+1:<11:?L
)
);</
Output:
<pre>:Balanced
Line 1,521:
=={{header|Brat}}==
<
brackets = []
balanced = true
Line 1,551:
{ p "#{test} is balanced" }
{ p "#{test} is not balanced" }
}</
Output:
Line 1,566:
=={{header|C}}==
<
#include<stdlib.h>
#include<string.h>
Line 1,608:
while(n<9) doSeq(n++);
return 0;
}</
'[]': True
']][[': False
Line 1,616:
']]]][[[]][[[': False
']]]]]][][[[[[[': False
'[][]][[][[[]]][]': False</
=={{header|C sharp|C#}}==
<
using System.Linq;
Line 1,660:
}
}
}</
Sample output:
<pre>"" is balanced.
Line 1,671:
"[]]][][]][[][[" is not balanced.
"[]]][]]][[][[][[" is not balanced.</pre>
<
// simple solution
string input = Console.ReadLine();
Line 1,696:
Console.WriteLine("Not Okay");
</syntaxhighlight>
=={{header|C++}}==
<
#include <iostream>
#include <string>
Line 1,731:
std::cout << (balanced(s) ? " ok: " : "bad: ") << s << "\n";
}
}</
Output:
<pre> ok:
Line 1,745:
=={{header|Ceylon}}==
<
platformRandom,
Random
Line 1,771:
ints.filter((i) => i != 0)
.scan(0)(plus<Integer>)
.every((i) => i >= 0);</
Output:
Line 1,788:
=={{header|Clojure}}==
<
(->> (concat (repeat n \[) (repeat n \]))
shuffle
Line 1,801:
(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:
(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:
=={{header|CLU}}==
<
% "misc.lib" that comes with PCLU.
Line 1,893:
end
end
end start_up</
{{out}}
<pre>"": balanced
Line 1,909:
=={{header|COBOL}}==
{{works with|OpenCOBOL}}
<
PROGRAM-ID. test-balanced-brackets.
Line 2,006:
.
END PROGRAM check-if-balanced.</
=={{header|CoffeeScript}}==
<
isBalanced = (brackets) ->
openCount = 0
Line 2,025:
for brackets in bracketsCombinations 4
console.log brackets, isBalanced brackets
</syntaxhighlight>
output
<syntaxhighlight lang=text>
> coffee balanced.coffee
[[[[ false
Line 2,045:
]]][ false
]]]] false
</syntaxhighlight>
=={{header|Common Lisp}}==
<
(defun string-of-brackets (n)
(let* ((len (* 2 n))
Line 2,076:
(let ((s (string-of-brackets i)))
(format t "~3A: ~A~%" (balancedp s) s))))
</syntaxhighlight>
Output:
Line 2,096:
=={{header|Component Pascal}}==
BlackBox Component Builder
<
MODULE Brackets;
IMPORT StdLog, Args, Stacks (* See Task Stacks *);
Line 2,157:
END Brackets.
</syntaxhighlight>
Execute: ^Q Brackets.Do [] [][] [[][]] ][ ][][ []][[]~<br/>
Output:
Line 2,170:
=={{header|Crystal}}==
<
(['[',']'] * n).shuffle.join # Implicit return
end
Line 2,195:
str = generate(i)
puts "#{str}: #{is_balanced(str)}"
end</
Output:
Line 2,213:
===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:
writeln(s.balancedParens('[', ']') ? " OK: " : "bad: ", s);
}
}</
{{out}}
<pre> OK: []
Line 2,233:
===Imperative Version===
{{trans|Raku}}
<
bool isBalanced(in string txt) pure nothrow {
Line 2,255:
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:
writeln(s.isBalanced ? " OK " : "Bad ", s);
}
}</
=={{header|Delphi}}==
<
var BracketsStr : string;
Line 2,312:
writeln(BracketsStr+': not OK');
end;
end;</
<pre>
Line 2,327:
=={{header|Déjà Vu}}==
<
swap 0
for c in chars:
Line 2,345:
!. matching? "]["
!. matching? "][]["
!. matching? "[]][[]"</
{{out}}
<pre>true
Line 2,356:
=={{header|EchoLisp}}==
<
(define (balance str)
(for/fold (closed 0) ((par str))
Line 2,385:
❌ "[[][]]]["
</syntaxhighlight>
=={{header|Elena}}==
ELENA 4.x :
<
import extensions;
import extensions'text;
Line 2,434:
console.readChar()
}</
{{out}}
<pre>
Line 2,452:
{{trans|Erlang}}
{{works with|Elixir|1.1}}
<
def task do
Enum.each(0..5, fn n ->
Line 2,478:
end
Balanced_brackets.task</
{{out}}
Line 2,491:
=={{header|Erlang}}==
<
-module( balanced_brackets ).
-export( [generate/1, is_balanced/1, task/0] ).
Line 2,521:
task_balanced( true ) -> "OK";
task_balanced( false ) -> "NOT OK".
</syntaxhighlight>
{{out}}
<pre>
Line 2,534:
=={{header|Euphoria}}==
<
integer level
level = 0
Line 2,578:
puts(1," NOT OK\n")
end if
end for</
Sample output:
Line 2,600:
{{Works with|Office 365 betas 2021}}
<
=LAMBDA(bracketPair,
LAMBDA(s,
Line 2,685:
)
)
)</
and also assuming the following generic bindings in the Name Manager for the WorkBook:
<
=LAMBDA(xs,
LAMBDA(ys,
Line 2,798:
)
)
)</
{{Out}}
Line 2,913:
=={{header|F_Sharp|F#}}==
<
let rec loop count = function
| ']'::_ when count = 0 -> false
Line 2,934:
for n in 1..10 do
let s = generate n
printfn "\"%s\" is balanced: %b" s (isBalanced s)</
Output:
Line 2,950:
=={{header|Factor}}==
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.
<
IN: balanced-brackets
Line 2,971:
readln
balanced</
Some more idiomatic solution might be as follows:
<
IN: balanced-brackets
Line 2,995:
-- Data stack:
t
</syntaxhighlight>
=={{header|Fantom}}==
<
class Main
{
Line 3,039:
}
}
</syntaxhighlight>
Output (for n=3):
Line 3,067:
=={{header|Forth}}==
{{works with|4tH|3.61.1}}
<
include lib/ctos.4th ( n -- a 1)
Line 3,089:
; \ evaluate string and print result
make[] eval[]</
'''Examples''':<pre>[][[]] OK
[[[[]][[ NOT OK
Line 3,105:
=={{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:
end subroutine generate
end program balanced_brackets
</syntaxhighlight>
=={{header|FreeBASIC}}==
<
Function isBalanced(s As String) As Boolean
Line 3,250:
Print
Print "Press any key to quit"
Sleep</
Sample output (last 7 lines random) :
{{out}}
Line 3,272:
=={{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:
Return sBrk 'Return the sBrk array
End</
Output:
<pre>
Line 3,366:
=={{header|GAP}}==
<
local c, r;
r := 0;
Line 3,401:
Balanced("[[[]][]]]");
# false</
=={{header|Go}}==
<
import (
Line 3,457:
}
testBalanced("()")
}</
Output:
<pre>
Line 3,475:
=={{header|Groovy}}==
Generate Arbitrary String of Bracket Pairs:
<
def factorial = { (it > 1) ? (2..it).inject(1) { i, j -> i*j } : 1 }
Line 3,495:
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:
return brackets.size() == 1 ? depth == 0 : balancedBrackets(brackets[1..-1], depth)
}
}</
Test:
<
(0..100).each {
(0..8).each { r ->
Line 3,523:
def bal = balancedBrackets(it) ? "balanced: " : "unbalanced: "
println "${bal} ${it}"
}</
Output:
Line 3,722:
=={{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:
-- 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:
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:
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:
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:
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,866:
bracket :: Int -> Char
bracket 0 = '['
bracket _ = ']'</
{{Out}}
<pre>]][]][: Unmatched
Line 3,891:
=={{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:
every !s := ?s # shuffle
return s
end</
Output:<pre>
Line 3,923:
=={{header|J}}==
'''Solution''': <
checkBalanced =: _1 -.@e. bracketDepth
genBracketPairs =: (?~@# { ])@#"0 1&'[]' NB. bracket pairs in arbitrary order</
'''Examples''':<
OK
][ bad
Line 3,936:
[[]][[][][]][] OK
]]]][[][][[[[]][ bad
[]]][][][[[[]][[]] bad</
'''Comments''': This task highlights the versatility and usefulness of J's scanning modifiers, <code>/</code> and <code>\</code>.
Line 3,943:
=={{header|Java}}==
{{works with|Java|1.5+}}
<
public static boolean hasBalancedBrackets(String str) {
Line 3,991:
}
}
}</
Sample output (generate uses random numbers, so it should not be the same every time):
<pre>: true
Line 4,011:
=== Extended ===
<
import java.util.Deque;
Line 4,074:
}
}
}</
{{out}}
<pre>With areSquareBracketsBalanced:
Line 4,101:
====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:
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:
==== Another solution ====
{{works with|Node.js}}
<
console.log("Supplied examples");
var tests = ["", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]"];
Line 4,201:
return generated;
}
</syntaxhighlight>
{{out}}
<pre>
Line 4,229:
====Functional====
With visual indication of where the balance fails:
<
'use strict';
Line 4,333:
// ---
return main();
})();</
{{Out}}
<pre>'' OK
Line 4,348:
=={{header|Julia}}==
<
function balancedbrackets(str::AbstractString)
Line 4,363:
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:
'''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:
("][[][[]]][[]]]][][";0)
("]][[[[]]]][][][[]]]]";0))
</syntaxhighlight>
=={{header|Klingphix}}==
<syntaxhighlight lang=text>"[[]][]]"
%acc 0 !acc
Line 4,415:
print
" " input</
=={{header|Kotlin}}==
{{trans|FreeBASIC}}
<
fun isBalanced(s: String): Boolean {
Line 4,450:
println("$s " + if (isBalanced(s)) "OK" else "NOT OK")
}
}</
Sample output (last 7 lines random) :
{{out}}
Line 4,474:
=={{header|L++}}==
<
(defn bool balanced (std::string s)
Line 4,488:
(pr std::boolalpha)
(foreach x tests
(prn x "\t" (balanced x))))</
=={{header|Lasso}}==
<
local(out) = array
Line 4,512:
with i in 1 to 10
let input = randomparens(#i)
select #input + ' = ' + validateparens(#input)</
{{out}}
Line 4,526:
=={{header|Liberty BASIC}}==
<syntaxhighlight lang=lb>
print "Supplied examples"
for i =1 to 7
Line 4,589:
end
</syntaxhighlight>
Supplied examples
The string '' is OK.
Line 4,612:
=={{header|Lua}}==
<
function isBalanced(s)
--Lua pattern matching has a 'balanced' pattern that matches sets of balanced characters.
Line 4,633:
print(RS)
print(isBalanced(RS))
</syntaxhighlight>
=={{header|Maple}}==
This functionality is provided by Maple.
<
> use StringTools in
> IsBalanced( "", "[", "]" );
Line 4,669:
false
</syntaxhighlight>
Furthermore, Maple can check whether multiple fences are balanced in the same string.
<
> StringTools:-IsBalanced( "[()()]", "[(", "])" );
true
</syntaxhighlight>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
gen[n_] := RandomSample[Table[{1, -1}, {n}] // Flatten]
Line 4,689:
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:
=={{header|Maxima}}==
<
[n: slength(s), r: 0, c],
catch(
Line 4,745:
brack("[[[]][]]]");
false</
=={{header|Mercury}}==
<
:- module balancedbrackets.
:- interface.
Line 4,789:
; print(" is unbalanced\n", !IO)
).
</syntaxhighlight>
=={{header|MiniScript}}==
Line 4,795:
We start by defining a function:
<
level = 0
for c in str
Line 4,803:
end for
return level == 0
end function</
We can evaluate the example strings with this code:
<
"",
"[]",
Line 4,821:
if balanced then outcome = "is OK" else outcome = "NOT OK"
print """" + str + """ " + outcome
end for</
{{out}}
Line 4,836:
{{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:
END;
END Brackets.
</syntaxhighlight>
{{out}}
<pre>
Line 4,901:
=={{header|Nanoquery}}==
{{trans|Python}}
<
def gen(N)
Line 4,933:
println format("%-22s is not balanced", txt)
end
end</
{{out}}
<pre> is balanced
Line 4,948:
=={{header|Nim}}==
<
from random import random, randomize, shuffle
from strutils import repeat
Line 4,972:
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,987:
=={{header|Oberon-2}}==
{{works with|oo2c version 2}}
<
MODULE BalancedBrackets;
IMPORT
Line 5,090:
Do
END BalancedBrackets.
</syntaxhighlight>
{{out}}
<pre>
Line 5,102:
=={{header|Objeck}}==
<
bundle Default {
class Balanced {
Line 5,135:
}
}
</syntaxhighlight>
<pre>
: true
Line 5,148:
=={{header|OCaml}}==
<
let rec aux i acc =
if i <= 0 then acc else
Line 5,172:
List.iter print_char brk;
Printf.printf " %B\n" (is_balanced brk);
;;</
<pre>
Line 5,183:
=={{header|Oforth}}==
<
| c |
0 self forEach: c [
Line 5,193:
: genBrackets(n)
"" #[ "[" "]" 2 rand 2 == ifTrue: [ swap ] rot + swap + ] times(n) ;</
{{out}}
Line 5,211:
=={{header|ooRexx}}==
<
tests = .array~of("", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]")
Line 5,259:
end
return answer~string
</syntaxhighlight>
Sample output (uses randomly generated groupings, so it should be different on each run):
<pre>
Line 5,280:
=={{header|OxygenBasic}}==
<
'=======================================
sys co, le=len s
Line 5,307:
print CheckBrackets "[][]"'1
print CheckBrackets "][" '0
</syntaxhighlight>
=={{header|PARI/GP}}==
<
my(n=0,v=Vecsmall(s));
for(i=1,#v,
Line 5,322:
};
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:
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:
my $input = generate($_);
print balanced($input) ? " ok:" : "bad:", " '$input'\n";
}</
{{out}}
Line 5,362:
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 (non-bracket chars allowed). Its recent versions use the subpattern recursion and are hence also only for Perl 5.10 and up.
<
my $re = qr/^$RE{balanced}{-parens=>'[]'}$/;
sub balanced {
return shift =~ $re;
}</
Alternative implementation, using straightforward depth counting:
<
my $depth = 0;
for (split //, shift) {
Line 5,383:
}
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:
<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:
=={{header|Phixmonti}}==
<
0 var acc
Line 5,451:
" 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:
printf("%s\t%s%s", $s, printbool(isbalanced($s)), PHP_EOL);
}
</syntaxhighlight>
Sample run:
<pre>
Line 5,507:
=={{header|Picat}}==
===Foreach loop===
<
tests(Tests),
member(Test,Tests),
Line 5,531:
"][][", "[]][[]", "[][][][][][][][][][]",
"[[[[[[[]]]]]]]", "[[[[[[[]]]]]]",
"[][[]][]","[[][]][]", "[][][[]][]"]).</
{{out}}
Line 5,550:
===DCG===
Here is an implementation using DCG (Definite Clause Grammars).
<
tests(Tests),
foreach(Test in Tests)
Line 5,564:
balanced --> "".
balanced --> "[", balanced, "]", balanced.</
=={{header|PicoLisp}}==
<
(de generateBrackets (N)
Line 5,583:
(for N 10
(prinl (if (checkBrackets (prin (generateBrackets N))) " OK" "not OK")) )</
Output:
<pre>[] OK
Line 5,597:
=={{header|PL/I}}==
<
cb: Proc Options(main);
/* PL/I program to check for balanced brackets [] ********************
Line 5,658:
End;
End;</
Output:
<pre> balanced ''
Line 5,689:
=={{header|PowerShell}}==
{{works with|PowerShell|2}}
<
function Get-BalanceStatus ( $String )
{
Line 5,708:
return $Status
}
</syntaxhighlight>
<
# Test
$Strings = @( "" )
Line 5,718:
$String.PadRight( 12, " " ) + (Get-BalanceStatus $String)
}
</syntaxhighlight>
{{out}}
<pre>
Line 5,731:
===PowerShell (Regex Version)===
<
function Test-BalancedBracket
{
Line 5,789:
"{0}: {1}" -f $s.PadRight(8), "$(if (Test-BalancedBracket Brace $s) {'Is balanced.'} else {'Is not balanced.'})"
}
</syntaxhighlight>
{{Out}}
<pre>
Line 5,803:
=={{header|Prolog}}==
DCG are very usefull for this kind of exercice !
<
test_brackets([]),
test_brackets(['[',']']),
Line 5,855:
bracket(0) --> ['['].
bracket(1) --> [']'].
</syntaxhighlight>
Sample output :
<pre> ?- balanced_brackets.
Line 5,882:
=={{header|PureBasic}}==
<
For i=1 To N
sample$+"[]"
Line 5,925:
PrintN(" is not balanced")
EndIf
Next</
Output sample
<pre>
Line 5,937:
=={{header|Python}}==
===Procedural===
<
... txt = ['[', ']'] * N
... random.shuffle( txt )
Line 5,963:
'[[]]]]][]][[[[' is not balanced
'[[[[]][]]][[][]]' is balanced
'][[][[]]][]]][[[[]' is not balanced</
=== Functional ===
Line 5,969:
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:
'][]][][[]][[][' is not balanced
'][[]]][][[]][[[]' is not balanced
'][[][[]]]][[[]][][' is not balanced</
=== Array Programming ===
Line 5,998:
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:
'[][[[]][[]]][]' is balanced
'[[][][[]]][[[]]]' is balanced
'][]][][[]][]][][[[' is not balanced</
=={{header|Qi}}==
<
[] 0 -> true
[] _ -> false
Line 6,048:
(balanced-brackets "[]][[]")
</syntaxhighlight>
=={{header|Quackery}}==
<
swap
char ] swap of
Line 6,072:
[ say "un" ]
say "balanced."
cr ]</
{{out}}
Line 6,091:
=={{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:
8 FALSE []]]][[[]][[[]
9 TRUE [[[[][[][]]]]]
10 TRUE []</
=={{header|Racket}}==
<
#lang racket
Line 6,145:
(for ([n 10]) (try n))
</syntaxhighlight>
=={{header|Raku}}==
Line 6,154:
{{works with|Rakudo|2015.12}}
<syntaxhighlight lang=raku
my $l = 0;
for $s.comb {
Line 6,170:
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:
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:
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:
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:
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:
===with examples + 30 permutations===
<
/*REXX program to check for balanced brackets [] **********************
* test strings and random string generation copied from Version 1
Line 6,381:
end
return nest=0 /* nest=0 -> balanced */
</syntaxhighlight>
{{out}}
<pre>
Line 6,430:
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:
/*──────────────────────────────────────────────────────────────────────────────────────*/
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:
=={{header|Ring}}==
<
nr = 0
while nr < 10
Line 6,484:
next
return "ok."
</syntaxhighlight>
Output:
<pre>
Line 6,502:
{{trans|D}}
{{works with|Ruby|1.9}}
<
(?<bb> # begin capture group <bb>
\[ # literal [
Line 6,518:
t = s.gsub(/[^\[\]]/, "")
puts (t =~ re ? " OK: " : "bad: ") + s
end</
One output: <pre>
Line 6,537:
=={{header|Run BASIC}}==
<
brk$(1) = "[[[][]]]"
brk$(2) = "[[[]][[[][[][]]]]]"
Line 6,557:
if trim$(b$) = "" then print " OK "; else print "Not OK ";
print brk$(i)
next i</
One output: <pre> OK
Line 6,575:
{{libheader|rand}}
<
trait Balanced {
Line 6,614:
println!("{} {}", brackets, brackets.is_balanced())
}
}</
Output: <pre>
true
Line 6,634:
=== Scala Version 1 ===
{{works with|Scala|2.9.1}}
<
import scala.util.Random
Line 6,669:
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:
=== Scala Version 2 ===
{{works with|Scala|2.10.1}}
<
object BalancedBracketsApp extends App {
Line 7,072:
}
}</
Alternate implementation of "isBalanced" using tail-recursion instead of var and return:
<
import scala.annotation.tailrec
Line 7,095:
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:
}
}
</syntaxhighlight>
Sample output:
Line 7,135:
=={{header|Scheme}}==
<
(define (b chars sum)
(cond ((< sum 0)
Line 7,160:
(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:
x=isbb(s);
disp(x);
end</
Console output:
<pre> ][]][
Line 7,200:
=={{header|Seed7}}==
<
const func string: generateBrackets (in integer: count) is func
Line 7,252:
end for;
end for;
end func;</
Output:
Line 7,274:
=={{header|Sidef}}==
<
var depth = 0
Line 7,287:
for str [']','[','[[]','][]','[[]]','[[]]]][][]]','x[ y [ [] z ]][ 1 ][]abcd'] {
printf("%sbalanced\t: %s\n", balanced(str) ? "" : "NOT ", str)
}</
{{out}}
Line 7,301:
=={{header|Simula}}==
<
INTEGER U;
U := ININT;
Line 7,346:
END;
END</
{{in}}
<pre>710</pre>
Line 7,396:
{{works with|PolyML}}
<
and checkBrackets 0 [] = true
| checkBrackets _ [] = false
Line 7,402:
| 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:
(* A set of strings to test *)
["", "[]", "[][]", "[[][]]", "][", "][][", "[]][[]"]
)</
Output:
Line 7,431:
=={{header|Stata}}==
<
function random_brackets(n) {
return(invtokens(("[","]")[runiformint(1,2*n,1,2)],""))
Line 7,442:
return(all(a:>=0) & a[n]==0)
}
end</
'''Test'''
Line 7,469:
Checks balance function:
<
func isBal(str: String) -> Bool {
Line 7,478:
}
</
isBal("[[[]]]") // true
isBal("[]][[]") // false
</
func randBrack(n: Int) -> String {
Line 7,499:
}
</
randBrack(2) // "]][["
</
func randIsBal(n: Int) {
Line 7,518:
randIsBal(4)
</
// ][ is unbalanced
Line 7,526:
// []][[] is unbalanced
//
// [][][[]] is balanced</
=={{header|Tcl}}==
<
if {!$n} return
set l [lrepeat $n "\[" "\]"]
Line 7,556:
set s [generate $i]
puts "\"$s\"\t-> [expr {[balanced $s] ? {OK} : {NOT OK}}]"
}</
Sample output:
<pre>
Line 7,577:
===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:
}
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:
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:
>>;
n: 0; i: 0; b: 0; seed: 0;</
Sample output:
Line 7,619:
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:
nonl: !<<
>>;</
Sample output:
Line 7,642:
=={{header|TUSCRIPT}}==
<
$$ MODE TUSCRIPT
Line 7,672:
PRINT b," ",status
ENDLOOP
</syntaxhighlight>
Output:
<pre>
Line 7,692:
=={{header|TXR}}==
<
@(do (defvar r (make-random-state nil))
Line 7,714:
@{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:
== {{header|TypeScript}} ==
{{trans|JavaScript}}
<
function isStringBalanced(str: string): bool {
Line 7,795:
console.log(`The string '${test}' is ${(isStringBalanced(test) ? "OK." : "not OK.")}`);
}
</syntaxhighlight>
{{out}}
<pre>
Line 7,822:
=={{header|UNIX Shell}}==
{{works with|bash}}
<
local b=()
local i j tmp
Line 7,859:
balanced "$test" && result=OK || result="NOT OK"
printf "%s\t%s\n" "$test" "$result"
done</
{{output}}
Line 7,876:
=={{header|Ursala}}==
<
#import nat
Line 7,883:
#cast %bm
main = ^(2-$'[]'*,balanced)* eql@ZFiFX*~ iota64</
output:
<pre><
Line 7,903:
=={{header|VBA}}==
<syntaxhighlight lang=vb>
Public Function checkBrackets(s As String) As Boolean
'function checks strings for balanced brackets
Line 7,970:
Next
End Sub
</syntaxhighlight>
sample output:
Line 7,990:
=={{header|VBScript}}==
<
sequence = Generate_Sequence(n)
WScript.Echo sequence & " is " & Check_Balance(sequence) & "."
Line 8,025:
Check_Balance = "Balanced"
End If
End Function</
{{out}}
Line 8,042:
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:
& s & vbtab & " Checks as " & iif(bb,"","un")&"balanced"
next
</syntaxhighlight>
Sample run
<pre>
Line 8,099:
=={{header|Visual Basic .NET}}==
<
Private rand As New Random
Line 8,142:
Return numOpen = numClosed
End Function
End Module</
{{out}}
Line 8,159:
=={{header|Vlang}}==
<
fn is_valid(bracket string) bool {
Line 8,182:
println('$b ${is_valid(b)}')
}
}</
{{out}}
Line 8,198:
=={{header|Wren}}==
{{trans|Kotlin}}
<
var isBalanced = Fn.new { |s|
Line 8,227:
for (j in 1..8) s = s + ((rand.int(2) == 0) ? "[" : "]")
System.print("%(s) %(isBalanced.call(s) ? "OK" : "NOT OK")")
}</
{{out}}
Line 8,251:
=={{header|X86 Assembly}}==
<
section .data
Line 8,318:
syscall
ret
</syntaxhighlight>
=={{header|XBasic}}==
{{trans|JavaScript}}
{{works with|Windows XBasic}}
<
PROGRAM "balancedbrackets"
VERSION "0.001"
Line 8,422:
END PROGRAM
</syntaxhighlight>
{{out}}
<pre>
Line 8,448:
=={{header|XBS}}==
<
func GenerateString(Amount:number=4):string{
set Result:string = "";
Line 8,464:
set s = GenerateString(math.random(2,4)*2);
log(`{s}: {IsBalanced(s)}`);
}</
{{out}}
<pre>
Line 8,480:
=={{header|XPL0}}==
<
int N, I, C, Nest;
Line 8,505:
Text(0,"OK
");
]</
Example output:
Line 8,517:
=={{header|Ya}}==
<
// all types are prefixed by `
Line 8,553:
//@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:
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:
=={{header|ZX Spectrum Basic}}==
{{trans|AWK}}
<
20 READ s$
25 PRINT "The sequence ";s$;" is ";
Line 8,614:
1100 RETURN
2000 DATA "[]","][","][][","[][]","[][][]","[]][[]","[[[[[]]]]][][][]][]["
</syntaxhighlight>
|