Infix, Postfix, and Prefix Expressions in Java

Halo Sobat Blodhil! Notasi Infix, Postfix, dan Prefix adalah tiga cara yang berbeda tetapi setara dalam penulisan ekspresi. Cara termudah untuk mendemonstrasikan perbedaan dengan melihat contoh operator yang menggunakan dua operan.

Notasi infiks: X + Y

Operator ditulis di antara operan mereka. Ini adalah cara biasa kami menulis ekspresi. Ekspresi seperti A * (B + C) / D biasanya diartikan seperti: "Pertama tambahkan B dan C bersama-sama, kemudian kalikan hasilnya dengan A, kemudian bagi dengan D untuk memberikan jawaban akhirnya."

Notasi infix membutuhkan informasi tambahan untuk memperjelas urutan evaluasi operator: aturan yang dibangun ke dalam bahasa tentang prioritas dan asosiatif operator, dan tanda kurung ( ) untuk memungkinkan pengguna mengganti aturan ini. Sebagai contoh, aturan umum untuk asosiatif mengatakan bahwa kita melakukan operasi dari kiri ke kanan, sehingga perkalian dengan A diasumsikan terjadi sebelum pembagian dengan D. Demikian pula, aturan umum untuk prioritas mengatakan bahwa kita melakukan perkalian dan pembagian sebelum kita melakukannya. penambahan dan pengurangan.

Notasi postfix (juga dikenal sebagai "Reverse Polish notation"): X Y +

Operator ditulis setelah operannya. Ekspresi infix yang diberikan di atas setara dengan A B C + * D /

Urutan evaluasi operator selalu dari kiri ke kanan, dan tanda kurung tidak dapat digunakan untuk mengubah urutan ini. Karena "+" berada di sebelah kiri "*" pada contoh di atas, penambahan harus dilakukan sebelum perkalian.

Operator segera bertindak berdasarkan nilai di sebelah kiri mereka. Misalnya, "+" di atas menggunakan "B" dan "C". Kita dapat menambahkan tanda kurung (sama sekali tidak perlu) untuk membuatnya eksplisit:

((A (B C +) *) D /)

Jadi, "*" menggunakan dua nilai tepat sebelum: "A", dan hasil penjumlahan. Demikian pula, "/" menggunakan hasil perkalian dan "D".

Notasi prefiks (juga dikenal sebagai "notasi Polandia"): + X Y

Operator ditulis sebelum operannya. Ekspresi yang diberikan di atas setara dengan / * A + B C D

Untuk Postfix, operator dievaluasi dari kiri ke kanan dan tanda kurung tidak berguna. Operator bertindak berdasarkan dua nilai terdekat di sebelah kanan. Saya sekali lagi menambahkan tanda kurung (sama sekali tidak perlu) untuk memperjelas ini:

(/ (* A (+ B C)) D)

Meskipun Prefix "operator dievaluasi dari kiri ke kanan", mereka menggunakan nilai di sebelah kanannya, dan jika nilai ini sendiri melibatkan komputasi maka ini mengubah urutan operator harus dievaluasi. Dalam contoh di atas, meskipun pembagiannya adalah operator pertama di sebelah kiri, bekerja berdasarkan hasil perkalian, dan perkalian harus terjadi sebelum pembagian (dan demikian pula penambahan harus terjadi sebelum perkalian).

Karena operator Postfix menggunakan nilai di sebelah kirinya, nilai apapun yang melibatkan komputasi sudah dihitung saat kita pergi dari kiri ke kanan, dan urutan evaluasi operator tidak terganggu dengan cara yang sama seperti pada ekspresi Prefix.

Di ketiga versi, operan muncul dalam urutan yang sama, dan hanya operator yang harus dipindahkan untuk menjaga artinya tetap benar. (Ini sangat penting untuk operator asimetris seperti pengurangan dan pembagian: A - B tidak berarti sama dengan B - A; yang pertama sama dengan A B - atau - A B, yang terakhir ke B A - atau - B A).

Contoh:

Metode yang paling mudah adalah memulai dengan memasukkan semua tanda kurung implisit yang menunjukkan urutan evaluasi misalnya:

Anda dapat mengonversi langsung di antara formulir tanda kurung ini hanya dengan menggerakkan operator di dalam tanda kurung, mis. (X + Y) atau (X Y +) atau (+ X Y). Ulangi langkah ini untuk semua operator dalam ekspresi, dan terakhir hapus tanda kurung yang tidak berguna.

Anda dapat menggunakan trik serupa untuk mengonversi ke dan dari pohon parse - setiap triplet tanda kurung dari operator dan dua operannya (atau sub-ekspresi) sesuai dengan simpul pohon. Pohon parse yang sesuai adalah:

Oke sobat Blodhil! Implementasi yang kita akan lakukan sekarang adalah infix to postfix!

dengan output seperti ini