Table of contentsClick link to navigate to the desired location
This content has been automatically translated from Ukrainian.
The condition for the task is as follows. Create a function valid_braces that takes a string consisting only of brackets: ()[]{}. The function should return true if all brackets open and close in the correct order, or false if the brackets are incorrectly placed.
Example of method execution:
valid_braces("()") → true
valid_braces("({[]})") → true
valid_braces("({[)]}") → false
valid_braces("(((()") → false
valid_braces("{[()]}[]") → true
How does bracket checking work?
This task is classically solved using a stack — a data structure that works on the principle of "last in, first out". The idea is to add opening brackets to the stack, and when we encounter a closing bracket — check if it matches the one at the top of the stack. If so — remove it from the stack; if not — the string is incorrect.
Test (RSpec) for checking the method
RSpec.describe '#valid_braces' do
it 'returns true for valid brackets' do
expect(valid_braces('()')).to eq(true)
expect(valid_braces('([])')).to eq(true)
expect(valid_braces('{[()]}')).to eq(true)
expect(valid_braces('{[()]}[]')).to eq(true)
end
it 'returns false for invalid brackets' do
expect(valid_braces('[(])')).to eq(false)
expect(valid_braces('({[)]}')).to eq(false)
expect(valid_braces('((')).to eq(false)
expect(valid_braces(']')).to eq(false)
end
end
Method valid_braces
def valid_braces(string)
stack = []
pairs = { ')' => '(', ']' => '[', '}' => '{' }
string.each_char do |char|
if pairs.values.include?(char)
stack.push(char)
elsif pairs.keys.include?(char)
return false if stack.pop != pairs[char]
end
end
stack.empty?
end
Algorithm operation principle
- Each time we see an opening bracket — we add it to the stack.
- If we encounter a closing one — we compare it with the last opening one (from the top of the stack).
- If they match — we continue.
- If not — we immediately return false.
- If the stack is empty after processing the string — all brackets were correctly closed, so we return true.
This approach can be used for paired symbols of any type — not just brackets. It is well-suited for checking the correctness of nested structures, for example, in parsers or HTML analyzers.
This post doesn't have any additions from the author yet.
