KONVERSI INFLIX KE POSTFIX : matematika diskrit

KONVERSI INFLIX KE POSTFIX

Ada tiga bentuk penulisan notasi matematis di komputer, satu bentuk adalah yang umum digunakan manusia (sebagai input di komputer) yaitu infix, dan dua yang digunakan oleh komputer (sebagai proses), yaitu postfix dan infix. Berikut contoh-contohnya:

No.	Infix	Postfix	Prefix
1.	A + B	A B +	+ A B
2.	(A + B) * C	A B + C *	* + A B C
3.	A * ( B + C)	A B C + *	* A + B C

1. Konversi Infix ke Postfix

Untuk mengetahui bentuk postfix dari notasi infix, ada tiga cara yang dapat dilakukan, yaitu

(1) manual dan (2) stack. Berikut contoh notasi infixnya: A * ( B + C ) / D ^ E –F

1. Cara Manual

Caranya adalah dengan menyederhanakan notasi menjadi duaoperand (variabel) dan satu operator, seperti A + B.

Langkah 1: tentukan (berdasarkan derajat operasi) mana yang akan diproses terlebih dulu. Diperoleh ( B + C ). Jika ( B + C ) dianggap G, maka notasi infix tadi menjadi: A * G / D ^ E – F

Langkah 2: dari hasil langkah 1, disederhanakan lagi, kali ini ((berdasarkan derajat operasi) akan disederhanakan D ^ E. Bila D ^ E dianggap H, maka notasi infix tadi menjadi: A * G / H – F

Langkah 3: dari hasil langkah 2, disederhanakan lagi, kali ini ((berdasarkan derajat operasi) akan disederhanakan A * G. Bila A* G dianggap I, maka notasi infix tadi menjadi: I / H – F

Langkah 4: dari hasil langkah 3, disederhanakan lagi, kali ini ((berdasarkan derajat operasi) akan disederhanakan I / H. Bila I / H dianggap J, maka notasi infix tadi menjadi: J – F

Setelah diperoleh bentuk seperti itu, maka satu per satu kita kembalikan ke notasi semula sambil mengubahnya menjadi notasi postfix.

Langkah 5: hasil akhir J – F, dibentuk postfixnya, menjadi J F –

Langkah 6: J sebenarnya adalah I / H yang jika ditulis dalam bentukpostfix menjadi I H /,

lalu kita gabung dengan hasil di langkah 5 tadi, diperoleh: I H / F -

Langkah 7: H sebenarnya adalah D ^ E yang jika ditulis dalam bentukpostfix menjadi D E ^,

lalu kita gabung dengan hasil di langkah 6 tadi, diperoleh: I D E ^ / F –

Langkah 8: I sebenarnya adalah A * G yang jika ditulis dalam bentukpostfix menjadi A G *,

lalu kita gabung dengan hasil di langkah 7 tadi, diperoleh: A G * D E ^ / F –

Langkah 9: G sebenarnya adalah B + C yang jika ditulis dalam bentukpostfix menjadi B C +,

lalu kita gabung dengan hasil di langkah 8 tadi, diperoleh: A B C + * D E ^ / F –

Dengan demikian, untuk notasi infix: A * ( B + C ) / D ^ E – F maka notasipostfixnya

menjadi: A B C + * D E ^ / F –

Postfix tidak memerlukan tanda kurung, prosesnya berjalan sebagai berikut:

2 3 5 + * 4 2 ^ / 3 –

2 8  * 4 2 ^ / 3 –

16 4 2 ^ / 3 -

16 16 / 3 -

1 3 –

-2

Sama hasilnya pada infix:  2 * ( 3 + 5 ) / 4 ^ 2 – 3 = -2

2. Cara Stack

Stack adalah tumpukan (jadi, memori diibaratkan dengan tumpukan) yang memiliki cara kerja, “yang pertama masuk ke kotak, maka akan terakhir kali diambil kembali” atau “first in last out”, atau sebaliknya, “yang terakhir masuk ke kotak, akan diambil yang pertama kali,” atau “last in first out.”

Untuk mengubah notasi infix menjadi postfix digunakan stack untuk menyimpan operator dengan beberapa aturan sebagai berikut

Sediakan stack untuk menyimpan operator (tipe : char)

Algoritma mengubah notasi infix menjadi postfix

[1]. Baca setiap karakter notasi infix dari awal

[2]. Bila operand maka langsung dicetak

[3]. Bila tanda ‘(‘ masukkan stack

[4]. Bila tanda ‘)’ pop dan cetak semua isi stack sampai TOS = ‘(‘. Pop juga   tanda ‘(‘ ini, tetapi tidak usah dicetak

[5]. Bila operator : jika stack kosong atau derajad operator lebih tinggi dibanding derajad TOS, push operator ke dalam stack. Jika tidak, pop dan cetak; kemudian ulangi pembandingan dengan TOS. Kemudian di-push

[6]. Jika akhir notasi infix telah tercapai, dan stack masih belum kosong, pop semua isi stack dan cetak hasilnya Contoh notasi infix : ( A + B ) / (( C – D ) * E ^ F) Ilustrasi pengubahan notasi infix di atas menjadi notasi postfix secara lengkap tersaji dalam tabel sebagai berikut:

Karakter dibaca	Isi Tumpukan	Karakter tercetak	Hasil Notasi Postfix Yang Terbentuk
(	(
A	( +	A	A
+	( +
B		B	A B
)		+	A B +
/	/
(	/ (
(	/ ( (
C	/ ( (	C	A B + C
–	/ ( ( –
D	/ ( ( –	D	A B + C D
)	/ (	–	A B + C D –
*	/ ( *
E	/ ( *	E	A B + C D – E
^	/ ( * ^
F	/ ( * ^	F	A B + C D – E F
)	/ ( *	^	A B + C D – E F ^
	/ (	*	A B + C D – E F ^ *
	/
		/	A B + C D – E F ^ */

Dari ilustrasi di atas, bisa kita lihat bahwa notasi postfix dari ungkapan: ( A + B ) / (( C – D ) * E ^ F) adalah A B + C D – E F ^ */