De Python syntaxis vereist dat alle haakjes gebalanceerd zijn. Dit betekent dat elk geopend haakje verderop in de broncode ook moet afgesloten worden en dat elk haakje dat gesloten wordt, eerder in de broncode reeds moet geopend zijn. Als de haakjes niet gebalanceerd zijn, dan resulteert dit in een compileerfout. Hieronder zie je bijvoorbeeld welke haakjes met elkaar corresponderen in het gebalanceerde tekstfragment (()(()(()))()(()())).

Schrijf een programma dat voor een gegeven tekstfragment kan beslissen of de gebruikte haakjes al dan niet gebalanceerd zijn.

Invoer

De eerste regel van de invoer bevat een getal $$t \in \mathbb{N}$$. Daarna volgen $$t$$ regels die elk een een tekstfragment bevatten. Je mag ervan uitgaan dat in elk tekstfragment slechts één soort haakjes gebruikt wordt. De mogelijke haakjes waarmee je rekening moet houden zijn ( en ), { en }, < en > en [ en ].

Uitvoer

Voor elk tekstfragment uit de invoer moet een regel uitgeschreven worden met de tekst gebalanceerd als de haakjes gebalanceerd zijn, of de tekst ongebalanceerd als de haakjes niet gebalanceerd zijn.

Algoritme

Als een gegeven tekstfragment maar één soort haakjes bevat, dan kan je het volgende algoritme gebruiken om na te gaan of die haakjes gebalanceerd zijn:

1. initialiseer een teller met waarde 0

2. doorloop de karakters van het tekstfragment van links naar rechts, en

1. verhoog de teller met één indien het karakter een geopend haakje is

2. verlaag de teller met één indien het karakter een gesloten haakje is; als de teller hierna negatief geworden is, dan betekent het dat er vóór dit punt in het tekstfragment meer gesloten dan geopende haakjes zijn (wat niet toegelaten is)

3. als de teller na het doorlopen niet gelijk is aan nul, dan betekent dit dat het aantal geopende haakjes niet gelijk is aan het aantal gesloten haakjes (wat niet toegelaten is)

Voorbeeld

Invoer:

4
(()()(()))
[[[[[ ]]]]
een (twee (drie) vier) vijf
)(

Uitvoer:

gebalanceerd
ongebalanceerd
gebalanceerd
ongebalanceerd