Infix to Postfix

# Infix to Postfix  Operasi-operasi artimatika seperti perkalian, pembagian, penjumlahan, dan pengurangan, dituliskan dalam ekspresi aritmatika. Ekpsresi aritmatika adalah kombinasi dari operand dan operator. Operator adalah simbol-simbol yang digunakan untuk menandakan suatu operasi aritmatika (operator `*` menandakan perkalian, operator `/` menandakan pembagian, operator `+` menandakan penjumlahan, dan operator `-` menandakan pengurangan). Sedangkan operand adalah nilai-nilai yang terhadapnya dilakukan operasi-operasi. Operand dapat berupa nilai langsung yang dituliskan (literal) maupun variabel. ### Notasi Infix Kita umumnya menuliskan ekpsresi aritmatika seperti berikut: B * C. Ekspresi B * C berarti kita mengalikan variabel B dengan variabel C. Penulisan ekspresi seperti ini disebut sebagai notasi **infix** karena operator dituliskan *in between* (diantara) dua operand. Kita juga dapat menuliskan ekspresi aritmatika yang terdiri dari lebih dari satu operator dalam notasi infix seperti berikut: A + B * C. Ekspresi ini dievaluasi dengan mengalikan B dengan C terlebih dahulu lalu menambahkan A dengan hasil perkalian tersebut. Penghitungan operator mana yang dievaluasi terlebih dahulu ini berdasarkan level **precedence** dari operator. Level precedence adalah level keutamaan operator. Operator * mempunyai level precedence lebih tinggi daripada operator + sehingga operasi perkalian dievaluasi terlebih dahulu dibandingkan operasi penjumlahan. Berikut adalah level precedence dari operator `*`, `/`, `+`, dan `-`: | Operator | Level Precedence | |----------|------------------| | `*`, `/` | 2 | | `+`, `-` | 1 | Perhatikan pada tabel di atas, operator `*` dan `/` mempunyai level precedence sama. Begitu juga dengan operator `+` dan `-` mempunyai level precedence sama. Jika dalam sebuah ekspresi aritmatika terdapat operator-operator dengan level precedence yang sama, maka evaluasi dilakukan berdasarkan asosiatif kiri, yang berarti operator yang berada di sebelah kiri yang dievaluasi terlebih dahulu. Misalkan, ekspresi `A + B - C` dievaluasi dengan mengevaluasi `A + B` terlebih dahulu lalu hasilnya dikurangi dengan `C`. Kita juga dapat mendahulukan evaluasi dari suatu operator meskipun level precedence dari operator tersebut lebih rendah dibandingkan operator lainnya dengan menuliskan tanda kurung. Sebagai contoh, pada ekspresi (A + B) * C, tanda kurung pada `A + B` membuat `A + B` dievaluasi terlebih dahulu lalu hasilnya dikalikan dengan `C`. ### Notasi Postfix Selain menggunakan notasi infix, ekspresi aritmatika dapat dituliskan dalam notasi **postfix**. Disebut dengan notasi postfix, karena operator ditulis setelah (post diterjemahkan sebagai setelah) operand-operand. Notasi postfix tidak umum dijumpai dalam bahasa pemrograman atau notasi matematika umum. Namun, notasi postfix ini tidak membutuhkan level precedence atau tanda kurung untuk memperjelas urutan evaluasi. Berikut adalah contoh notasi postfix: `A B +`. Notasi postfix `A B +` adalah ekuivalen dengan notasi infix `A + B`, ekspresi ini menghitung jumlah `A` dan `B`. Contoh lain notasi postfix: `A B C + * D /`. Pada notasi postfix, urutan evaluasi selalu dari kiri ke kanan. Karena, `+` berada di sebelah kiri `*`, maka penjumlahan `B` dan `C` dilakukan terlebih dahulu, lalu hasilnya dikalikan dengan `A` Dan kemudian hasil dari perkalian dibagi dengan `D`. Ekspresi dalam notasi postfix ini ekuivalen dengan ekspres dalam notasi infix berikut: `((B + C) * A) / D` Tabel berikut memberikan contoh-contoh notasi postfix dan notasi infix yang ekuivalen: | Infix | Postfix | Keterangan | |------------------|-----------------|------------| |`A * B + C / D` | `A B * C D / +` | Kali A dan B, bagi C dan D, tambahkan kedua hasilnya | |`A * (B + C) / D` | `A B C + * D /` | Tambah B dan C, kali hasilnya dengan A, bagi hasilnya dengan D | |`A * (B + C / D)` | `A B C D / + *` | Bagi C dan D, tambah hasilnya dengan B, kali hasilnya dengan A | ### Konversi Infix ke Postfix Konversi notasi infix ke postfix dapat dilakukan menggunakan struktur Stack. Algoritma konversi infix ke postfix dapat dituliskan sebagai berikut: 1. Buat stack kosong bernama `opStack`. Buat string kosong bernama `postfix` untuk menyimpan ekspresi postfix. 2. Scan ekspresi infix karakter per karakter (sebut karakter yang discan sebagai token) dan lakukan hal-hal sesuai dengan kondisi-kondisi berikut: - **Kasus 1**: Jika token discan adalah tanda kurung buka, `(`, push ke `opStack`. - **Kasus 2**: Jika token discan adalah tanda kurung tutup, `)`, pop `opStack` sampai dengan `(` yang berada di dalam `opStack` di-pop. Konkatenasi setiap operator (kecuali tanda kurung buka `(`) yang di-pop ke string `postfix`. - **Kasus 3**: Jika token discan adalah sebuah operand, konkatenasi ke akhir string `postfix`. - **Kasus 4**: Jika token discan adalah sebuah operator, push ke `opStack`. Sebelum meng-push token ke `opStack`, selama `opStack` tidak kosong dan top dari `opStack` bukan `(` dan top dari `opStack` mempunyai level precedence lebih tinggi atau sama dengan level precedence token, pop operator-operator dalam `opStack` (sehingga top dari `opStack` adalah operator dengan level precedence lebih rendah dari token atau tanda ‘(‘). Konkatenasi setiap operator yang di-pop ke akhir string `postfix`. 3. Pop semua operator dalam `opStack` yang tersisa dan konkatenasi ke akhir string `postfix`. Tabel berikut mencontohkan penerapan algoritma di atas untuk mengkonversi notasi infix: `A+(B*C–(D/E)*G)*H` ke notasi postfix: ![](https://i.imgur.com/A4X4bUI.png)