Sa consideram secvente constituite numai din paranteze rotunde si paranteze
patrate, adica din caracterele ( ) [
].
Prin definitie, o secventa de paranteze este regulata daca se obtine
aplicand urmatoarele reguli:
1.() si []
sunt secvente regulate.
2. Daca A este regulata, atunci
(A) si [A]
sunt secvente regulate.
3. Daca A si B
sunt regulate, atunci AB este
secventa regulata.
De exemplu, () () [] si [(())][]
sunt regulate, in timp ce ][
sau [(] sau([)]
nu sunt regulate.
Se considera o secventa de paranteze.
La fiecare pas se insereaza o paranteza (rotunda sau patrata, deschisa sau inchiss)
la inceputul sau la sfarsitul secventei.
Cerinta
Scrieti
un program care sa determine, dupa fiecare pas, lungimea celei mai scurte subsecvente
regulate (formata din caractere consecutive ale secventei) care contine paranteza
inserata la pasul respectiv.
Date de intrare
Fisierul
de intrare secvreg.in contine
pe prima linie secventa initiala de paranteze. Pe cea de a doua linie a fisierului
de intrare se afla un numar natural N
care reprezinta numarul de pasi.
Fiecare dintre urmatoarele N
linii contine un numar natural A
si un caracter C separate printr-un
singur spatiu. Daca A este 0
(zero) atunci caracterul C este
inserat la inceputul secventei; daca A
este 1 (unu) atunci caracterul
C este inserat la sfarsitul secventei.
Date de iesire
Fisierul
de iesire secvreg.out contine
N linii. Pe cea de a i-a
linie va fi afisata lungimea celei mai scurte subsecvente regulate (formata
din caractere consecutive ale secventei) care contine paranteza inserata la
pasul i. Daca nu exista o astfel
de subsecventa, pe linia respectiva veti afisa 0.
Restrictii
Lungimea
secventei initiale de paranteze <=100
000
1<=N<=100 000
Exemple
secvreg.in
secvreg.out
secvreg.in
secvreg.out
secvreg.in
secvreg.out
( 1
1 )
2
(]
3
1 )
0 )
0 (
0
0
2
[])
3
0 )
0 (
0 (
0
2
6
prof. Emanuela
Cerchez
Liceul de Informatica "Grigore Moisil" Iasi