Difference between revisions of "RosettaCode Balanced Brackets"

Latest revision as of 01:39, 3 October 2012

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