A+b*c-d/e*f Infix To Prefix

Suzhoumeite

5 min read

·

Sep 02, 2024

27

Share

Mengubah Ekspresi Infix ke Prefix: a + b * c - d / e * f

Dalam matematika dan ilmu komputer, ekspresi infix adalah cara standar untuk menulis ekspresi matematika, di mana operator berada di antara operandnya. Contohnya, a + b * c - d / e * f adalah ekspresi infix.

Ekspresi prefix, di sisi lain, menempatkan operator sebelum operandnya. Untuk mengubah ekspresi infix ke prefix, kita dapat menggunakan algoritma yang disebut Shunting-Yard Algorithm, yang ditemukan oleh Edsger W. Dijkstra.

Berikut langkah-langkah untuk mengubah ekspresi infix ke prefix menggunakan algoritma Shunting-Yard:

1. Inisialisasi dua stack:
   • Operator Stack: Stack untuk menyimpan operator.
   • Output Stack: Stack untuk menyimpan ekspresi prefix yang sudah diubah.
2. Scan ekspresi infix dari kiri ke kanan:
   • Jika token adalah operand (a, b, c, d, e, f): Dorong token ke Output Stack.
   • *Jika token adalah operator (+, -, , /):
     • Jika Operator Stack kosong atau token memiliki prioritas lebih tinggi dari operator di puncak Operator Stack: Dorong token ke Operator Stack.
     • Jika token memiliki prioritas lebih rendah atau sama dengan operator di puncak Operator Stack: Pop operator dari Operator Stack dan dorong ke Output Stack sampai token memiliki prioritas lebih tinggi dari operator di puncak Operator Stack, lalu dorong token ke Operator Stack.
3. Setelah semua token dalam ekspresi infix diproses:
   • Pop semua operator yang tersisa dari Operator Stack dan dorong ke Output Stack.
4. Pop semua token dari Output Stack dan keluarkan dalam urutan terbalik.

Contoh Penerapan:

Mari kita ubah ekspresi infix a + b * c - d / e * f ke prefix.

1. Inisialisasi Stack:

   • Operator Stack: Kosong
   • Output Stack: Kosong

2. Scan Ekspresi Infix:

   • a: Dorong ke Output Stack.
   • +: Dorong ke Operator Stack.
   • b: Dorong ke Output Stack.
   • *: Dorong ke Operator Stack (prioritas lebih tinggi dari +).
   • c: Dorong ke Output Stack.
   • -: Dorong ke Operator Stack (prioritas lebih rendah dari *, pop * ke Output Stack, kemudian dorong - ke Operator Stack).
   • d: Dorong ke Output Stack.
   • /: Dorong ke Operator Stack (prioritas lebih rendah dari -, pop - ke Output Stack, kemudian dorong / ke Operator Stack).
   • e: Dorong ke Output Stack.
   • *: Dorong ke Operator Stack (prioritas lebih tinggi dari /).
   • f: Dorong ke Output Stack.

3. Pop semua operator dari Operator Stack:

   • Pop * ke Output Stack.

4. Pop semua token dari Output Stack:

   • Pop f, pop *, pop e, pop /, pop d, pop -, pop c, pop *, pop b, pop +, pop a.

Hasil Akhir:

Ekspresi prefix dari a + b * c - d / e * f adalah: - + a * b c / d * e f.

Catatan:

• Prioritas operator: * dan / memiliki prioritas lebih tinggi dari + dan -.
• Operator dengan prioritas yang sama diproses dari kiri ke kanan.

Kesimpulan:

Dengan menggunakan algoritma Shunting-Yard, kita dapat mengubah ekspresi infix ke prefix dengan mudah. Ini adalah proses penting dalam pemrosesan bahasa dan komputasi, terutama dalam konteks kalkulator dan bahasa pemrograman.