#algo #ruby

brackets.rb

# You are given a template for an expression with parantheses.
# For every template, print all possible valid parantheses expressions.

def solution template, index, balance
	if balance < 0
		return
	end

	# handles ? as last character in template
	if index >= template.length
		if balance == 0
			p template
		end
		return
	end

	found_blank = false # every function call shall handle only one blank character

	template[index..-1].each_char.with_index(0) do |c, i|
		if balance < 0
			return
		end

		if c == '?' && !found_blank
			found_blank = true

			template[index+i] = '('
			solution(template, index+i+1, balance+1)
			template[index+i] = ')'
			solution(template, index+i+1, balance-1)
			template[index+i] = '?'
		elsif c == '('
			balance += 1
		elsif c == ')'
			balance -= 1
		end
	end

	# prevents ??() from being printed
	# only for when there are no more ? left in the template to be processed
	if balance == 0 && !found_blank
		p template
	end
end

test_cases = ['??()', '(??())', '()(?', '()??)?', '?())', '?()?', '?()))']
test_cases.each do |t|
	p "For test case #{t}: "
	solution t, 0, 0
end