Dalam struktur data terdapat 3 notasi operasi yang dilakukan suatu operasi aritmatika, yaitu prefix, infix, dan postfix.
Namun, sebelumnya kita harus memahami terlebih dahulu indikator yang membentuk terjadinya notasi dalam struktur data. Notasi terbentuk dari operand dan operator. Operand adalah data atau nilai yang membantu dalam proses, sedangkan operator adalah fungsi yang digunakan dalam proses.
Contoh :
A + B * C
2 + 3 * 5
Keterangan : A, B, C, 2, 3, 5 adalah operand.
+, * adalah operator
Setelah kita mengetahui indikator pembentuk suatu notasi, kita juga harus mengetahui level dari operator, seperti:
1. “^” (pangkat)
2. “*” (kali) atau “/” (bagi)
3. “+” (tambah) atau “-” (kurang)
Namun, apabila terdapat operand di dalam sebuah kurung (“(.....)”), maka pengerjaannya akan dimulai dari operand yang berada di dalam kurung tersebut.
Contoh :
(A-B)*(C+D)
Prioritas pengerjaannya adalah sebagai berikut:
1. Dalam kurung pertama : (A-B)
2. Dalam kurung kedua : (C+D)
3. Perkalian hasil pengurangan dengan hasil penjumlahan
Aturan notasi prefix, infix, dan postfix :
- Notasi prefix : Operator-Operand-Operand, + AB (disebut juga Polish Notation – PN)
- Notasi infix : Operand-Operator-Operand, A + B
- Notasi postfix : Operand-Operand-Operator, AB + (disebut juga Reveser Polish Notation – RPN)
Notasi Prefix
Notasi Prefix adalah notasi yang operatornya ditempatkan sebelum dua operand.
Contoh : A+B*C (Infix)
Maka, notasi prefixnya adalah +A*BC
Pemecahannya :
A + B * C
Diketahui ada 3 operand, yaitu : A, B, C dan 2 operator, yaitu : +, *. Proses dimulai dengan melihat dari level operator. Contoh di atas operator tertinggi adalah * kemudian +. Tanda * diapit oleh 2 operand, yaitu B dan C. Prefixnya dengan menggabungkan operand dan memindahkan operator ke depan dari operand, sehingga fungsi B * C, notasi prefixnya menjadi *BC. Hasil sementara dari notasi prefixnya adalah :
A + *BC
Selanjutnya, mencari prefix untuk operator yang berikutnya, yaitu +, cara yang dilakukan sama seperti di atas. Operator +, diapit oleh 2 operand, yaitu A dan *BC. Gabungkan operand sehingga menjadi A*BC, lalu pindahkan operator + ke depan operand, sehingga hasil akhir menjadi :
+ A * B C
Contoh lainnya :
1. A + B – C * D
A + B - * CD
+ AB - * CD
- + AB * CD
2. A * B ^ C – D
A * ^ BC – D
* A ^ BC – D
- * A ^ BCD
3. A + (B – C) * D
A + - BC * D
A + * - BCD
+ A * - BCD
Contoh konversi dari prefix ke infix :
+ / * ABCD
Pengerjaan : (Mencari operator dimulai dari operand terkanan)
Cari operator pertama : *, ambil dua operand sebelumnya, yaitu A dan B, sehingga infixnya menjadi (A * B)
Cari operator kedua : /, ambil dua operand sebelumnya (A * B) dan C, sehingga infixnya adalah ((A * B) / C)
Cari operator ketiga : +, ambil dua operand sebelumnya ((A * B) / C) dan D, sehingga infixnya adalah ((A * B) / C) + D
Contoh konversi dari prefix ke postfix :
+ / * ABCD
Pengerjaan : (Mencari operator dimulai dari operand terkanan)
Cari operator pertama : *, ambil dua operand sebelumnya, yaitu A dan B, sehingga postfixnya menjadi AB *
Cari operator kedua : /, ambil dua operand sebelumnya AB * dan C, sehingga postfixnya adalah AB * C /
Cari operator ketiga : +, ambil dua operand sebelumnya AB * C / dan D, sehingga postfixnya adalah AB * C / D +
Notasi Infix
Notasi infix adalah notasi yang operatornya ditempatkan di antara dua operand. Notasi ini telah dikenal secara umum oleh manusia dan selalu digunakan dalam perhitungan aritmatika.
Contoh : A + B * C
(A + B) * C
A – (B + C) * D ^ E
Contoh konversi dari infix ke prefix :
(A + B) – (C * D)
Pengerjaan :
Pengerjaan dalam kurung pertama : (A + B), prefixnya adalah + AB
Pengerjaan dalam kurung kedua : (C * D), prefixnya adalah * CD
Terakhir adalah operator -, + AB - * CD, prefixnya adalah - + AB * CD
Contoh konversi dari infix ke postfix :
(A + B) – (C * D)
Pengerjaan :
Pengerjaan dalam kurung pertama : (A + B), postfixnya adalah AB +
Pengerjaan dalam kurung kedua : (C * D), postfixnya adalah CD *
Terakhir adalah operator -, AB + - CD *, postfixnya adalah AB + CD * -
Notasi Postfix
Notasi postfix adalah notasi yang operatornya ditempatkan setelah dua operand.
Contoh : A+B*C (Infix)
Maka, notasi postfixnya adalah ABC*+
Pemecahannya :
A + B * C
Diketahui ada 3 operand, yaitu : A, B, C dan 2 operator, yaitu : +, *. Proses dimulai dengan melihat dari level operator. Contoh di atas operator tertinggi adalah * kemudian +. Tanda * diapit oleh 2 operand, yaitu B dan C. Postfixnya dengan menggabungkan operand B dan C menjadi BC, lalu memindahkan operator ke belakang operand C, sehingga fungsi B * C, notasi postfixnya menjadi BC*. Sehingga hasil sementara dari notasi postfix adalah :
A + BC*
Selanjutnya, mencari postfix untuk operator yang berikutnya, yaitu +, cara yang dilakukan sama seperti di atas. Operator +, diapit oleh 2 operand, yaitu A dan BC*. Gabungkan operand sehingga menjadi ABC*, lalu pindahkan operator + ke depan operand, sehingga hasil akhir menjadi :
A B C * +
Contoh lainnya :
1. A + B – C * D
A + B – CD *
AB + - CD *
AB + CD * -
2. A * B ^ C – D
A * BC ^ – D
ABC ^ * - D
ABC ^ * D -
3. A + (B – C) * D
A + BC - * D
A + BC – D *
ABC – D * +
Contoh konversi dari postfix ke infix :
ABCD * / -
Pengerjaan : (Mencari operator dimulai dari operand terkiri)
Cari operator pertama : *, ambil dua operand sebelumnya, yaitu C dan D, sehingga infixnya menjadi (C * D)
Cari operator kedua : /, ambil dua operand sebelumnya B dan (C * D), sehingga infixnya adalah (B / (C * D))
Cari operator ketiga : -, ambil dua operand sebelumnya A dan (B / (C * D)), sehingga infixnya adalah A – (B / (C * D))
Contoh konversi dari postfix ke prefix :
ABCD * / -
Pengerjaan : (Mencari operator dimulai dari operand terkiri)
Cari operator pertama : *, ambil dua operand sebelumnya, yaitu C dan D, sehingga prefixnya menjadi * CD
Cari operator kedua : /, ambil dua operand sebelumnya B dan * CD, sehingga prefixnya adalah / B * CD
Cari operator ketiga : -, ambil dua operand sebelumnya A dan / B * CD, sehingga prefixnya adalah – A / B * CD
