View source for RosettaCode Balanced Brackets

You do not have permission to edit this page, for the following reasons:

The action you have requested is limited to users in one of the groups: Autoconfirmed users, emailconfirmed, editors.
You must confirm your email address before editing pages. Please set and validate your email address through your user preferences.

You can view and copy the source of this page:

[[Category:Rosetta Code]]
[[Category:Flash Code]]

'''-> [[RosettaCode]] Overview'''

==Reference==
Statement of the Balanced Brackets problem on RosettaCode: [http://rosettacode.org/wiki/Balanced_brackets here].

==Eiffel code==

Here's a candidate implementation using [[EiffelBase2]]:

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

Return to RosettaCode Balanced Brackets.

Retrieved from "https://dev.eiffel.com/RosettaCode_Balanced_Brackets"

View source for RosettaCode Balanced Brackets

Navigation

Development

Wiki

Search

Tools