Poprawność nawiasów

Zadanie 9 z 9 · rozdział 25Trudność: 2 z 3stringstacknawiasy

Treść zadania

Otrzymujesz napis, który oprócz dowolnych innych znaków może zawierać nawiasy trzech rodzajów: okrągłe (), kwadratowe [] i klamrowe {}. Pozostałe znaki pomijamy. Nawiasy są poprawne, jeśli każdy nawias zamykający zamyka nawias otwierający tego samego rodzaju, który został otwarty najpóźniej i jeszcze nie jest zamknięty, a na końcu napisu żaden nawias nie zostaje otwarty. Na przykład {[()()]} i a(b)[c] są poprawne, a ([)], (() i ()) — nie.

Sprawdź napis, czytając go od lewej do prawej:

  • jeśli trafisz na nawias zamykający, dla którego nie ma żadnego otwartego nawiasu albo ostatnio otwarty nawias jest innego rodzaju — błąd jest na pozycji tego nawiasu zamykającego (dalszej części napisu już nie sprawdzamy),
  • jeśli dojdziesz do końca bez takiego błędu, ale niektóre nawiasy pozostały otwarte — błąd jest na pozycji pierwszego (najbardziej na lewo) niezamkniętego nawiasu otwierającego.

Dane wejściowe

Jedna linia: napis S.

Dane wyjściowe

Tak, jeśli nawiasy są poprawne; w przeciwnym razie pozycja (indeks liczony od 0) pierwszego błędu.

Ograniczenia

  • 1 ≤ |S| ≤ 1000

Uwagi

  • Do tego zadania służy stos: struktura, do której dokładamy elementy na wierzch i zdejmujemy je z wierzchu (ostatni włożony wychodzi pierwszy). W Pythonie stosem jest zwykła lista: append kładzie element na wierzch, stos[-1] podgląda wierzch, a pop() go zdejmuje:
    ```python
    stos = []
    stos.append(3) # stos: [3]
    stos.append(7) # stos: [3, 7]
    print(stos[-1]) # 7 — wierzch stosu
    stos.pop() # zdejmuje 7, stos: [3]
    print(len(stos)) # 1
    `
  • Każdy nawias otwierający odkładaj na stos (najlepiej jego indeks — przyda się do zgłoszenia błędu). Przy nawiasie zamykającym sprawdź, czy stos nie jest pusty i czy na wierzchu leży nawias pasującego rodzaju; jeśli tak — zdejmij go. Pary nawiasów wygodnie trzymać w słowniku, np. {")": "(", "]": "[", "}": "{"}.
  • Po przejściu całego napisu niezamknięte nawiasy zostają na stosie — pierwszy z nich leży na samym dole (stos[0]).

Przykłady

Wejście
a(b[c]{d}e)f
Wyjście
Tak
Wejście
(a[b)c]
Wyjście
4

Nawias ) na pozycji 4 zamyka ostatnio otwarty nawias [, czyli nawias innego rodzaju.

Wejście
((x)(
Wyjście
0

Na końcu otwarte zostają nawiasy z pozycji 0 i 4 — pierwszy z nich jest na pozycji 0.

Potrzebujesz teorii?

Zasady obowiązujące w rozdziale 25

Trudniejsze zadania na napisach: samodzielna zamiana i usuwanie fragmentów, przedrostki, kodowanie RLE, rotacje, szukanie najdłuższych powtórzeń i wspólnych fragmentów (programowanie dynamiczne) oraz sprawdzanie nawiasów za pomocą stosu. Spróbuj rozwiązywać je własnymi pętlami, bez gotowych metod w rodzaju replace czy startswith — właśnie o to w nich chodzi.

Konwencje wspólne:

  • Każde zadanie to osobny program: czyta standardowe wejście i wypisuje wynik na standardowe wyjście.
  • Program nie wypisuje komunikatów typu „Podaj napis:”. Tekst podany w input("…") jest ignorowany przez sprawdzarkę.
  • Każdy napis zajmuje jedną całą linię wejścia, razem ze spacjami — wczytuj go przez input(), bez strip() i split().
  • Wielkość liter ma znaczenie (A i a to różne znaki), a spacja też jest znakiem.
  • Podnapis to ciągły fragment napisu, np. kot jest podnapisem kotlet, a ket — nie.
  • Pozycje znaków (indeksy) liczymy od 0, tak jak w Pythonie.
  • Odpowiedzi logiczne wypisuj jako Prawda albo Fałsz (o ile zadanie nie mówi inaczej).

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.

Python uruchomi się w przeglądarce przy pierwszym teście.

Kod zapisuje się automatycznie w tej przeglądarce. Tab wstawia wcięcie; aby opuścić edytor klawiaturą, naciśnij Esc, a potem Tab.

Testy

Program dostaje „Wejście” przez input() i musi wypisać „Oczekiwane wyjście”. Liczby porównywane są z tolerancją 0,01, a tekst podany w input("…") nie jest sprawdzany.

Test 1

Nie uruchomiono
Wejście
abc
Oczekiwane wyjście
Tak

Test 2

Nie uruchomiono
Wejście
)
Oczekiwane wyjście
0

Test 3

Nie uruchomiono
Wejście
(
Oczekiwane wyjście
0

Test 4

Nie uruchomiono
Wejście
(()
Oczekiwane wyjście
0

Test 5

Nie uruchomiono
Wejście
())
Oczekiwane wyjście
2

Test 6

Nie uruchomiono
Wejście
([)]
Oczekiwane wyjście
2

Test 7

Nie uruchomiono
Wejście
{[()()]}
Oczekiwane wyjście
Tak

Test 8

Nie uruchomiono
Wejście
((]
Oczekiwane wyjście
2

Test 9

Nie uruchomiono
Wejście
{}((
Oczekiwane wyjście
2

Test 10

Nie uruchomiono
Wejście
(()(
Oczekiwane wyjście
0

Test 11

Nie uruchomiono
Wejście
[(])
Oczekiwane wyjście
2

Test 12

Nie uruchomiono
Wejście
x = (a + b] * c
Oczekiwane wyjście
10

Test 13

Nie uruchomiono
Wejście
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((())))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
Oczekiwane wyjście
Tak

Test 14

Nie uruchomiono
Wejście
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((()))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
Oczekiwane wyjście
0

Test 15

Nie uruchomiono
Wejście
([[(-[*[]={=}] {()(bb-a+b--)}bxy)-]=])()( +( +- {{(y[**+= *b]-++)+y}{()*a{[x+x* -=+b**]a[ax -*y-y x](-)+(*){xx *b *axy-=}x}({+}){[ x] +(b)+=x}{y}}({{-=}(**-+a=bx=yxx==+**a-xbx= x*)*b}+x[]= a((-)*[ x*=x](  -=)(+ ){}{=a=x}[+]) []((*xbx-bb=-a)(-y+ )(yy)())a{[](aya)x(a a)()(aax-x)}*=)yb[((yy+-a){** +ayb=-}*y== )*][[( -+)]{}]})aa )(b)([+b]*)()(a[]+*)(x)()(+)()(a)( y(-{}){})()({})([]+*{})(+[a-(*a)*(y[[(a=*== +-==byby=-xby==== x)]]({y}()){})[b{(){(*)[*=][+-xx--](ax )}()[b()(a=+yab-=+=x*yy)()()-{y}( )+b {+ y +}[+bba+]]}-{y()ax{(=xxb=+)+{= -+a* }{b}{xa}(b**a-b-a)[yx]{bb*a+}a}(b)}(=[{**bb*}{-y}[ay *](+x= ) x[*xx * -=ya= *]{=ax-a+-a }(x  )a])]]{})(([xx{(ba a*(y*)b-{})a}[{}=]](x()*y[](=){=*}{}+=[xb([+==-]b){y{a+ +ax-=x=*a}}[a()+{x = *x}{x + -=y-yy --=*}]{x[*y =ab-]*(a-x-=     +*)}b])=)b)()(y)()(a)()(*{y[{{}{}[]([]{-++babayxby*}[=-]*( *){ *b}[y])[{++=-+y-}]={bb[y*y+a +x*a-xya=-x-x=]{}[](a )y}bxb }]-+})(-b+)(-)(=())()()(b )()([-]y)()()([*]x=[]y)()()()(*-*() )({} *)(*)(={}+(=[]))()(=-)(bbx)()({({(={bax*}a)})}{})(y)(+(({-[{a}(+y-)[]]{[*+ba*]*x=-[]+(x+a)x[==*y]}[[]={+y= y}bb-()( + a+--x+b)a(*=-xya*=)y(){==xb*yx-b}x(xay-)[yy+-bxby][ =]a]}[yb]+)))()()()()()([*-][][x =*b+ ]({ }))()(+)()()()()()(bb(y-){{a[x(bx[b--=ax=b-=*][-+b]-[a](y)[-*+*-a](- xxy*+xb ) ) [](){( x-a=xbx byby*==- a+)(+=)[-](x+=)[xyy -y]{=*}=}({}=[bb]( xy- ){a-bxx-xxa}{}*[aax] *+ya{ya-by+x**xyy  + *y-})({}){y{ay} x*}[]]-}a[({[]+[-yb]}=b+{y(+b){}(++ *+ +-)})]{}y }b)
Oczekiwane wyjście
Tak

Test 16

Nie uruchomiono
Wejście
([[(-[*[]={=}] {()(bb-a+b--)}bxy)-]=])()( +( +- {{(y[**+= *b]-++)+y}{()*a{[x+x* -=+b**]a[ax -*y-y x](-)+(*){xx *b *axy-=}x}({+}){[ x] +(b)+=x}{y}}({{-=}(**-+a=bx=yxx==+**a-xbx= x*)*b}+x[]= a((-)*[ x*=x](  -=)(+ ){}{=a=x}[+]) []((*xbx-bb=-a)(-y+ )(yy)())a{[](aya)x(a a)()(aax-x)}*=)yb[((yy+-a){** +ayb=-}*y== )*][[( -+)]{}]})aa )(b)([+b]*)()(a[]+*)(x)()(+)()(a)( y(-{}){})()({})([]+*{})(+[a-(*a)*(y[[(a=*== +-==byby=-xby==== x)]]({y}()){})[b{(){(*)[*=][+-xx--](ax )}()[b()(a=+yab-=+=x*yy)()()-{y}( )+b {+ y +}[+bba+]]}-{y()ax{(=xxb=+)+{= -+a* }{b}{xa}(b**a-b-a)[yx]{bb*a+}a}(b)}(=[{**bb*}{-y}[ay *](+x= ) x[*xx * -=ya= *]{=ax-a+-a }(x  )a])]]{})(([xx{(ba a*(y*)b-{})a}[{}=]](x()*y[](=){=*}{}+=[xb([+==-]b){y{a+ +ax-=x=*a}}[a()+{x = *x}{x + -=y-yy --=*}]{x[*y =ab-]*(a-x-=     +*)}b])=)b)()(y)()(a)()(*{y[{{}{}[]([]{-++babayxby*}[=-]*( *){ *b}[y])[{++=-+y-}]={bb[y*y+a +x*a-xya=-x-x=]{}[](a )y}bxb }]-+})(-b+)(-)(=())()()(b )()([-]y)()()([*]x=[]y)()()()(*-*() )({} *)(*)(={}+(=[]))()(=-)(bbx)()({({(={bax*}a)})}{})(y)(+(({-[{a}(+y-)[]]{[*+ba*]*x=-[]+(x+a)x[==*y]}[[]={+y= y}bb-()( + a+--x+b)a(*=-xya*=)y(){==xb*yx-b}x(xay-)[yy+-bxby][ =]a]}[yb]+)))()()()()()([*-][][x =*b+ ]({ }))()(+)()()()()()(bb(y-){{a[x(bx[b--=ax=b-=*][-+b]-[a](y)[-*+*-a](- xxy*+xb ) ) [](){( x-a=xbx byby*==- a+)(+=)[-](x+=)[xyy -y]{=*}=}({}=[bb]( xy- ){a-bxx-xxa}{}*[aax] *+ya{ya-by+x**xyy  + *y-})({}){y{ay} x*}[]]-}a[({[]+[-yb]}=b+{y(+b){}(++ *+ +-)})]{}y }b]
Oczekiwane wyjście
1432
Uruchom z własnymi danymi