Aplikasi stack

Pemeriksaan tanda kurung seimbang, mekanisme undo, dan evaluasi ekspresi.

Daftar isi

Stack menjadi alat penyelesaian masalah begitu pola LIFO-nya dipasangkan dengan kebutuhan yang cocok. Topik ini menelusuri tiga aplikasi yang diurutkan dari yang paling sederhana, yaitu pemeriksaan tanda kurung seimbang, mekanisme undo, dan evaluasi ekspresi postfix. Ketiganya berbagi satu resep, yakni menunda keputusan dengan menumpuk elemen, lalu mempopnya tepat saat keputusan bisa diambil. Dua aplikasi diimplementasikan sebagai berkas utuh dan satu sebagai potongan pendek, semuanya dijalankan dengan keluaran asli.

Tanda kurung seimbang#

Pemeriksa tanda kurung seimbang membaca satu string dan menentukan apakah setiap kurung penutup memiliki pembuka yang cocok dan berada pada posisi yang benar. Aturannya cocok dengan LIFO secara persis. Kurung pembuka ditumpuk, dan setiap kurung penutup harus dipasangkan dengan pembuka yang baru saja masuk, yaitu puncak stack. Pemeriksaan menyatakan seimbang hanya bila seluruh string selesai dibaca dan stack kembali kosong.

Tiga jenis kurung menuntut pemetaan pasangan yang eksplisit, misalnya kamus yang memetakan ) ke (, ] ke [, dan } ke {. Ketika penutup ditemukan, puncak stack dipop lalu dibandingkan dengan pasangannya. Kegagalan terjadi pada dua keadaan, yaitu stack kosong saat penutup tiba (pembukanya tidak ada) atau puncaknya tidak cocok (urutannya salah). Diagram berikut mengikuti pemeriksaan string {[()]} langkah demi langkah sampai stack kosong.

Keadaan stack pada setiap karakter string {[()]}: tiga kali push, tiga kali pop, lalu kosong

python kurung_seimbang.py

"""Pemeriksa tanda kurung seimbang menggunakan stack."""

pasangan = {")": "(", "]": "[", "}": "{"}

def seimbang(s):
    tumpukan = []
    for ch in s:
        if ch in "([{":                # kurung pembuka: masuk stack
            tumpukan.append(ch)
        elif ch in pasangan:           # kurung penutup: harus cocok dengan puncak
            if not tumpukan or tumpukan.pop() != pasangan[ch]:
                return False
    return not tumpukan                # seimbang bila stack kosong di akhir

uji = ["()", "{[()]}", "(]", "([)]", "(((", ")("]
for s in uji:
    print(f"{s:8} -> {seimbang(s)}")

text Keluaran

()       -> True
{[()]}   -> True
(]       -> False
([)]     -> False
(((      -> False
)(       -> False

Keluarannya menampilkan dua kasus seimbang dan empat yang tidak. Kasus ([)] paling sering mengecoh karena jumlah kurungnya pas, padahal urutannya salah, dan stack justru mendeteksinya lewat ketidakcocokan puncak. Kasus ((( dan )( menutup dua sisi lain, yaitu pembuka yang tersisa dan penutup tanpa pembuka. Soal Valid Parentheses meminta implementasi yang sama dengan pemeriksaan cocok sebagai intinya.

Versi Java di bawah memakai java.util.ArrayDeque sebagai stack, setelah implementasi dari nol selesai dibangun pada topik stack. Metode push, pop, dan isEmpty tersedia tanpa perlu menulis indeks puncak sendiri.

java KurungSeimbang.java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

public class KurungSeimbang {
    public static boolean seimbang(String s) {
        Map<Character, Character> pasangan = Map.of(')', '(', ']', '[', '}', '{');
        Deque<Character> tumpukan = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                tumpukan.push(ch);                 // pembuka: masuk stack
            } else if (pasangan.containsKey(ch)) { // penutup: harus cocok
                if (tumpukan.isEmpty() || !tumpukan.pop().equals(pasangan.get(ch))) {
                    return false;
                }
            }
        }
        return tumpukan.isEmpty();
    }

    public static void main(String[] args) {
        String[] uji = {"()", "{[()]}", "(]", "([)]"};
        for (String s : uji) {
            System.out.println(s + " -> " + seimbang(s));
        }
    }
}

text Keluaran

() -> true
{[()]} -> true
(] -> false
([)] -> false

Mekanisme undo#

Fitur undo pada pengolah teks dan aplikasi gambar bekerja persis seperti stack. Setiap aksi yang dilakukan menyimpan keadaan lama ke dalam stack, dan tombol undo hanya melakukan satu pop, yaitu mengembalikan keadaan terakhir yang tersimpan dengan biaya $O(1)$ . Aksi paling baru memang biasanya yang paling dulu dibatalkan, sehingga urutan LIFO mengikuti cara pakai yang alami. Potongan berikut memeragakannya pada teks tiga huruf.

python Contoh: undo dengan stack keadaan lama

aksi = []          # stack keadaan lama sebelum diganti
teks = ""

def jalankan(teks_baru):
    global teks
    aksi.append(teks)      # simpan keadaan lama terlebih dahulu
    teks = teks_baru

jalankan("k")
jalankan("ka")
jalankan("kat")
print("teks sekarang :", teks)

teks = aksi.pop()          # undo: kembalikan keadaan terakhir
print("setelah undo  :", teks)
teks = aksi.pop()
print("undo lagi     :", teks)

text Keluaran

teks sekarang : kat
setelah undo  : ka
undo lagi     : k

Setiap pemanggilan jalankan menumpuk keadaan teks sebelum perubahan, dan dua pop mengembalikan isi teks dua langkah ke belakang. Aplikasi nyata menyimpan keadaan yang lebih kaya, misalnya posisi kursor dan atribut format, tetapi strukturnya tetap stack. Kedalaman undo pun kerap dibatasi secara eksplisit, karena stack yang terus tumbuh pada akhirnya menghabiskan memori. Tombol redo lahir dari stack kedua, yaitu keadaan yang dibatalkan undo dipindahkan ke sana alih-alih dibuang, lalu diambil kembali dengan satu pop.

Evaluasi ekspresi postfix#

Postfix (notasi yang menaruh operator setelah kedua operandnya, seperti 3 4 +) disebut juga Reverse Polish notation, dan bentuk ini menghilangkan kebutuhan tanda kurung sama sekali. Urutan penulisannya sudah memuat semua informasi prioritas, sehingga evaluator cukup membaca dari kiri ke kanan satu kali. Angka ditumpuk, dan setiap operator mengambil dua nilai teratas, menghitungnya, lalu menaruh hasilnya kembali. Hasil akhirnya tersisa sebagai satu-satunya nilai di stack.

Arah pengambilan operand menuntut ketelitian. Operand kanan keluar lebih dulu karena masuk lebih akhir, sedangkan operand kiri keluar berikutnya, dan urutan ini menentukan hasil pada operator yang tidak komutatif seperti pengurangan dan pembagian. Ekspresi 10 2 - menghasilkan 8 dan bukan -8 justru karena 10 masuk lebih dulu sehingga berada di bawah 2. Berkas berikut mengimplementasikan evaluator lengkapnya.

python evaluasi_postfix.py

"""Evaluasi ekspresi postfix (Reverse Polish notation) dengan stack."""

def evaluasi(token):
    tumpukan = []
    for t in token:
        if t in "+-*/":               # operator: pop dua operand teratas
            b = tumpukan.pop()        # operand kanan keluar lebih dulu
            a = tumpukan.pop()
            if t == "+":
                tumpukan.append(a + b)
            elif t == "-":
                tumpukan.append(a - b)
            elif t == "*":
                tumpukan.append(a * b)
            else:
                tumpukan.append(a // b)
        else:                         # angka: langsung masuk stack
            tumpukan.append(int(t))
    return tumpukan[0]

print("4 13 5 / + =", evaluasi(["4", "13", "5", "/", "+"]))
print("2 3 4 * +  =", evaluasi(["2", "3", "4", "*", "+"]))
print("10 2 -     =", evaluasi(["10", "2", "-"]))

text Keluaran

4 13 5 / + = 6
2 3 4 * +  = 14
10 2 -     = 8

Ekspresi pertama menghitung 13 / 5 terlebih dahulu menjadi 2 dengan pembagian bulat, lalu 4 + 2 menghasilkan 6. Evaluator membaca masukan sekali dan setiap token memicu paling sedikit satu push atau pop, sehingga biaya totalnya $O(n)$ untuk $n$ token. Struktur yang sama dipakai mesin virtual berbasis stack untuk menjalankan bytecode, sehingga pola ini bukan sekadar soal latihan. Soal Evaluate Reverse Polish Notation meminta evaluator yang sama beserta penanganan nilai negatifnya.

Biaya setiap aplikasi#

Aplikasi	Waktu	Ruang	Operasi kunci
Tanda kurung seimbang	$O(n)$	$O(n)$	push pembuka, pop penutup
Undo	$O(1)$ per aksi	$O(k)$ untuk kedalaman $k$	push keadaan, pop undo
Evaluasi postfix	$O(n)$	$O(n)$	push angka, pop dua operand

Ketiganya membaca masukan sekali dan menjaga stack agar tidak pernah lebih panjang dari masukannya. Kompleksitas $O(n)$ berarti pemeriksaan berkas kode berisi satu juta karakter tetap selesai dalam satu lintasan. Biaya ruang terburuknya juga $O(n)$ , terjadi ketika seluruh masukan berupa pembuka atau angka yang menumpuk tanpa pernah dipop.

Kesalahan umum#

Pop tanpa memeriksa stack kosong. String yang diawali penutup seperti )( membuat pop berjalan saat stack kosong dan memunculkan IndexError. Periksa kekosongan sebelum pop, lalu laporkan sebagai tidak seimbang.
Menukar urutan operand pada evaluator. Nilai a dan b yang terbalik tetap lolos pada penjumlahan, tetapi salah pada pengurangan dan pembagian. Operand kanan wajib dipop lebih dulu.
Menghitung jumlah kurung tanpa stack. String ([)] memiliki jumlah yang seimbang tetapi urutannya salah, dan hitungan saja tidak akan menangkapnya. Perbandingan puncak stack-lah yang mendeteksinya.
Membiarkan stack berisi sisa di akhir. String ((( lolos dari setiap pemeriksaan per karakter, tetapi stack tidak kosong saat pembacaan selesai. Hasil akhir tetap harus dikondisikan pada stack kosong.

Ringkasan#

Pemeriksa kurung seimbang menumpuk pembuka, mempop penutup, dan menyatakan seimbang hanya bila stack kosong di akhir.
Undo menyimpan keadaan lama ke stack dan membatalkan dengan satu pop, sedangkan redo memakai stack kedua.
Evaluator postfix menumpuk angka dan mempop dua operand per operator, sehingga ekspresi dinilai dalam $O(n)$ tanpa tanda kurung.

Referensi#

Stack (abstract data type) — Wikipedia — membahas aplikasi stack, termasuk pemeriksaan kurung dan evaluasi ekspresi.
Algorithms, 4th Edition — Princeton University — materi stack Princeton yang memuat aplikasi evaluator ekspresi.
VisuAlgo — visualisasi interaktif operasi stack untuk menelusuri langkah pemeriksaan kurung.