Balanced brackets: Difference between revisions

=={{header|11l}}==

{{trans|Python}}

V txt = [‘[’, ‘]’] * n

random:shuffle(&txt)

 

=={{header|360 Assembly}}==

BALANCE CSECT

USING BALANCE,R13 base register and savearea pointer

 

=={{header|ABAP}}==

CLASS lcl_balanced_brackets DEFINITION.

PUBLIC SECTION.

 

=={{header|Action!}}==

BYTE i,half

 

Using #HASH-OFF

</pre>

FUNCTION bBRACKETS_MATCH(zStringWithBrackets: STRING): STRING

VAR sCount: SHORT

=={{header|Ada}}==

brackets.adb:

with Ada.Text_IO;

with Ada.Strings.Fixed;

 

=={{header|Aime}}==

{

integer b, i;

=={{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:

<br clear=both>

==={{header|Java}}===

grammar balancedBrackets ;

 

and a function to check whether a given string of brackets is balanced.

 

bal ← (((|≡⊢)+\) ∧ 0=+/)(+⌿1 ¯1×[1]'[]'∘.=⊢)</syntaxhighlight>

 

Sample run for 0..N..10:

 

: Good

[]: Good

(ES6 functionally composed version)

 

 

-- Zero-based index of the first problem (-1 if none found):

 

=={{header|ARM Assembly}}==

.data

 

 

=={{header|Arturo}}==

cnt: 0

 

=={{header|AutoHotkey}}==

Loop, 5

{

 

A second example repeatedly replacing []:

{

B = %A_Index%

 

=={{header|AutoIt}}==

#include <Array.au3>

Local $Array[1]

=={{header|AWK}}==

BEGIN {

print isbb("[]")

 

=={{header|BaCon}}==

 

str$ = ""

{{works with|QBasic}}

 

DECLARE FUNCTION generator$ (length AS INTEGER)

 

==={{header|Commodore BASIC}}===

Based on ZX Spectrum BASIC implementation

20 FOR N=1 TO 7

30 READ S$

=={{header|BASIC256}}==

{{trans|Yabasic}}

print s$; " = ";

 

=={{header|Batch File}}==

Uses the rewrite rule <code>"[]" -> null</code> to check if brackets are balanced.

:: Batch File Implementation

 

=={{header|BBC BASIC}}==

test$=FNgenerate(RND(10))

PRINT "Bracket string ";test$;" is ";FNvalid(test$)

{{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" ,, ^

This allows for a particular simple implementation:

 

Bal ← {

Mul ← {a‿b𝕊x‿y: ⟨a+0⌈x-b, y+0⌈b-x⟩}

=={{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

 

=={{header|Brat}}==

brackets = []

balanced = true

 

=={{header|C}}==

#include<stdlib.h>

#include<string.h>

while(n<9) doSeq(n++);

return 0;

'[]': True

']][[': False

 

=={{header|C sharp|C#}}==

using System.Linq;

 

"[]]][][]][[][[" is not balanced.

"[]]][]]][[][[][[" is not balanced.</pre>

// simple solution

string input = Console.ReadLine();

 

=={{header|C++}}==

#include <iostream>

#include <string>

 

=={{header|Ceylon}}==

platformRandom,

Random

 

=={{header|Clojure}}==

(->> (concat (repeat n \[) (repeat n \]))

shuffle

 

* We can use <code>reduce</code> to consume the sequence:

(empty?

(reduce

 

* Only <code>[</code>s are put on the stack. We can just count the unmatched ones.

(let [opens-closes (->> s

(map {\[ 1, \] -1})

 

=={{header|CLU}}==

% "misc.lib" that comes with PCLU.

 

=={{header|COBOL}}==

{{works with|OpenCOBOL}}

PROGRAM-ID. test-balanced-brackets.

 

 

=={{header|CoffeeScript}}==

isBalanced = (brackets) ->

openCount = 0

</syntaxhighlight>

output

> coffee balanced.coffee

[[[[ false

 

=={{header|Common Lisp}}==

(defun string-of-brackets (n)

(let* ((len (* 2 n))

=={{header|Component Pascal}}==

BlackBox Component Builder

MODULE Brackets;

IMPORT StdLog, Args, Stacks (* See Task Stacks *);

 

=={{header|Crystal}}==

(['[',']'] * n).shuffle.join # Implicit return

end

===Standard Version===

D standard library has a [http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html#balancedParens function] for this.

 

void main() {

===Imperative Version===

{{trans|Raku}}

 

bool isBalanced(in string txt) pure nothrow {

===Functional Style===

{{trans|Haskell}}

 

bool isBalanced(in string s, in char[2] pars="[]") pure nothrow @safe @nogc {

=={{header|Delphi}}==

 

 

var BracketsStr : string;

 

=={{header|Déjà Vu}}==

swap 0

for c in chars:

 

=={{header|EchoLisp}}==

(define (balance str)

(for/fold (closed 0) ((par str))

=={{header|Elena}}==

ELENA 4.x :

import extensions;

import extensions'text;

{{trans|Erlang}}

{{works with|Elixir|1.1}}

def task do

Enum.each(0..5, fn n ->

 

=={{header|Erlang}}==

-module( balanced_brackets ).

-export( [generate/1, is_balanced/1, task/0] ).

 

=={{header|Euphoria}}==

integer level

level = 0

 

{{Works with|Office 365 betas 2021}}

=LAMBDA(bracketPair,

LAMBDA(s,

and also assuming the following generic bindings in the Name Manager for the WorkBook:

 

=LAMBDA(xs,

LAMBDA(ys,

 

=={{header|F_Sharp|F#}}==

let rec loop count = function

| ']'::_ when count = 0 -> false

=={{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

 

Some more idiomatic solution might be as follows:

 

IN: balanced-brackets

 

=={{header|Fantom}}==

 

class Main

{

=={{header|Forth}}==

{{works with|4tH|3.61.1}}

include lib/ctos.4th ( n -- a 1)

 

=={{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

 

=={{header|FreeBASIC}}==

 

Function isBalanced(s As String) As Boolean

=={{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

 

=={{header|GAP}}==

local c, r;

r := 0;

 

=={{header|Go}}==

 

import (

=={{header|Groovy}}==

Generate Arbitrary String of Bracket Pairs:

 

def factorial = { (it > 1) ? (2..it).inject(1) { i, j -> i*j } : 1 }

 

Check Balance of Bracket String:

if (brackets == null || brackets.empty) return depth == 0

switch (brackets[0]) {

 

Test:

(0..100).each {

(0..8).each { r ->

=={{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 []

This generates an infinite stream of correct balanced brackets expressions:

 

$ [1.. ] >>= (`replicateM` "[]{}") </syntaxhighlight>

<pre>λ> take 10 brackets

In case the index of unmatched opening bracket is need to be found, following solution is suitable.

 

import Control.Monad

import System.Random

zipWithM_ (\n r -> check $ shuffle (take n bs) r) [0,2 ..] rs</syntaxhighlight>

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

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)

 

=={{header|Icon}} and {{header|Unicon}}==

every s := genbs(!arglist) do

write(image(s), if isbalanced(s) then " is balanced." else " is unbalanced")

 

=={{header|J}}==

checkBalanced =: _1 -.@e. bracketDepth

genBracketPairs =: (?~@# { ])@#"0 1&'[]' NB. bracket pairs in arbitrary order</syntaxhighlight>

OK

][ bad

=={{header|Java}}==

{{works with|Java|1.5+}}

 

public static boolean hasBalancedBrackets(String str) {

 

=== Extended ===

import java.util.Deque;

 

====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

==== Another solution ====

{{works with|Node.js}}

console.log("Supplied examples");

var tests = ["", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]"];

====Functional====

With visual indication of where the balance fails:

'use strict';

 

 

=={{header|Julia}}==

 

function balancedbrackets(str::AbstractString)

 

'''One-line version''':

 

=={{header|K}}==

gen_brackets:{"[]"@x _draw 2}

check:{r:(-1;1)@"["=x; *(0=+/cs<'0)&(0=-1#cs:+\r)}

 

=={{header|Klingphix}}==

 

%acc 0 !acc

=={{header|Kotlin}}==

{{trans|FreeBASIC}}

 

fun isBalanced(s: String): Boolean {

 

=={{header|L++}}==

(defn bool balanced (std::string s)

 

=={{header|Lasso}}==

local(out) = array

 

 

=={{header|Liberty BASIC}}==

print "Supplied examples"

for i =1 to 7

 

=={{header|Lua}}==

function isBalanced(s)

--Lua pattern matching has a 'balanced' pattern that matches sets of balanced characters.

=={{header|Maple}}==

This functionality is provided by Maple.

> use StringTools in

> IsBalanced( "", "[", "]" );

</syntaxhighlight>

Furthermore, Maple can check whether multiple fences are balanced in the same string.

> StringTools:-IsBalanced( "[()()]", "[(", "])" );

true

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

gen[n_] := RandomSample[Table[{1, -1}, {n}] // Flatten]

 

=={{header|MATLAB}} / {{header|Octave}}==

t = cumsum((s=='[') - (s==']'));

x = all(t>=0) && (t(end)==0);

 

=={{header|Maxima}}==

[n: slength(s), r: 0, c],

catch(

 

=={{header|Mercury}}==

:- module balancedbrackets.

:- interface.

We start by defining a function:

 

level = 0

for c in str

We can evaluate the example strings with this code:

 

"",

"[]",

{{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;

=={{header|Nanoquery}}==

{{trans|Python}}

 

def gen(N)

 

=={{header|Nim}}==

from random import random, randomize, shuffle

from strutils import repeat

=={{header|Oberon-2}}==

{{works with|oo2c version 2}}

MODULE BalancedBrackets;

IMPORT

 

=={{header|Objeck}}==

bundle Default {

class Balanced {

=={{header|OCaml}}==

 

let rec aux i acc =

if i <= 0 then acc else

=={{header|Oforth}}==

 

| c |

0 self forEach: c [

 

=={{header|ooRexx}}==

tests = .array~of("", "[]", "][", "[][]", "][][", "[[][]]", "[]][[]")

 

 

=={{header|OxygenBasic}}==

'=======================================

sys co, le=len s

 

=={{header|PARI/GP}}==

my(n=0,v=Vecsmall(s));

for(i=1,#v,

Idiomatic solution, using a regex that performs subpattern recursion ''(works with Perl 5.10 and newer)'':

 

my $n = shift;

my $str = '[' x $n;

If input strings are allowed to contain unrelated characters, this can be extended to:

 

shift =~ /^ ( [^\[\]]++ | \[ (?1)* \] )* $/x;

}</syntaxhighlight>

<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 {

Alternative implementation, using straightforward depth counting:

 

my $depth = 0;

for (split //, shift) {

 

=={{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>

 

=={{header|Phixmonti}}==

0 var acc

 

The sample is given as unix shell script, you need to have ''php-cli'' (or what your package manager calls it) installed.

 

<?php

 

=={{header|Picat}}==

===Foreach loop===

tests(Tests),

member(Test,Tests),

===DCG===

Here is an implementation using DCG (Definite Clause Grammars).

tests(Tests),

foreach(Test in Tests)

 

=={{header|PicoLisp}}==

 

(de generateBrackets (N)

 

=={{header|PL/I}}==

cb: Proc Options(main);

/* PL/I program to check for balanced brackets [] ********************

=={{header|PowerShell}}==

{{works with|PowerShell|2}}

function Get-BalanceStatus ( $String )

{

}

</syntaxhighlight>

# Test

$Strings = @( "" )

 

===PowerShell (Regex Version)===

function Test-BalancedBracket

{

=={{header|Prolog}}==

DCG are very usefull for this kind of exercice !

test_brackets([]),

test_brackets(['[',']']),

 

=={{header|PureBasic}}==

For i=1 To N

sample$+"[]"

=={{header|Python}}==

===Procedural===

... txt = ['[', ']'] * N

... random.shuffle( txt )

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):

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):

=={{header|Qi}}==

 

[] 0 -> true

[] _ -> false

=={{header|Quackery}}==

 

swap

char ] swap of

=={{header|R}}==

 

str <- strsplit(str, "")[[1]]

str <- ifelse(str=='[', 1, -1)

Alternately, using perl 5.10-compatible regexps,

 

regexpr('^(\\[(?1)*\\])*$', str, perl=TRUE) > -1

}</syntaxhighlight>

To generate some some examples:

 

 

as.data.frame(within(list(), {

 

Output:

1 FALSE ][][

2 FALSE [][[]]][[]][]]][[[

=={{header|Racket}}==

 

#lang racket

 

{{works with|Rakudo|2015.12}}

 

my $l = 0;

for $s.comb {

===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.

.none < 0 and .[*-1] == 0

given ([\+] '\\' «leg« $s.comb).cache;

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}}

Nil while s:g/'[]'//;

$_ eq '';

===Parsing with a grammar===

{{works with|Rakudo|2015.12}}

 

my $n = prompt "Number of bracket pairs: ";

 

=={{header|Red}}==

balanced-brackets: [#"[" any balanced-brackets #"]"]

rule: [any balanced-brackets end]

=={{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*/

 

===with examples + 30 permutations===

/*REXX program to check for balanced brackets [] **********************

* test strings and random string generation copied from Version 1

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*/

 

=={{header|Ring}}==

nr = 0

while nr < 10

{{trans|D}}

{{works with|Ruby|1.9}}

(?<bb> # begin capture group <bb>

\[ # literal [

 

=={{header|Run BASIC}}==

brk$(1) = "[[[][]]]"

brk$(2) = "[[[]][[[][[][]]]]]"

 

{{libheader|rand}}

 

trait Balanced {

=== Scala Version 1 ===

{{works with|Scala|2.9.1}}

import scala.util.Random

 

=== Scala Version 2 ===

{{works with|Scala|2.10.1}}

 

object BalancedBracketsApp extends App {

Alternate implementation of "isBalanced" using tail-recursion instead of var and return:

 

import scala.annotation.tailrec

 

Slightly modified implementation of "isBalanced" using tail-recursion

{{works with|Scala|2.11.7}}

@scala.annotation.tailrec

final def isBalanced(

 

=={{header|Scheme}}==

(define (b chars sum)

(cond ((< sum 0)

=={{header|Scilab}}==

{{trans|MATLAB}}

st=strsplit(s);

t=cumsum((st=='[')-(st==']'));

{{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>.

s=[];

for i=1:j

 

=={{header|Seed7}}==

 

const func string: generateBrackets (in integer: count) is func

 

=={{header|Sidef}}==

 

var depth = 0

 

=={{header|Simula}}==

INTEGER U;

U := ININT;

{{works with|PolyML}}

 

and checkBrackets 0 [] = true

| checkBrackets _ [] = false

An example of usage

 

List.app print

(List.map

=={{header|Stata}}==

 

function random_brackets(n) {

return(invtokens(("[","]")[runiformint(1,2*n,1,2)],""))

Checks balance function:

 

 

func isBal(str: String) -> Bool {

}

isBal("[[[]]]") // true

 

isBal("[]][[]") // false

 

 

func randBrack(n: Int) -> String {

}

 

 

randBrack(2) // "]][["

 

 

func randIsBal(n: Int) {

randIsBal(4)

 

 

// ][ is unbalanced

 

=={{header|Tcl}}==

if {!$n} return

set l [lrepeat $n "\[" "\]"]

===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} {

 

Generation program in Unix TMG:

loop: parse(render) [--n>0?]/done loop;

render: random(i, 15) [i = (i+1)*2] loop2 = { 1 * };

 

Analysis can be done easily using grammar specification, rather than counting brackets:

corr: brkts * = { < OK: > 1 * };

brkts: brkt/null brkts = { 2 1 };

 

=={{header|TUSCRIPT}}==

$$ MODE TUSCRIPT

 

=={{header|TXR}}==

 

@(do (defvar r (make-random-state nil))

 

== {{header|TypeScript}} ==

{{trans|JavaScript}}

 

function isStringBalanced(str: string): bool {

=={{header|UNIX Shell}}==

{{works with|bash}}

local b=()

local i j tmp

=={{header|Ursala}}==

 

#import nat

 

 

=={{header|VBA}}==

Public Function checkBrackets(s As String) As Boolean

'function checks strings for balanced brackets

"]][][[[][]]][][[][][": Not OK

</pre>

 

=={{header|VBScript}}==

sequence = Generate_Sequence(n)

WScript.Echo sequence & " is " & Check_Balance(sequence) & "."

 

Antother version not using libraries. The generator works as intended (more difficult to do than the checking)

option explicit

 

 

=={{header|Visual Basic .NET}}==

 

Private rand As New Random

 

=={{header|Vlang}}==

 

fn is_valid(bracket string) bool {

=={{header|Wren}}==

{{trans|Kotlin}}

 

var isBalanced = Fn.new { |s|

 

=={{header|X86 Assembly}}==

section .data

 

{{trans|JavaScript}}

{{works with|Windows XBasic}}

PROGRAM "balancedbrackets"

VERSION "0.001"

 

=={{header|XBS}}==

func GenerateString(Amount:number=4):string{

set Result:string = "";

 

=={{header|XPL0}}==

 

int N, I, C, Nest;

 

=={{header|Ya}}==

 

// all types are prefixed by `

 

=={{header|Yabasic}}==

local level, i

 

=={{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>

=={{header|ZX Spectrum Basic}}==

{{trans|AWK}}

20 READ s$

25 PRINT "The sequence ";s$;" is ";

2000 DATA "[]","][","][][","[][]","[][][]","[]][[]","[[[[[]]]]][][][]][]["

</syntaxhighlight>