# RosettaCode Balanced Brackets

-> RosettaCode Overview

## Reference

Statement of the Balanced Brackets problem on RosettaCode: here.

## Eiffel code

Here's a candidate implementation using EiffelBase2:

```class
BALANCED_BRACKETS

create
make

feature {NONE} -- Initialization

make
-- Generate bracket string.
local
random: V_RANDOM
do
create random
count := 2 * random.bounded_item (0, Max_half_count)
--			count := 50
create brackets.make (1, count)
fill_random
brackets := as_boolean_array ("") ; printout
brackets := as_boolean_array ("[]") ; printout
brackets := as_boolean_array ("[][]") ; printout
brackets := as_boolean_array ("[[][]]") ; printout
brackets := as_boolean_array ("][") ; printout
brackets := as_boolean_array ("][][") ; printout
brackets := as_boolean_array ("[]][[]") ; printout
end

feature -- Access

Max_half_count: INTEGER = 10
-- Maximum possible value for count // 2.

count: INTEGER
-- Number of items in bracket sequence.

brackets: V_ARRAY [BOOLEAN]
-- The string of brackets to be generated and analyzed.
-- True is opening bracket, False is closing.

feature -- Basic operations

is_balanced: BOOLEAN
-- Is bracket string represented by `brackets' bracket-balanced?
local
balance: INTEGER
do
Result := True
across brackets as b until not Result loop
if b.item then
balance := balance + 1
else
if balance = 0 then
Result := False
else
balance := balance - 1
end
end
end
Result := Result and (balance = 0)
end

feature -- Conversion

as_bracket_string (br: V_ARRAY [BOOLEAN]): STRING
-- `br' understood as a string consisting solely of opening and closing brackets.
do
create Result.make (count)

across br as b loop
if b.item then
Result.extend ('[')
else
Result.extend (']')
end
end

end

as_boolean_array (bs: STRING): V_ARRAY [BOOLEAN]
-- `br' turned into boolean array ("[" is True, "]"is False).
require
exists: bs /= Void
only_brackets: bs.occurrences ('[') + bs.occurrences (']') = bs.count
do
create Result.make (1, bs.count)
across bs as b loop
Result [b.target_index] := (b.item = '[')
end

end

feature -- Input and output

printout
-- Output result.
do
print ("Bracket string: ")
print (as_bracket_string (brackets)+ "%T")
if not is_balanced then
print ("NOT ")
end
print ("OK%N")
end

feature {NONE} -- Implementation

fill_random
-- Set `count//2' random `brackets' position to opening.
local
random: V_RANDOM
filled, pos: INTEGER
do
from
create random
invariant
filled <= count // 2
until
filled = count // 2
loop
pos := random.bounded_item (brackets.lower, brackets.upper)
if not brackets [pos] then
brackets [pos] := True
filled := filled + 1
end
random.forth
-- variant
-- Interestingly enough, there is no  variant as this
-- loop might in principle not terminate, depending
-- on the properties of the random generator.
end
end

invariant
count_limit: count <= 2 * Max_half_count
array_length_consistent: brackets.count = count

end```