InhaltsverzeichnisKlicke auf den Link, um zur gewünschten Stelle zu navigieren
Dieser Inhalt wurde automatisch aus dem Ukrainischen übersetzt.
Die Bedingung für die Aufgabe ist folgende. Erstellen Sie die Funktion valid_braces, die einen String akzeptiert, der nur aus Klammern besteht: ()[]{}. Die Funktion sollte true zurückgeben, wenn alle Klammern in der richtigen Reihenfolge geöffnet und geschlossen werden, oder false — wenn die Klammern inkorrekt angeordnet sind.
Beispiel für die Ausführung der Methode:
valid_braces("()") → true
valid_braces("({[]})") → true
valid_braces("({[)]}") → false
valid_braces("(((()") → false
valid_braces("{[()]}[]") → true
Wie funktioniert die Klammerüberprüfung?
Diese Aufgabe wird klassisch mit einem Stack gelöst — einer Datenstruktur, die nach dem Prinzip „Last In, First Out“ funktioniert. Die Idee besteht darin, öffnende Klammern in den Stack hinzuzufügen, und wenn wir auf eine schließende Klammer stoßen — zu überprüfen, ob sie der Klammer an der Spitze des Stacks entspricht. Wenn ja — entfernen wir sie aus dem Stack; wenn nein — ist der String ungültig.
Test (RSpec) zur Überprüfung der Methode
RSpec.describe '#valid_braces' do
it 'gibt true für gültige Klammern zurück' 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 'gibt false für ungültige Klammern zurück' 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
Methode 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
Funktionsweise des Algorithmus
- Jedes Mal, wenn wir eine öffnende Klammer sehen — fügen wir sie dem Stack hinzu.
- Wenn wir auf eine schließende stoßen — vergleichen wir sie mit der letzten öffnenden (von der Spitze des Stacks).
- Wenn sie übereinstimmen — machen wir weiter.
- Wenn nicht — geben wir sofort false zurück.
- Wenn der Stack nach dem Durchlauf des Strings leer ist — wurden alle Klammern korrekt geschlossen, also geben wir true zurück.
Dieser Ansatz kann für Paarzeichen beliebigen Typs verwendet werden — nicht nur für Klammern. Er eignet sich hervorragend zur Überprüfung der Richtigkeit von verschachtelten Strukturen, beispielsweise in Parsern oder HTML-Analyzern.
