Írjunk egy függvényt, ami True értéket ad vissza, ha az argumentumban megadott szövegben a kerek zárójelek párosítottak, vagyis megfelelő sorrendben minden bal zárójelhez tartozik jobb zárójel. Ha ez nem teljesül, akkor a függvény visszatérési értéke False.
Ha balról az első zárójel jobb zárójel, akkor biztos, hogy nem lesznek megfelelően párosítottak a zárójelek. Ha pedig balról jobbra haladva párosított zárójelek után jobb zárójel jön, akkor szintén biztos, hogy a megkívánt feltétel nem teljesül. Például az „f(x)” szövegben megfelelően párosítottak a zárójelek, de a „) f(x)”, „f(x))” vagy „f((x)” esetekben már nem.
Ezek végigondolása után már nem nehéz a függvénytörzs logikájának lekódolása. Egy számlálót inicializálunk 0 értékkel, majd vesszük balról jobbra haladva a szöveg egyes karaktereit és megnézzük, hogy az bal vagy jobb kerek zárójel-e. Ha bal zárójel, akkor a számlálót eggyel növeljük, ha jobb zárójel, akkor eggyel csökkentjük a számláló értékét. Ha az iteráció során a számláló bármikor negatív érték lesz, az azt jelenti, hogy a jobb zárójel előbb jön, mint a bal, így biztos nem lehet párosított. Ezért azonnal kilépünk a ciklusból és False értékkel térünk vissza. Ha a számláló nem lesz negatív az iteráció során, akkor a végén lehet pozitív vagy 0. Ha pozitív, akkor az azt jelenti, hogy több bal zárójel szerepelt a szövegben, mint jobb. Tehát a függvény csak akkor térhet vissza True értékkel, ha a számláló 0.
Ennek alapján a függvénydefiníció a következő:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
# 1. megoldás feltételes elágazásokkal. def zárójelek_párosítottak(s: str): számláló = 0 for c in s: if c == '(': számláló += 1 if c == ')': számláló -= 1 if számláló < 0: return False return True if számláló == 0 else False |
A két feltételes elágazást úgy is megfogalmazhatjuk, hogy bal zárójel esetén +1, jobb zárójel esetén -1 értéket kell hozzáadni a számláló aktuális értékéhez, majd ezzel az összeggel kell aktualizálni a számlálót. Ez lényegében egy megfeleltetést jelent a zárójelek, valamit a +1 és -1 értékek között, amit egy szótárral valósíthatunk meg. Ha így teszünk, akkor a szótár get() metódusát meg tudjuk hívni a cikluson belül az aktuális karakterrel, valamint 0 alapértelmezett értékkel. Így, ennek eredménye három szám lehet: +1, ha az aktuális karakter bal zárójel, -1, ha jobb, és 0, ha az aktuális karakter se nem bal, se nem jobb kerek zárójel. A get() metódus eredményével módosítjuk a számláló értékét. Ezzel a változattal megvalósított függvényt és a teszteredményeket láthatjuk alább.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
# 2. megoldás szótárral. def zárójelek_párosítottak(s: str): számláló = 0 for c in s: számláló += {'(': +1, ')': -1}.get(c, 0) if számláló < 0: return False return True if számláló == 0 else False # TESZT szövegek = ('f(x)', 'fx)', ')f(x)', 'a) f(x):', 'f(x))(', '((1,2), (3,4))') for szöveg in szövegek: if not zárójelek_párosítottak(szöveg): print(f'Hibás zárójelpárosítás: "{szöveg}"') # Eredmény: # Hibás zárójelpárosítás: "fx)" # Hibás zárójelpárosítás: ")f(x)" # Hibás zárójelpárosítás: "a) f(x):" # Hibás zárójelpárosítás: "f(x))(" |
Vajon e megoldásnak van-e haszna azon túl, hogy érdekes, és egy jó gyakorlat a szótár használatára? Igen, mégpedig akkor, ha a függvényünket úgy akarjuk általánosítani, hogy ne csak a szövegben szereplő kerek zárójelekre, hanem más zárójelfajtákra, például a szögletes vagy akár a kapcsos zárójelek párosítottságának ellenőrzésére is képes legyen.
Természetesen meg lehetne úgy oldani e kibővített igényű feladatot, hogy újabb és újabb feltételes elágazásokat teszünk be a függvénytörzsbe. Ez azonban általában nem ajánlott, mert minden módosításnál hibát vihetünk be, ezért tesztelni is illene minden alkalommal, ami erőforrásigényes.
A szótárral történő megoldás elve azonban általánosítható, és ezzel olyan kód alakítható ki, amely újabb zárójelfajta esetén nem igényli, hogy a függvény definícióján változtassunk. Az így megvalósított függvény a következő:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
def zárójelek_párosítottak(s: str, zárójelek: str = '()'): # Az egyes zárójelpárokhoz tartozó számlálók és szótárak listáit tartalmazó lista. számlálók_szótárak = [] for bz, jz in zárójelek.split(): számlálók_szótárak.append([0, dict(zip((bz, jz), (+1, -1)))]) for c in s: for elem in számlálók_szótárak: számláló, szótár = elem elem[0] += szótár.get(c, 0) if számláló < 0: return False # Ha az egyes számlálók értéke minden zárójelfajtára 0, akkor lesz csak True a visszatérési érték. return True if all([számláló == 0 for számláló, _ in számlálók_szótárak]) else False # TESZT szövegek = ('f(x)','fx)', ')f(x)','a) f(x):','f(x))(', '((1,2), (3,4))', 'f(x, [1,2])', 'f(x, [[1,2])', 'f(x, [1,2], {3, 4})', 'f(x, [1,2], {3, 4}})', 'f((x, [1,2], {3, 4})') for szöveg in szövegek: if not zárójelek_párosítottak(szöveg, '() [] {}'): print(f'Hibás zárójelpárosítás: "{szöveg}"') # Eredmény: # Hibás zárójelpárosítás: "fx)" # Hibás zárójelpárosítás: ")f(x)" # Hibás zárójelpárosítás: "a) f(x):" # Hibás zárójelpárosítás: "f(x))(" # Hibás zárójelpárosítás: "f(x, [[1,2])" # Hibás zárójelpárosítás: "f(x, [1,2], {3, 4}})" # Hibás zárójelpárosítás: "f((x, [1,2], {3, 4})" |
A függvény első paramétere fogadja a vizsgálandó szöveget. A második argumentumban lehet megadni a zárójelpárokat egy karakterláncban, szóközzel elválasztva a párokat. Alapértelmezetten a kerek zárójel szerepel. Az egyes zárójelfajtáknak megfelelően létrehozzuk a +1, -1 értéket megfeleltető szótárakat, majd ezeket egy-egy kételemű listába helyezzük, amelyek másik eleme az adott zárójelfajtához tartozó számláló lesz 0 kezdőértékkel. Ezeket a kételemű listákat egy másik listában gyűjtjük össze. A kód többi része az előzőekben vázolt feldolgozási logikának az adaptálása: végig iterálunk a szöveg karakterein és minden egyes karakterre megnézzük, hogy a megadott zárójelfajták bal vagy jobb változatának egyikével egyezik-e. Ha igen, akkor vagy növeljük, vagy csökkentjük a hozzá tartozó számlálót. Ha menet közben valamelyik számláló negatív, akkor rögtön visszatérünk False értékkel. Ha nem, akkor a végén megvizsgáljuk, hogy minden számláló 0 értékű-e. Ha igen, akkor True, ha nem nulla, akkor False lesz az ellenőrzés eredménye.
Ebben a feladatban a dict típusú szótárobjektumnak kiemelt szerepe volt. Erről a Python tudásépítés lépésről lépésre e-könyv „Beépített konténerobjektumok” fejezet „Szótár” alfejezetében, valamint a „Beépített típusok nyilvános metódusai” fejezet „Leképzés típusú konténerek” alfejezetében olvashatunk bővebben.