Tarkibga o'tish

To'g'ri qavslar

Kod yozayotganda kompilyator yoki muharrir biror satrda xato topib, "kutilmagan belgi" yoki "yopilmagan qavs" deya ogohlantirish berganini ko'rgan bo'lsangiz, aynan shu masala bilan tanishsiz. Oddiy matn tekshirish dasturidan tortib to SQL parser, JSON validator yoki HTML muharrirgacha — barchasi satr ichidagi qavslar to'g'ri juftlashgan-juftlashmaganini tekshiradi. Bu tekshiruv stacksiz ham qilinishi mumkin, lekin stack bu ishni nihoyatda sodda qiladi.

Masala: faqat (, ), [, ], {, } belgilardan iborat satr berilgan. Satr to'g'ri hisoblanishi uchun:

  • har ochuvchi qavs mos yopuvchi qavs bilan juftlashishi kerak;
  • qavs juftlari to'g'ri ichma-ich tartibda joylashishi kerak.
"()"         → to'g'ri
"()[]{}"     → to'g'ri
"([{}])"     → to'g'ri

"(]"         → noto'g'ri: ( va ] mos juft emas
"([)]"       → noto'g'ri: [ yopilishidan oldin ( yopilgan
"((("        → noto'g'ri: uchta ochuvchi qavs yopilmay qolgan
")"          → noto'g'ri: juft ochuvchi qavs yo'q

Nima uchun aynan stack?

Qavslarning asosiy xususiyati — ular ichma-ich joylashadi. "([{}])" satrida {} avval yopiladi, so'ng [], eng oxirida (). Oxirgi ochilgan qavs birinchi yopilishi kerak.

Bu LIFO — "oxirgi kirgan, birinchi chiqadi" tartibi bilan aynan bir xil. Stack qurish g'oyasi ham shu.

Ochuvchi qavs uchraganida uni "kutib turish" uchun bir joyga qo'yamiz. Yopuvchi qavs uchraganida esa eng so'nggi kutayotgan ochuvchi qavs shu yopuvchi bilan mos kelishi kerak. "Eng so'nggi kutayotgan" — bu stackning top elementi.

Agar faqat ochuvchi va yopuvchi qavslar sonini sansak, "([)]" kabi satrlarni to'g'ri deb hisoblab qo'yamiz: sonlar teng, lekin tartib noto'g'ri. Stack aynan tartibni nazorat qiladi.

Algoritm

Satrni chapdan o'ngga o'qiymiz:

  1. Ochuvchi qavs (, [, { uchraganda uni stackka PUSH qilamiz.
  2. Yopuvchi qavs ), ], } uchraganda:
  3. stack bo'sh bo'lsa — yopuvchi qavs uchun juft yo'q, satr noto'g'ri;
  4. stack tepasini POP qilamiz va mos juft ekanini tekshiramiz;
  5. mos kelmasa — satr noto'g'ri.
  6. Satr tugagach, stack bo'sh bo'lsa — barcha ochuvchi qavslar yopilgan, to'g'ri; bo'sh bo'lmasa — biror ochuvchi qavs javobsiz qolgan, noto'g'ri.
FUNCTION IS_VALID(s)
    stack = bo'sh stack

    FOR har bir symbol s ichida
        IF symbol ochuvchi qavs bo'lsa
            stack.PUSH(symbol)
        ELSE
            IF stack.IS_EMPTY()
                RETURN FALSE

            top = stack.POP()

            IF symbol = ')' VA top ≠ '('  THEN  RETURN FALSE
            IF symbol = ']' VA top ≠ '['  THEN  RETURN FALSE
            IF symbol = '}' VA top ≠ '{'  THEN  RETURN FALSE

    RETURN stack.IS_EMPTY()

Oxirida stack.IS_EMPTY() qaytarilishi muhim. Faqat TRUE qaytarish noto'g'ri: "(((" satrida tsikl davomida hech qanday xato topilmaydi, lekin satr noto'g'ri.

Bosqichma-bosqich dry run

"([)]" — noto'g'ri misol:

Symbol: (    → ochuvchi, PUSH    Stack: [(]
Symbol: [    → ochuvchi, PUSH    Stack: [(, []
Symbol: )    → yopuvchi
               POP → top = [
               ) juft ( bo'lishi kerak, lekin top = [
               RETURN FALSE

"([{}])" — to'g'ri misol:

Symbol: (    → PUSH    Stack: [(]
Symbol: [    → PUSH    Stack: [(, []
Symbol: {    → PUSH    Stack: [(, [, {]
Symbol: }    → POP top = {   → { juft } ✓    Stack: [(, []
Symbol: ]    → POP top = [   → [ juft ] ✓    Stack: [(]
Symbol: )    → POP top = (   → ( juft ) ✓    Stack: []

Stack bo'sh → RETURN TRUE

")(" — tartibi teskari:

Symbol: )    → yopuvchi, stack bo'sh → RETURN FALSE

Vaqt va xotira murakkabligi

Har symbol bir marta ko'riladi. Har belgida PUSH yoki POP — ikkala amal ham O(1). n ta belgili satr uchun jami O(n) vaqt.

Stack eng ko'pi bilan barcha belgilar ochuvchi qavs bo'lganda n ta element saqlaydi. Yordamchi xotira O(n).

Amal Vaqt Yordamchi xotira
Bir belgini qayta ishlash O(1) O(1)
Butun satr O(n) O(n)

O(n) dan yaxshiroq yechim mavjud emas: har symbol potensial qavs bo'lgani uchun hammasini ko'rib chiqish shart.

Edge case'lar

Bo'sh satr. For tsikli bajarmaydi, stack bo'sh qoladi. IS_EMPTY() → TRUE. Mantiqan to'g'ri: nol ta qavs, nol ta mos juft kerak.

Faqat ochuvchi qavslar. "(((" — barcha belgilar stackka qo'shiladi. Satr tugagach stack bo'sh emas → FALSE.

Faqat yopuvchi qavslar. ")))" — birinchi ) stack bo'sh paytda keladi → darhol FALSE.

Bitta belgi. "(" — tsikl tugagach stack bo'sh emas → FALSE. ")" — stack bo'sh paytda yopuvchi → FALSE.

Turlar aralashgan, sonlar teng. "([)]" — ochuvchi va yopuvchi qavslar soni teng, lekin tartib noto'g'ri. Stack top bilan solishtirishda mos kelmaydi → FALSE. Faqat sonni sanash bu xatoni topa olmaydi.

Note

"([)]" satrida ( soni 1, ) soni 1, [ soni 1, ] soni 1 — hammasi teng. Lekin satr noto'g'ri. Stack ichma-ich tartibni nazorat qiladi, hisoblagich esa tartibni bilmaydi.

Juft belgilarni saqlash usullari

Algoritm ichida yopuvchi qavs va uning mos juftini solishtirish uchun turli usul ishlatilishi mumkin.

Bir usul — qo'lda yozilgan shart ketma-ketligi (IF symbol = ')' VA top ≠ '('). Bu o'qilishi oson.

Boshqa usul — yopuvchi qavs uchraganda uning mos ochuvchisini oldindan biladigan lug'at (mapping) saqlash:

pairs = { ')' → '(', ']' → '[', '}' → '{' }

Yopuvchi qavs uchraganida pairs[symbol] ni top bilan solishtirish mumkin. Bu kodni qisqartiradi va yangi qavs turi qo'shilganda faqat lug'atni kengaytirish yetadi.

Keyingi qadamlar

To'g'ri qavslar masalasi stackning ichma-ich tuzilmalarni tekshirishdagi asosiy ishlatilishini ko'rsatadi. Xuddi shu mantiq bilan HTML yoki XML teglarini, Python bloklaridagi if/for/def tuzilmalarini yoki matematik ifodalar parsing natijasini tekshirish mumkin.

Stackning keyingi klassik masalasi — ifodalarni hisoblash. Teskari polyak yozuvida raqamlar va operatorlar shunday tartibda yozilganki, stack yordamida qavssiz va ustuvorlik qoidalarisiz hisob bajarish mumkin.