Konversi Infix ke Postfix dengan Stack: Tabel Langkah per Token

Konversi infix ke postfix memakai stack dikerjakan dengan membaca ekspresi dari kiri ke kanan: operand langsung ditulis ke output, sedangkan operator ditahan di stack sampai muncul operator lain yang presedensinya lebih rendah atau sama, atau tanda kurung tutup. Hasilnya, a + b * c menjadi a b c * + dan (a + b) * (c - d) menjadi a b + c d - *. Di bawah ini tiga ekspresi dikerjakan dalam tabel per token, lengkap dengan isi stack di setiap langkah, lalu hasilnya dievaluasi dengan angka.

#Aturan konversi infix ke postfix dengan stack

Algoritma ini sering disebut shunting-yard. Untuk setiap token, dari kiri ke kanan:

1. Operand (huruf atau angka): tulis langsung ke output.
2. Kurung buka (: push ke stack.
3. Kurung tutup ): pop semua operator ke output sampai bertemu (. Buang kedua kurung, jangan ditulis ke output.
4. Operator: selama puncak stack berisi operator dengan presedensi lebih tinggi, atau presedensi sama dan operator baru berasosiatif kiri, pop puncak itu ke output. Setelah itu push operator baru.
5. Setelah token habis: pop semua sisa stack ke output.

Aturan nomor 4 adalah tempat hampir semua kesalahan terjadi, jadi pegang tabel presedensinya:

Kurung buka di dalam stack tidak pernah di-pop oleh operator. Ia hanya dikeluarkan oleh kurung tutup pasangannya.

#Contoh 1: a + b * c

Perkalian lebih kuat dari penjumlahan, jadi * harus keluar duluan.

Hasil: a b c * +. Saat * datang, + tidak di-pop karena presedensinya lebih rendah. Itu yang membuat b * c dihitung lebih dulu.

#Contoh 2: (a + b) * (c - d)

Kurung memaksa penjumlahan dan pengurangan dihitung sebelum perkalian.

Hasil: a b + c d - *. Perhatikan baris token -: walaupun di stack ada * yang presedensinya lebih tinggi, * itu terhalang (, jadi tidak ikut di-pop. Postfix tidak punya tanda kurung sama sekali, karena urutan penulisannya sudah membawa informasi itu.

#Contoh 3: a / b ^ c - d dan asosiativitas kanan pangkat

Ekspresi ini memakai tiga tingkat presedensi sekaligus.

Hasil: a b c ^ / d -, yang setara dengan $\left(a/b^c\right)-d$.

Sekarang bandingkan dua ekspresi yang bentuknya mirip:

• a - b - c menghasilkan a b - c -. Saat - kedua datang, - pertama di puncak punya presedensi sama dan berasosiatif kiri, jadi di-pop dulu.
• a ^ b ^ c menghasilkan a b c ^ ^. Saat ^ kedua datang, ^ pertama tidak di-pop karena pangkat berasosiatif kanan. Keduanya baru keluar di akhir.

Bedanya nyata. Dengan $a=2$, $b=3$, $c=2$, bentuk yang benar $2^{\left(3^2\right)}=2^9=512$, sedangkan kalau kamu salah memperlakukan pangkat sebagai asosiatif kiri, hasilnya $(2^3{)}^2=64$.

#Bagaimana mengevaluasi postfix dengan angka?

Evaluasi postfix juga memakai stack, tapi kali ini yang disimpan adalah angka. Operand di-push. Saat bertemu operator, pop dua angka teratas, hitung, lalu push hasilnya. Satu-satunya hal yang harus diingat: angka yang di-pop pertama adalah operand kanan.

Evaluasi a b c ^ / d - dengan $a=64$, $b=2$, $c=3$, $d=5$:

Hasil akhirnya 3. Cek dengan infix aslinya: $64/2^3-5=64/8-5=3$. Cocok.

Evaluasi a b + c d - * dengan $a=3$, $b=5$, $c=7$, $d=2$: push 3 dan 5, + menghasilkan 8. Push 7 dan 2, - menghasilkan $7-2=5$. Stack sekarang berisi 8 dan 5, lalu * menghasilkan 40. Cek: $(3+5)\times (7-2)=40$.

Kalau tugasmu meminta program, kode Python berikut melakukan konversi dan bisa dipakai untuk mengecek jawaban tabelmu:

PREC = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}

def infix_ke_postfix(ekspresi):
    stack, output = [], []
    for t in ekspresi.replace(' ', ''):
        if t.isalnum():
            output.append(t)
        elif t == '(':
            stack.append(t)
        elif t == ')':
            while stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()                      # buang '('
        else:
            while (stack and stack[-1] != '(' and
                   (PREC[stack[-1]] > PREC[t] or
                    (PREC[stack[-1]] == PREC[t] and t != '^'))):
                output.append(stack.pop())
            stack.append(t)
    while stack:
        output.append(stack.pop())
    return ' '.join(output)

print(infix_ke_postfix('a/b^c-d'))   # a b c ^ / d -

Setiap token di-push dan di-pop paling banyak sekali, jadi konversinya berjalan dalam waktu linear terhadap panjang ekspresi. Cara menghitung kompleksitas seperti ini dibahas di cara menghitung Big O dari kode.

#Kesalahan yang sering terjadi di soal infix ke postfix

• Membalik operand saat evaluasi. Untuk 8 5 -, pop pertama adalah 5 dan pop kedua adalah 8. Hasilnya $8-5=3$, bukan $5-8=-3$. Kesalahan yang sama terjadi pada / dan ^.
• Mem-pop operator dengan presedensi sama untuk pangkat. a ^ b ^ c ditulis a b ^ c ^ oleh banyak mahasiswa. Itu jawaban untuk $(a^b{)}^c$, bukan untuk ekspresi aslinya.
• Tidak mem-pop operator dengan presedensi sama untuk + - atau * /. a - b + c harus menjadi a b - c +, bukan a b c + -. Yang kedua berarti $a-(b+c)$.
• Menulis kurung ke output. Postfix tidak pernah memuat ( atau ).
• Membiarkan operator di bawah ( ikut di-pop. Operator di bawah kurung buka baru boleh keluar setelah kurung itu ditutup.
• Lupa mengosongkan stack di akhir. Kalau baris "akhir" tidak ada di tabelmu, operator terakhir biasanya hilang dari jawaban.

#Kapan pakai stack dan kapan pakai queue?

Konversi ini memakai stack karena operator yang terakhir masuk harus keluar pertama (LIFO). Pada a / b ^ c, operator ^ masuk setelah / tapi harus dihitung lebih dulu. Hanya stack yang memberi urutan terbalik seperti itu.

Queue (FIFO) dipakai saat urutan kedatangan harus dipertahankan. Di algoritma shunting-yard, output sebenarnya bersifat seperti queue: token ditulis di belakang dan dibaca dari depan saat evaluasi. Contoh lain yang wajar memakai queue adalah antrean cetak, penjadwalan proses round robin, dan penelusuran pohon level demi level. Sebaliknya, fitur undo, pengecekan pasangan kurung, dan call stack pada fungsi rekursif adalah contoh stack. Call stack itu bisa kamu lihat bekerja di tracing rekursi Python.

#FAQ

#Apa hubungan postfix dengan pohon ekspresi?

Postfix adalah hasil traversal postorder dari pohon ekspresi, sedangkan prefix adalah hasil preorder. Pohon untuk (a + b) * (c - d) punya akar *, anak kiri +, dan anak kanan -. Penjelasan lengkapnya ada di traversal pohon biner preorder, inorder, postorder.

#Bagaimana cara mengubah infix ke prefix?

Cara yang paling aman: balik urutan ekspresi infix, tukar ( dengan ), lakukan konversi ke postfix, lalu balik lagi hasilnya. Untuk a + b * c, prefixnya + a * b c. Hati-hati, saat ekspresi dibalik, aturan asosiativitas ikut terbalik, jadi operator dengan presedensi sama diperlakukan berbeda dari konversi postfix biasa.

#Kenapa komputer memakai postfix?

Postfix bisa dievaluasi dalam satu kali baca dari kiri ke kanan tanpa perlu memeriksa presedensi atau kurung lagi. Mesin cukup punya satu stack angka.

#Bagaimana kalau ekspresinya punya angka lebih dari satu digit?

Pisahkan token dengan spasi, misalnya 12 + 3 * 45, lalu proses per kata, bukan per karakter. Kode di atas membaca per karakter, jadi untuk angka multidigit kamu perlu tokenizer sederhana, misalnya ekspresi.split() dengan syarat setiap token dipisah spasi.

#Apakah tanda minus negatif diproses sama dengan pengurangan?

Tidak. Minus unary seperti pada -a + b adalah operator dengan satu operand dan presedensi lebih tinggi. Di soal kuliah tingkat awal biasanya tidak muncul, tapi kalau muncul, banyak dosen menuliskannya dengan simbol berbeda, misalnya ~, supaya tidak tertukar.