Stek — "ən son qoyulan ən əvvəl çıxır" şərti olan hər yerdə təbii alətdir. Bu dərsdə beş klassik tətbiqə baxırıq: mötərizələr, RPN, undo/redo, DFS və monoton stek. Stekin özü əvvəlki dərsdə yazılıb: stek reallaşdırması; burada adi list kifayətdir.

Mötərizələrin yoxlanması
Mötərizələrin yoxlanması

Mötərizələrin yoxlanması

Açan mötərizəni stekə qoyuruq. Bağlayan gələndə stekdən götürüb cütlüyü yoxlayırıq. Üç səhv halı: cüt uyğun gəlmir, bağlayan boş steklə rastlaşır, sonda açan qalır. Sətir yalnız bunların heç biri baş verməsə və stek boş qalsa düzgündür. Vaxt O(n), yaddaş O(n).

python
PAIRS = {")": "(", "]": "[", "}": "{"}

def balanced(s):
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in PAIRS:
            if not stack or stack.pop() != PAIRS[ch]:
                return False
    return not stack

for s in ["{[()]}", "([)]", "((", ")("]:
    print(s, balanced(s))
text
{[()]} True
([)] False
(( False
)( False

Postfix ifadə (RPN)