MATERI INFIX
v PERFIX, INFIX, DAN POSTFIX
NOTASI POSTFIX
Dalam struktur data yang banyak dipelajari, kita ketahui adanya 3 notasi operasi yang dilakukan untuk suatu operasi aritmatika, yaitu prefix, infix, dan postfix.
Sebelum kita kupas mengenai notasi di atas, perlu dipahami 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.
Dalam struktur data yang banyak dipelajari, kita ketahui adanya 3 notasi operasi yang dilakukan untuk suatu operasi aritmatika, yaitu prefix, infix, dan postfix.
Sebelum kita kupas mengenai notasi di atas, perlu dipahami 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
Ok,sekarang kita akan mencoba mengetahui operasi yang digunakan dalam perhitungan:
1. ^ (pangkat)
2. * (kali) atau / (bagi)
3. + (jumlah) atau – (kurang)
Seperti yang telah dibahas di awal, diketahui notasi pada struktur data terdiri atas 3 macam, yaitu
1. ^ (pangkat)
2. * (kali) atau / (bagi)
3. + (jumlah) atau – (kurang)
Seperti yang telah dibahas di awal, diketahui notasi pada struktur data terdiri atas 3 macam, yaitu
1. Prefix
yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada didepan operand.
2. Infix
yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada diantara operand. Notasi ini hanya dikenal oleh manusia dan selalu digunakan dalam perhitungan aritmatika.
3. Postfix
yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada dibelakang operand. Notasi ini hanya dikenal oleh processor dan dipahami dalam ALU.
Apa
yang dimaksud dengn Infix, Prefix dan Postfix?
Infix, Prefix ataupun Postfix adalah bentuk
penulisan operasi matematika, bedanya :
o
Infix - Operator
diletakkan di antara Operand
o
Prefix - Operator
diletakkan di depan Operand
o
Postfix
/
Sufix - Operator diletakkan di belakang Operand
·
Contoh
:
Mengapa
harus menggunakan Prefix dan Postfix?
Karena infix memiliki beberapa kekurangan, yaitu :
1.
Urutan pengerjaan tidak berdasarkan
letak kiri atau kanannya, tetapi berdasarkan precedence-nya
·
Contoh
:
3
+ 4 x 2
3
+ 4 x 2 , maka
urutan pengerjaan adalah 4 x 2 dahulu.
3
+
8
,baru hasilnya ditambah 3
11
Urutan precedence (dari prioritas tertinggi) adalah
sebagai berikut :
1) Pemangkatan
2) Perkalian
dan Pembagian
3) Penjumlahan
dan Pengurangan.
4) Kecuali
kalau ada tanda kurung.
2.
Menggunakan tanda kurung. Infix
bisa menggunakan tanda kurung. Tetapi tanda kurung dapat mengacak urutan
precedence.
·
Contoh
:
Tanpa
penggunaan tanda kurung :
9
– 5 – 3
9
– 5 – 3 , maka
urutan pengerjaan adalah 9 - 5 dahulu.
4
– 3
1
Bandingkan dengan
penggunaan tanda kurung berikut :
9
– ( 5 – 3 )
9
– ( 5 – 3 ) , maka urutan pengerjaan
adalah 5 – 3 dahulu.
9
– 2
7
3.
Jika suatu program akan
mengevaluasi (mencari hasil) suatu infix, maka komputer perlu men-scan
berulang-ulang mencari urutan pengerjaannya dahulu.
·
Contoh
:
7 + 4 x 2 – 6 / 3
7 + 4 x 2 – 6 / 3
Jika
kita diminta untuk menghitung soal seperti itu, maka kita tahu bahwa yang
pertama kali harus kita kerjakan adalah 4 x 2. Lalu 6 / 3 dsb, seperti
langkah-langkah berikut :
7
+ 4 x 2 – 6 / 3
7
+ 8 – 6 / 3
7
+ 8 – 2
15
– 2
13
Komputer tidak bisa membaca keseluruhan soal
sekaligus. Komputer hanya bisa men-scan soal satu per satu operand atau
operator. Sehingga untuk mengetahui mana yang harus dikerjakan duluan, komputer
harus men-scan keseluruhan soalnya dulu. Jadi langkah-langkah si komputer dalam
mengerjakan soal infix seperti berikut:
1. Cari
precedence tertinggi dengan men-scan kiri ke kanan keseluruhan soal.
2. Hitung
nilai operator dengan precedence tertinggi tersebut.
3. Ulangi
lagi dari langkah 1, sampai semua operator selesai yang dikerjakan.
Jika komputer tidak men-scan keseluruhan soal
terlebih dahulu, maka akan terjadi kesalahan pada hasilnya.
v KONVERSI
Ø Konversi Infix à Prefix
Manual
Langkah-langkahnya
adalah sebagai berikut :
1) Cari
operator yang memiliki precedence tertinggi.
2) Letakkan
operator tsb di depan operand-operandnya.
3) Ulangi
lagi.
·
Contoh:
A
+ B – C x D ^ E / F , ”D ^ E” maksudnya D pangkat E.
A
+ B – C x D ^ E / F , pangkat memiliki precedence
tertinggi
A
+ B – C x ^ D E / F , taruh ^ di depan D dan E
A
+ B – C x ^ D E / F , x (kali) dan / (bagi) memiliki
precedence sama tapi x di kiri
A
+ B – x C ^ D E / F , taruh x di belakang
A
+ B – x C ^ D E / F , dan sebagainya
A
+ B – / x C ^ D E F
A
+ B – / x C ^ D E F
+
A B – / x C ^ D E F
+
A B – / x C ^ D E F
–
+ A B / x C ^ D E F , inilah bentuk Prefix-nya.
Ø Konversi Infix à Prefix
Menggunakan Stack
Kali
ini kita menggunakan 2 Stack, yang satu untuk menampung operand (sebut saja dengan Stack
“Pre”) dan yang satunya lagi untuk menampung operator (sebut saja
dengan Stack “Opr”).
Langkah
– langkahnya adalah sebagai berikut:
1) Scan
Infix dari kanan ke kiri.
2) Jika
berupa operand, maka Push ke Stack “Pre”.
3) Jika
berupa operator, maka bandingkan operator NEW tersebut dengan TOP pada Stack
“Opr”:
a. WHILE
precedence TOP > NEW, maka POP Stack “Opr” pindahkan ke Stack “Pre”.
b. Lalu
Push NEW ke dalam Stack “Opr”.
4) Jika
berupa “)“, maka Push “)“ ke Stack “Opr”.
5) Jika
berupa “(”, maka Pop Stack “Opr” pindahkan ke stack “Pre” sampai ketemu “)“.
6) Ulangi
terus dari langkah 1 sampai seluruh Infix sudah di-scan.
7) POP
semua isi Stack “Opr”, pindahkan ke Stack “Pre”.
8) POP
semua isi Stack “Pre”, pindahkan ke Prefix.
·
Contoh
:
Yang
mirip Postfix tadi : A ^ B / ( C – D )
·
Contoh
:
A ^ B / ( C – D )
Ø Keterangan :
o
Tanda kurung “(“ dan “)”, dapat dianggap
tidak memiliki precedence, sehingga pada langkah ke-7, operator “–“ tidak
perlu dibandingkan lagi dengan “(“ dan langsung di Push ke Stack.
o
Pada langkah ke-8, tanda “)” dibaca dari
Infix, maka Stack di Pop terus sampai ketemu tanda “(“. Sehingga pada contoh di
atas operator “–“ di Pop dan dipindahkan ke Postfix.
v EVALUASI
Yang dimaksud dengan “Evaluasi” disini adalah
mencari nilai akhir dari suatu notasi. Dengan kata lain, disuruh ngitung
hasilnya.
·
Contoh
:
Berapa
hasil 3 + 4 ?
Jawab
: 7
Ø Evaluasi Postfix Manual
Langkah-langkahnya
sebagai berikut:
1) Scan
Postfix dari kiri ke kanan.
2) Jika
berupa operand, cuekin dulu aja.
3) Jika
berupa operator, ambil 2 operand sebelumnya (yang tadi sempet kita cuekin di
sebelah kiri), lakukan perhitungan, lalu simpan lagi berupa operand.
4) Begitu
seterusnya sampai ujung kanan Postfix.
·
Contoh
:
Postfix : 7 6 5 x 3
2 ^ – +
7 6
5 x 3 2 ^
– + , scan terus sampai ketemu
operator pertama.
7 6
5 x 3 2 ^
– + , hitung 6 x 5.
7
30 3
2 ^ – + , scan
lagi cari operator berikutnya.
7
30 3
2 ^ – +
, hitung 3 pangkat 2.
7
30
9
– + , scan lagi cari operator
berikutnya.
7 30
9
– + , hitung 30 – 9.
7
21
+ , scan lagi.
7
21
+ , hitung 7 + 24.
28
, selesai.
Ø Evaluasi Postfix Menggunakan Stack
Langkah-langkahnya
:
1) Scan
Postfix dari kiri ke kanan.
2) Jika
berupa Operand, masukkan ke Stack.
3) Jika
berupa Operator, Pop Stack 2 kali (ambil 2 operand), hitung hasilnya, lalu Push
lagi ke dalam Stack.
4) Ulangi
lagi sampai ujung kanan Postfix.
Ø Evaluasi Prefix Manual
Langkah-langkahnya
idem, sama kaya Postfix, tapi arah scannya dari kanan ke kiri.
·
Contoh
:
Prefix
: + 7 – x 6 5 ^ 3
2 (soalnya sama nih sama soal Postfix tadi)
+
7 – x 6 5
^ 3 2 , scan kanan ke
kiri sampai ketemu operator.
+
7 – x 6
5 ^ 3 2
, hitung 3 pangkat 2.
+
7 – x 6 5
9
, selanjutnya silahkan pelajari sendiri dulu.
+
7 – x 6 5
9
+
7 –
30 9
+
7 –
30 9
+
7 21
+
7 21
28
Ø Evaluasi Prefix Menggunakan Stack
Langkah-langkahnya
adalah sebagai berikut:
1) Scan
Postfix dari kanan ke kiri.
2) Jika
berupa Operand, masukkan ke Stack.
3) Jika
berupa Operator, Pop Stack 2 kali (ambil 2 operand), hitung hasilnya, lalu Push
lagi ke dalam Stack.
4) Ulangi
lagi sampai ujung kanan Postfix
Komentar
Posting Komentar