Írjunk egy függvényt, amely ellenőrzi, hogy egy megadott szövegben minden kerek nyitó zárójelhez tartozik-e ugyanannyi csukó zárójel, és hogy egyetlen csukó zárójel sem jelenik-e meg a hozzá tartozó nyitó párja előtt. A függvény True értékkel térjen vissza, ha ezek a feltételek teljesülnek, egyébként False értéket adjon vissza.
Például az ‘f(x) és g(x)’ szövegben a zárójelezés megfelelő hiszen a nyitó és csukó zárójelek száma megegyezik és minden csukó zárójel a nyitó párja után van. De a ‘) f(x) és g(x)’, az ‘f(x)) és g(x)’ vagy ‘f((x) és g(x)’ szövegek esetében a zárójelezés hibás.
Az ellenőrző függvényünkre egy lehetséges megoldás a következő. Egy state nevű változót hozunk létre 0 kezdőértékkel. Ezt követően vesszük balról jobbra haladva a szöveg egyes karaktereit és megnézzük, hogy az nyitó vagy csukó kerek zárójel-e. Ha nyitó, akkor a state értékét eggyel növeljük, ha csukó, akkor eggyel csökkentjük. Ha az iteráció során a state változó bármikor negatív értékű lesz, az azt jelenti, hogy a csukó zárójel előbb jön, mint a nyitó, így biztos, hogy a zárójelezés nem megfelelő. Ezért ilyenkor azonnal kilépünk a ciklusból és False értékkel térünk vissza. Ha a state nem lesz negatív az iteráció során, akkor a legvégén pozitív értékű vagy 0 lehet. Ha pozitív, akkor az azt jelenti, hogy több nyitó zárójel szerepelt a szövegben, mint csukó. Tehát a függvény csak akkor térhet vissza True értékkel, ha a state értéke 0. E függvénydefiníciót 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 27 28 29 30 31 32 33 34 35 |
def are_brackets_balanced(txt: str): """Ellenőrzi, hogy a megadott szövegben minden kerek nyitó zárójelhez tartozik-e ugyanannyi csukó zárójel, és hogy egyetlen csukó zárójel sem jelenik-e meg a hozzá tartozó nyitó párja előtt. A függvény True értékkel tér vissza, ha ezek a feltételek teljesülnek, egyébként False értéket ad vissza. """ state = 0 # Zárójelfeldolgozási állapotot jelző érték. for c in txt: if c == '(': state += 1 if c == ')': state -= 1 # Ha az állapotot jelző számérték pozitív, akkor több nyitó zárójel van feldolgozva, mint csukó. # Ha negatív, akkor egy csukó zárójel jelent meg a hozzá tartozó azonos típusú nyitó zárójel előtt. # Csak akkor True az eredmény, ha az állapotjelző értéke 0. if state < 0: return False return True if state == 0 else False # TESZT texts = ('f(x)', 'fx)', ')f(x)', 'a) f(x):', 'f(x))(', '((1,2), (3,4))') for text in texts: if not are_brackets_balanced(text): print(f'Zárójelezési hiba: "{text}"') # Eredmény: # Zárójelezési hiba: "fx)" # Zárójelezési hiba: ")f(x)" # Zárójelezési hiba: "a) f(x):" # Zárójelezési hiba: "f(x))(" |
Ami a két feltételes elágazásban történik, azt úgy is átfogalmazhatjuk, hogy nyitó zárójel esetén +1, csukó zárójel esetén -1 értéket kell hozzáadni a state aktuális értékéhez, majd ezzel az összeggel kell aktualizálni a state értéké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. E hívás eredménye három szám lehet: +1, ha az aktuális karakter nyitó zárójel, -1, ha csukó, és 0, ha az aktuális karakter se nem nyitó, se nem csukó kerek zárójel. A get() metódus eredményével módosítjuk a state értékét. Ezzel a változattal megvalósított függvény definíciója 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 |
def are_brackets_balanced(txt: str): """Ellenőrzi, hogy a megadott szövegben minden kerek nyitó zárójelhez tartozik-e ugyanannyi csukó zárójel, és hogy egyetlen csukó zárójel sem jelenik-e meg a hozzá tartozó nyitó párja előtt. A függvény True értékkel tér vissza, ha ezek a feltételek teljesülnek, egyébként False értéket ad vissza. """ state = 0 # Zárójelfeldolgozási állapotot jelző érték. for c in txt: state += {'(': +1, ')': -1}.get(c, 0) # Ha az állapotot jelző számérték pozitív, akkor több nyitó zárójel van feldolgozva, mint csukó. # Ha negatív, akkor egy csukó zárójel jelent meg a hozzá tartozó azonos típusú nyitó zárójel előtt. # Csak akkor True az eredmény, ha az állapotjelző értéke 0. if state < 0: return False return True if state == 0 else False # TESZT texts = ('f(x)', 'fx)', ')f(x)', 'a) f(x):', 'f(x))(', '((1,2), (3,4))') for text in texts: if not are_brackets_balanced(text): print(f'Zárójelezési hiba: "{text}"') # Eredmény: # Zárójelezési hiba: "fx)" # Zárójelezési hiba: ")f(x)" # Zárójelezési hiba: "a) f(x):" # Zárójelezési hiba: "f(x))(" |
Vajon e megoldásnak van-e haszna azon túl, hogy egy jó gyakorlás a dict típusú szótár használatára?
Igen van, mégpedig akkor, ha a függvényünket úgy akarjuk általánosítani, hogy ne csak 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 ellenőrzésére is képes legyen.
Az új követelményeknek természetesen meg lehetne úgy felelni, hogy minden egyes új zárójeltípushoz újabb és újabb feltételes elágazásokat illesztünk a függvénytörzsbe. Ez a módszer azonban általában nem ajánlott, mert minden módosításnál hibát vihetünk be egy már letesztelt kódba, ezért minden módosítás után tesztelni is kellene, ami idő- és munkaigényes.
A szótárral történő bemutatott 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ényt 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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
def are_brackets_balanced(txt: str, brackets: str = '()') -> bool: """Ellenőrzi, hogy a megadott szövegben minden nyitó zárójelhez tartozik-e ugyanannyi csukó zárójel, és hogy egyetlen csukó zárójel sem jelenik-e meg a hozzá tartozó nyitó párja előtt. A függvény True értékkel tér vissza, ha ezek a feltételek teljesülnek, egyébként False értéket ad vissza. A vizsgálandó zárójelpárokat a brackets paraméterben kell megadni, szóközzel elválasztva. Egy zárójelpáron belül először a nyitó, majd a csukó zárójel szerepel. Példák: brackets='()' csak a kerek zárójeleket ellenőrzi brackets='() [] {}' kerek, szögletes és kapcsos zárójeleket ellenőriz """ # Ha az állapotot jelző számérték pozitív, akkor több nyitó zárójel van feldolgozva, mint csukó. # Ha negatív, akkor egy csukó zárójel jelent meg a hozzá tartozó azonos típusú nyitó zárójel előtt. bracket_pair_states = [] for opening, closing in brackets.split(): bracket_pair_states.append([dict(zip((opening, closing), (+1, -1))), 0]) for c in txt: for bracket_state in bracket_pair_states: bracket_state[1] += bracket_state[0].get(c, 0) if bracket_state[1] < 0: return False # Csak akkor True az eredmény, ha minden zárójeltípushoz tartozó állapotjelző értéke 0. return all(state == 0 for _, state in bracket_pair_states) # TESZT texts = ('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 text in texts: if not are_brackets_balanced(text, '() [] {}'): print(f'Zárójelezési hiba: "{text}"') # Eredmény: # Zárójelezési hiba: "fx)" # Zárójelezési hiba: ")f(x)" # Zárójelezési hiba: "a) f(x):" # Zárójelezési hiba: "f(x))(" # Zárójelezési hiba: "f(x, [[1,2])" # Zárójelezési hiba: "f(x, [1,2], {3, 4}})" # Zárójelezési hiba: "f((x, [1,2], {3, 4})" |
A függvény első paramétere fogadja a vizsgálandó szöveget. Második argumentumként lehet megadni a zárójelpárokat egy karakterláncban, szóközzel elválasztva. Alapértelmezetten a kerek zárójelpár 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ásodik eleme az adott zárójelfajtához tartozó állapotérték 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 nyitó vagy csukó változatának egyikével egyezik-e. Ha igen, akkor vagy növeljük, vagy csökkentjük a hozzá tartozó állapotértéket. Ha menet közben valamelyik érték negatív, akkor rögtön visszatérünk False értékkel. Ha nem, akkor a végén megvizsgáljuk, hogy minden állapot 0 értékű-e. Ha igen, akkor True lesz az ellenőrzés eredménye, egyébként False.
Megjegyzés: A bemutatott megoldás azt ellenőrzi, hogy egy adott típusú nyitó zárójelhez tartozik-e ugyanannyi csukó zárójel, és hogy egyetlen csukó zárójel sem jelenik-e meg a hozzá tartozó nyitó párja előtt. Nem vizsgálja azonban a különböző típusú zárójelek egymásba ágyazásának helyességét, ezért például a ’( [ ) ]’ karakterláncot helyesnek tekinti. Az ilyen esetek felismeréséhez verem (stack) alapú megoldás szükséges.
A cikk célja azonban nem egy teljes körű zárójel-ellenőrző algoritmus ismertetése, hanem annak szemléltetése, hogyan válthatunk ki egy nehezen bővíthető if–elif szerkezetet egy adatvezérelt megoldással. A zárójelek ellenőrzése csupán egy gyakorlati példa ennek a technikának a bemutatására.
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 az alapoktól az első asztali alkalmazásig című 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.