0852 - Paranteze3
De la Universitas MediaWiki
Cerința
Se dau n șiruri de paranteze rotunde sau pătrate. Să se stabilească, despre fiecare șir, dacă este corect parantezat – adică dacă parantezele se închid corect.
Un șir de paranteze S rotunde este corect parantezat dacă:
- S este șirul vid, sau
- S = (T) și T este corect parantezat, sau
- S = [T] și T este corect parantezat, sau
- S = AB, iar A și B sunt corect parantezate.
Date de intrare
Fișierul de intrare paranteze3in.txt conține pe prima linie numărul n, pe următoarele n linii câte un șir de paranteze rotunde sau pătrate.
Date de ieșire
Fișierul de ieșire paranteze3out.txt va conține n linii: fiecare linie va conține valoarea 1, dacă șirul corespunzător de paranteze este corect parantezat și 0 în caz contrar.
Restricții și precizări
- 1 ≤ n ≤ 100
- fiecare șir va avea cel mult 255 de paranteze
Exemplul 1:
paranteze3in.txt
- 4
- ()[]
- )([]
- ()[(()[])()]
([)]
paranteze3out.txt
- Datele de intrare corespund restrictiilor impuse
- 1
- 0
- 1
- 0
Exemplul 2:
paranteze3in.txt
- ana are mere
paranteze3out.txt
- Datele de intrare nu corespund restrictiilor impuse
Rezolvare
def validare(numar, strings): # functia de validare a datelor de intrare
if numar < 1 or numar > 100:
raise ValueError
for sir in strings:
if len(sir) > 255:
raise ValueError
file_out.write("Datele de intrare corespund restrictiilor impuse\n")
def verifica_paranteze(sir): # functia de rezolvare
stiva = []
for paranteza in sir:
if paranteza in "([":
stiva.append(paranteza)
else:
if not stiva:
return 0
top = stiva.pop()
if paranteza == ")" and top != "(":
return 0
elif paranteza == "]" and top != "[":
return 0
if stiva:
return 0
return 1
if __name__ == '__main__':
file_in = open('paranteze3in.txt', 'r')
file_out = open('paranteze3out.txt', 'w')
try:
n = int(file_in.readline().strip())
siruri = [file_in.readline().strip() for _ in range(n)]
validare(n, siruri)
rezultate = [verifica_paranteze(sir) for sir in siruri]
for rezultat in rezultate:
file_out.write(str(rezultat) + '\n')
except ValueError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")
except IndexError:
file_out.write("Datele de intrare nu corespund restrictiilor impuse")