infiks , postfiks , dan prefiks

Infiks, Postfix dan Prefix

Infiks, notasi Postfix dan Prefix tiga cara yang berbeda tetapi setara dengan menulis ekspresi. Hal ini paling mudah untuk menunjukkan perbedaan dengan melihat contoh operator yang mengambil dua operan.

Infiks notasi: X + Y

Operator ditulis di-antara operan mereka. Ini adalah cara yang biasa kita menuliskan ekspresi. Sebuah ekspresi seperti A * ( B + C ) / D biasanya diartikan sesuatu seperti: ". Pertama menambahkan B dan C bersama-sama, kemudian kalikan hasilnya dengan A, kemudian bagi dengan D untuk memberikan jawaban akhir" Infiks notasi membutuhkan informasi tambahan untuk membuat urutan evaluasi dari operator jelas: aturan dibangun ke dalam bahasa tentang operator didahulukan dan associativity, dan kurung ( ) untuk memungkinkan pengguna untuk mengesampingkan aturan-aturan ini. Misalnya, peraturan yang biasa untuk associativity mengatakan bahwa kita melakukan operasi dari kiri ke kanan, sehingga perkalian dengan A diasumsikan datang sebelum pembagian dengan D. Demikian pula, aturan yang biasa untuk didahulukan mengatakan bahwa kita melakukan perkalian dan pembagian sebelum kita melakukan penambahan dan pengurangan. (Lihat kuliah CS2121 ).

Postfix notasi (juga dikenal sebagai "notasi Polandia Reverse"): XY +

Operator ditulis setelah operan mereka. Ekspresi infiks yang diberikan di atas adalah setara dengan A B C + * D /
Urutan evaluasi operator selalu kiri ke kanan, dan kurung tidak dapat digunakan untuk mengubah urutan ini. Karena "+" ada di sebelah kiri dari "*" dalam contoh di atas, penambahan harus dilakukan sebelum perkalian.
Operator bertindak pada nilai-nilai segera di sebelah kiri mereka. Sebagai contoh, "+" di atas menggunakan "B" dan "C". Kita dapat menambahkan (sama sekali tidak perlu) kurung untuk membuat ini jelas:
( (A (BC +) *) D /)
Dengan demikian, "*" menggunakan dua nilai menjelang: "A", dan hasil penambahan. Demikian pula, "/" menggunakan hasil dari perkalian dan "D".

Awalan notasi (juga dikenal sebagai "notasi Polandia"): + XY

Operator ditulis sebelum operan mereka. Ekspresi diberikan di atas adalah setara dengan / * A + B C D
Adapun Postfix, operator dievaluasi kiri ke kanan dan kurung adalah berlebihan. Operator bekerja pada dua nilai terdekat di sebelah kanan. Aku bagi lagi ditambahkan (sama sekali tidak perlu) kurung untuk membuat ini jelas:
(/ (* A (+ BC) ) D) Meskipun Awalan "operator dievaluasi kiri ke kanan", mereka menggunakan nilai-nilai di sebelah kanan mereka, dan jika nilai-nilai ini sendiri melibatkan perhitungan maka ini perubahan perintah pada operator harus dievaluasi masuk Dalam contoh di atas, meskipun pembagian itu operator pertama di sebelah kiri, bertindak berdasarkan hasil perkalian, dan sebagainya perkalian harus terjadi sebelum divisi ini (dan juga penambahan harus terjadi sebelum perkalian).
Karena Postfix operator menggunakan nilai-nilai ke kiri mereka, nilai-nilai yang melibatkan perhitungan sudah akan telah dihitung saat kita kiri ke kanan, dan urutan evaluasi operator tidak terganggu dengan cara yang sama seperti dalam ekspresi Prefix.

Di ketiga versi, operan terjadi dalam urutan yang sama, dan hanya operator harus dipindahkan untuk menjaga makna yang benar. (Hal ini sangat penting bagi operator asimetris seperti pengurangan dan pembagian: A - B tidak berarti sama dengan B - A ; yang pertama adalah setara dengan A B - atau - A B , yang terakhir untuk B A - atau - B A ).
Contoh:

Infiks	Postfix	Awalan	Catatan
A * B + C / D	A B * C D / +	+ * A B / C D	kalikan A dan B, membagi C dengan D, menambahkan hasil
A * (B + C) / D	A B C + * D /	/ * A + B C D	tambahkan B dan C, kalikan dengan A, bagi dengan D
A * (B + C / D)	A B C D / + *	* A + B / C D	membagi C dengan D, menambahkan B, kalikan dengan A

---

Konversi antara notasi

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

Infiks	Postfix	Awalan
( (A * B) + (C / D) )	( (AB *) (CD /) +)	(+ (* AB) (/ CD) )
((A * (B + C) ) / D)	( (A (BC +) *) D /)	(/ (* A (+ BC) ) D)
(A * (B + (C / D) ) )	(A (B (CD /) +) *)	(* A (+ B (/ CD) ) )

Anda dapat mengkonversi langsung antara bentuk-bentuk tanda kurung hanya dengan menggerakkan operator dalam kurung misalnya (X + Y) atau (X Y +) atau (+ X Y) . Ulangi langkah ini untuk semua operator dalam ekspresi, dan akhirnya menghapus tanda kurung berlebihan. Anda dapat menggunakan trik serupa untuk mengkonversi ke dan dari pohon parse - setiap triplet tanda kurung dari operator dan dua operand (atau sub-ekspresi) sesuai dengan node pohon. Pohon-pohon parse sesuai adalah:

          / *
       + / \ / \
      / \ D * A +
     / \ / \ / \
    * / A + B /
   / \ / \ / \ / \
  ABCD SM CD

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