Zárójelek
Stanford Local Programming Contest, 2004. 5. feladat
Megadjuk a "rendes zárójelezések" definícióját:
- az üres sorozat rendes zárójelezés
- ha s rendes zárójelezés, akkor (s) és [s] is az
- ha a és b rendes, akkor ab is rendes
- a többi sorozat nem rendes zárójelezés
Például a következő zárójelezések rendesek:
(), [], (()), ()[], ()[()],
ezek pedig nem:(, ], )(, ([)], ([(].
ezek pedig nem:(, ], )(, ([)], ([(].
Feladat
Zárójelek egy adott sorozatára adjuk meg a leghosszabb rendes zárójelezész leíró részsorozat hosszát!
Bemenet
A bemenet több tesztesetet tartalmaz. A tesztesetek egy-egy sorban vannak, és csak a "(", ")", "[", és "]" karaktereket tartalmazzák; a bemeneti sorok hossza legfeljebb 100.
A bemenet végét egy az "end" szöveget tartalmazó sor jelzi.
Kimenet
A kimenet minden sorába a megfelelő tesztesetre számolt maximális részsorozat hosszát kell írni.
Példák
A ([([]])] sorozatban a leghosszabb rendes zárójelezést adó részsorozat:
[([])].
| brackets.in | brackets.out |
|
((())) ()()() ([]]) )[)( ([][][) end |
6 6 4 0 6 |