Materi Prefix, infix, dan postfix

Definisi mengenai Prefix, infix, dan postfix

Prefix, infix, dan postfix adalah suatu cara penulisan ungkapan-ungkapan yang rumit, misalnya pemakaian tanda kurung dalam operasi matematika.

Prefix adalah metode penulisan dengan meletakkan operator di depan operand dan tanpa menuliskan tanda kurung.
Contoh pemakaian prefix adalah  +AB, – +ABC, * + AB – CD.
Infix adalah cara penulisan ungkapan dengan meletakkan operator di antara dua operand dalam hal ini pemakaian tanda kurung sangat menentukan hasil operasi.
Contoh pemakaian infix adalah A+B, A+B-C, (A+B)*(C-D).
Postfix adalah metode penulisan dengan menuliskan operator setelah operand dan tanpa menuliskan tanda kurung.

Salah satu contoh proses pengubahan infix menjadi postfix dari karakter:

( A + B ) / (( C – D ) * E ^ F)

Karakter dibaca	Isi Stack	Karakter tercetak	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 ^ * /

Stack

Stack merupakan bagian dari struktur data yang dikategorikan ke dalam bentuk linear data, dimana operasi pemasukan maupun pengeluaran data selalu dilakukan pada salah satu sisinya[1]. Dalam dunia komputer, penggunaan stack (tumpukan) merupakan suatu hal yang umum digunakan seperti untuk penentuan alamat memory, penempatan ruang data dan aplikasi lain. Sebagai bagian dari struktur data, aplikasi stack juga digunakan untuk berbagai macam keperluan seperti pengujian kalimat palindrome, penguji tanda kurung (matching parentheses), dan juga berfungsi sebagai konversi dari notasi infix menjadi notasi postfix.
Pada perhitungan aritmatika, notasi infix adalah notasi yang menempatkan operator ditengah dua operand sedangkan notasi Postfix adalah notasi yang menempatkan operator setelah dua operand. Penggunaan notasi infix merupakan hal yang lumrah digunakan dalam perhitungan aritmatika dibandingkan dengan penggunaan notasi Postfix, akan tetapi bagi mesin kompilasi notasi Postfix merupakan notasi yang digunakan untuk melakukan suatu perhitungan.
Tulisan ini dibuat untuk memberikan gambaran secara jelas proses simulasi konversi atas dua notasi aritmatika tersebut, berdasarkan studi literatur dari beberapa buku dan dituangkan dengan bantuan bahasa pemrograman Pascal. Adapun proses konversi ini ditujukan untuk menjelaskan bagaimana mesin kompilasi dapat merubah notasi infix yang biasa digunakan oleh berbagai kalangan menjadi notasi Postfix yang dimengerti oleh mesin kompilasi sehingga suatu proses perhitungan aritmatika dapat dilaksanakan oleh komputer. Alasan pemilihan bahasa pemrograman Pascal digunakan karena fleksibilitas bahasa tersebut dalam menerangkan implementasi dan aplikasi dari struktur data dalam bentuk pemrograman

Notasi Infix dan Postfix

Suatu perhitungan aritmatika biasanya berhubungan dengan operand dan operator. Operand merupakan suatu karakter atau elemen yang nilainya dioperasikan dengan bantuan suatu operator untuik menghasilkan suatu solusi.

Misalkan jika diberikan suatu ekspresi aritmatika 2 * 3, maka elemen ‘dua’ dan elemen ‘tiga’ merupakan operand dari ekspresi tersebut dan elemen ‘*’ merupakan operator perkalian atas dua operand yang menghasilkan suatu solusi. Suatu ekspresi aritmatika dapat dibedakan dalam tiga bentuk notasi perhitungan yaitu :

1) Notasi prefix, jika operator ditempatkan sebelum dua operand

2) Notasi infix, jika operator ditempatkan diantara dua operand

3) Notasi postfix, jika operator ditempatkan setelah dua operand

Dalam penggunaannya, dalam kehidupan sehari-hari notasi infix merupakan notasi aritmatika yang paling banyak digunakan untuk mengekspresikan suatu perhitungan artimatik dibanding dengan dua notasi yang lain, akan tetapi notasi Postfix merupakan notasi yang digunakan oleh mesin kompilasi pada komputer dengan maksud untuk mempermudah proses pengkodean, sehingga mesin kompilasi membutuhkan stack untuk proses translasi ekspresi tersebut.

Konversi notasi infix ke postfix

Berdasarkan teori yang diterangkan tersebut di atas, proses konversi infix menjadi notasi Postfix dalam implementasinya membutuhkan stack pada proses konversinya, adapun proses tersebut memiliki 4 (empat) aturan yang digunakan, yaitu :

• Jika ditemukan simbol kurung buka “(“

Operasi push pada stack akan digunakan untuk menyimpan simbol tersebut ke dalam stack.

• Jika ditemukan simbol kurung buka “)”

Operasi pop digunakan untuk mengeluarkan operator-operator yang berada di dalam stack.

• Jika terdapat simbol operator

Jika dalam suatu untai notasi infix ditemukan simbol operator maka operasi yang dilakukan pada stack terbagi atas :

1. Jika TOP(S) dari stack tersebut kosong atau berisi simbol “(“ maka operasi push akan digunakan untuk memasukan operator tersebut pada posisi di TOP(S)
2. Jika operator yang berada dipuncak stack merupakan elemen yang memiliki tingkat yang sama atau lebih tinggi maka operasi pop digunakan untuk mengeluarkan operator tersebut diikuti operasi push untuk menyimpan operator hasil scanning untai.
3. Jika operator yang berada di puncak stack memiliki tingkat yang lebih rendah dari operator yang discan, maka operator baru akan langsung dimasukan ke dalam stack dengan operasi push.

Adapun tingkatan operator yang dilacak menurut urutan tingkat adalah :

Tabel 1. Level Operator dalam stack

Operator	Level Operator dalam stack
**	Tertinggi
* atau /	Menengah
+ atau -	Rendah

      4. Jika ditemukan suatu operand

Nilai operand yang ada langsung dijadikan output dari notasi Postfix.

Dicontohkan dalam suatu aplikasi suatu ekspresi aritmatika dalam notasi infix sebagai berikut

((A * B) + C / D – E ** F) * G;

Ekspresi tersebut di atas, dikonversikan ke dalam bentuk notasi Postfix digambarkan sebagai berikut :

Indeks urutan ke-	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
Karakter-karakter yang akan dilacak dalam notasi infix	(	(	A	*	B	)	+	C	/	D	-	E	**	F	)	*	G	;
Operator puncak (TOP(S)	(	( (	( (	* ( (	* ( (	(	+ (	+ (	/ + (	/ + (	- (	- (	** - (	** - (		*	*
Output yg dihasilkan dalam bentuk postfix			A		B	*		C		D	/	+		F	** -		G	*

• Karakter-karakter yang akan dilacak dalam notasi infix
• Output yang dihasilkan dalam notasi Postfix

Dari contoh untai tersebut di atas, maka hasil konversi dari notasi infix menjadi notasi Postfix menghasilkan untai : A B * C D /+ E F **- G *