Konversi dan Evaluasi Notasi Ekspresi Aritmatika: Infix, Prefix, dan Postfix

Konversi dan Evaluasi Notasi Ekspresi Aritmatika: Infix, Prefix, dan Postfix

Kajian komprehensif mengenai teknik representasi ekspresi matematika dalam sistem komputasi, standarisasi presedensi operator, serta algoritma parsing ekspresi menggunakan struktur data Stack.

1. Tiga Bentuk Representasi Notasi Ekspresi

Dalam ilmu komputer, ekspresi matematika dapat dituliskan dalam 3 format utama:

• Infix: Operator aritmatika berada di antara dua operan (contoh: $A + B$). Format ini intuitif bagi manusia namun membutuhkan tanda kurung dan aturan presedensi yang rumit saat dievaluasi oleh mesin kompilator.
• Prefix (Polish Notation): Operator diletakkan sebelum kedua operannya (contoh: $+ A B$). Ditemukan oleh Jan Lukasiewicz, format ini meniadakan kebutuhan tanda kurung.
• Postfix (Reverse Polish Notation / RPN): Operator diletakkan setelah kedua operannya (contoh: $A B +$). Notasi ini sangat efisien bagi mesin berbasis stack karena urutan eksekusi bersifat deterministik dari kiri ke kanan.

2. Algoritma Shunting-Yard (Konversi Infix ke Postfix)

Dirancang oleh Edsger Dijkstra, algoritma ini memanfaatkan struktur data Stack operator:

1. Baca ekspresi infix dari kiri ke kanan token demi token.
2. Jika token adalah operan, langsung masukkan ke output string postfix.
3. Jika token adalah kurung buka '(', dorong (push) ke dalam stack.
4. Jika token adalah kurung tutup ')', keluarkan (pop) elemen stack dan tambahkan ke output hingga kurung buka ditemukan.
5. Jika token adalah operator, lakukan perbandingan tingkat presedensi (precedence level) dengan operator di puncak stack sebelum melakukan push.

3. Berkas Terlampir

• Slide materi perkuliahan resmi: Infix, Prefix and Postfix Expressions.pptx yang menyajikan tabel presedensi dan visualisasi call-stack langkah demi langkah.