Vrsta in sklad

V primeru niza '[(){[]}]' bi postopek tekel takole:

Korak	Znak	Dejanje	Sklad
(1)	[	dodaj na sklad	[
(2)	(	dodaj na sklad	[(
(3)	)	odvzemi s sklada in preveri ujemanje	[
(4)	{	dodaj na sklad	[{
(5)	[	dodaj na sklad	[{[
(6)	]	odvzemi s sklada in preveri ujemanje	[{
(7)	}	odvzemi s sklada in preveri ujemanje	[
(8)	]	odvzemi s sklada in preveri ujemanje
(9)		sklad je prazen ⇒ `return True`

V primeru niza '[(){[}]]' pa bi se postopek končal že pri koraku (6), saj se prebrani zaklepaj } ne bi ujemal s predklepajem [, ki bi ga v tem koraku odvzeli s sklada.

Zakaj opisana logika deluje? Zato, ker se na skladu vedno nahajajo tisti predklepaji, ki še niso zaključeni, in to po vrsti od skrajnega zunanjega do skrajnega notranjega (če gledamo od dna do vrha sklada). Na vrhu sklada se torej nahaja tisti predklepaj, ki ga moramo najprej zaključiti. Preveri sam(-a)!

Zapišimo funkcijo Oklepaji skupaj s pomožno funkcijo SeUjema in kodo za preverjanje v datoteko oklepaji.py:

import sklad as sk # Vrne True, če so oklepaji v podanem nizu # zaključeni in pravilno gnezdeni. # Sicer vrne False. def Oklepaji(niz): sklad = sk.Ustvari() for znakIzNiza in niz: if (znakIzNiza == '(' or znakIzNiza == '[' or znakIzNiza == '{'): # predklepaj sk.Dodaj(sklad, znakIzNiza) elif (znakIzNiza == ')' or znakIzNiza == ']' or znakIzNiza == '}'): # zaklepaj if sk.JePrazen(sklad): # sklad se je prezgodaj izpraznil return False znakSSklada = sk.Odvzemi(sklad) if not SeUjema(znakSSklada, znakIzNiza): return False return sk.JePrazen(sklad) # Vrne True, če se podani predklepaj ujema # s podanim zaklepajem; sicer vrne False. def SeUjema(predklepaj, zaklepaj): return (predklepaj == '(' and zaklepaj == ')' or predklepaj == '[' and zaklepaj == ']' or predklepaj == '{' and zaklepaj == '}') # Preverimo delovanje funkcije. print(Oklepaji('(((')) print(Oklepaji(')))')) print(Oklepaji('[(){[]}]')) print(Oklepaji('[(){[}]]'))

Izvedi Počisti