POHON (INFIX, PREFIX, POSTFIX)

INFIX, PREFIX, POSTFIX

PENDAHULUAN

Salah satu kegunaan stack adalah untuk mengubah notasi infix menjadi prefix ataupun 

postfix, ada baiknya mengenal istilah operand dan operator dahulu.

Apa yang dimaksud dengan Operand dan Operator ?

Apa yang dimaksud dengn Infix, Prefix dan Postfix?

Infix, Prefix maupun Postfix merupakan bentuk penulisan operasi matematika, perbedaannya :

Infix - Operator terletak di antara Operand

Prefix - Operator terletak di depan Operand

Postfix / Sufix - Operator terletak di belakang Operand

Contoh :

Mengapa harus menggunakan Prefix dan Postfix?

Karena infix memiliki beberapa kekurangan, yaitu :

      1. Urutan pengerjaan tidak berdasarkan letak sebelah kiri atau kanannya, tetapi berdasarkan urutan pengerjaannya

Contoh :    3 + 4 x 2

                  3 + 4 x 2          , maka urutan pengerjaan adalah 4 x 2 dahulu.

                  3 + 8                , lalu hasilnya kita tambah 3

                  11

      Urutan pengerjannya (berawal dari prioritas tertinggi dahulu) adalah sebagai berikut :

1.      - Pemangkatan

2.      - Perkalian dan Pembagian

3.      - Penjumlahan dan Pengurangan.

   - Kecuali kalau ada tanda kurung.

2. Menggunakan tanda kurung. Infix bisa menggunakan tanda kurung. Tetapi tanda kurung dapat membuat acak urutan pengerjaannya.

Contoh :    Tanpa penggunaan tanda kurung :

                  9 – 5 – 3

                  9 – 5 – 3          , maka urutan pengerjaan adalah 9 - 5 dahulu.

                  4 – 3

                  1

                  Dapat kita Bandingkan dengan menggunakan tanda kurung berikut ini :

                  9 – ( 5 – 3 )

                  9 – ( 5 – 3 )      , maka urutan pengerjaan adalah 5 – 3 dahulu.

                  9 – 2

                  7

3. misal suatu program akan mengevaluasi atau mencari hasil dari suatu infix, maka komputer perlu men-scan berulang-ulang untuk mencari urutan pengerjaannya atau precedencenya terdahulu.

Contoh :    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 agar mengetahui mana yang harus dikerjakan duluan oleh komputer, komputer harus men-scan semua isi soalnya dulu. Jadi langkah-langkah computer ini dalam menyelesaikan soal infix seperti berikut:

1.      - mencari urutan pengerjaan yang tertinggi dengan men-scan dari kiri lalu ke kanan keseluruh isi soal.

2.      - Hitung nilai operator dengan precedence tertinggi tersebut.

3.      – lalu diulangi lagi dari langkah 1, sampai semua operator atau operand selesai dikerjakan oleh komputer.

Jika komputer tidak men-scan seluruh isi soal terlebih dahulu, maka akan terjadi kesalahan pada hasil tersebut.

KONVERSI

Konversi Infix à Prefix Manual

Langkah-langkahnya:

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 à Postfix Manual

Langkah-langkahnya :

1.Cari operator yang memiliki precedence tertinggi.
2.Letakkan operator tsb di belakang operand-operandnya.

3. Ulangi terus sampai bosan, eh salah, sampai selesai.

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 belakang D dan E

      A + B – C x D E ^ / F    , x (kali) dan / (bagi) memiliki precedence sama tapi x di kiri

      A + B – C D E ^ x / F    , taruh x di belakang

      A + B – C D E ^ x / F    ,dan sebagainya

      A + B – C D E ^ x F /

      A + B – C D E ^ x F /

      A B + – C D E ^ x F /

      A B + – C D E ^ x F /

      A B + C D E ^ x F / –    , inilah bentuk Postfix-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 – langkah :

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.       a. WHILE urutan pengerjaan (precedence) TOP > NEW, maka POP Stack “Opr” dipindahkan menuju ke Stack “Pre”.

b.      b. Lalu Push NEW ke dalam Stack “Opr”.

      4. Jika berupa tanda “)“, maka Push “)“ menuju ke Stack “Opr”.

      5. Jika berupa “(”, maka Pop Stack “Opr” dipindahkan ke stack “Pre” sampai ketemu tanda “)“.

      6. diulangi terus dari langkah 1 sampai seluruh Infix sudah ter-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 )