Assalamualaikum
Tumpukkan
Tumpukkan (stack) bisa diartikan sebagai suatu kumpulan data yang seolah-olah ada data yang diletakkan diatas data yang lain. Dimana kita dapat menambah (menyisipkan) data dan mengambil (menghapus) data lewat ujung yang sama, yang disebut sebagai ujung atas tumpukkan (top of stack).
Jan Lukasiewicz adalah seorang ahli matematika yang mengembangkan suatu cara penulisan numeris yang disebut Notasi Polish.
Di dalam operasi aritmatika, ada 3 jenis notasi yaitu:
- Notasi Infix (menempatkan operator di antara 2 operand)
Contoh : A+B atau C-D atau E*F atau G/H
2.Notasi Prefix (menempatkan operator di depan / sebelum ke-2 operand)
Contoh : +AB atau –CD atau *EF atau /GH
3.Notasi Postfix ( menempatkan operator di belakang / setelah operand)
Contoh : AB+ atau CD- atau EF* atau GH/
Ekspresi matematika yang ditulis dalam notasi infix agar dapat dikenal oleh komputer harus diubah dengan memperhatikan
- Mengubah notasi infix menjadi postfix, kemudian mengitungnya
- Menggunakan stack sebagai penampung sementara operator dan operannya
- Notasi Infix
Salah satu pemanfaatan tumpukan adalah untuk menulis ungkapan menggunakan notasi tertentu. Dalam penulisan ungkapan khususnya ungkapan numeris, kita selalu menggunakan tanda kurung untuk mengelompokkan bagian mana yang harus dikerjakan lebih dahulu.
Contoh :
( A + B ) * ( C – D )
Suku ( A + B ) akan dikerjakan lebih dahulu, kemudian suku ( C – D ) dan terakhir mengalikan hasil yang diperoleh dari 2 suku ini
A + B * C – D
Maka B * C akan dikerjakan lebih dahulu diikuti yang lain. Dalam hal ini pemakain tanda kurung akan sangat mempengaruhi hasil akhir. Cara penulisan ungkapan sering disebut dengan “Notasi Infix” artinya operator ditulis diantara 2 operand
2. Notasi Prefix
Notasi Prefix adalah operator ditulis sebelum kedua operan yang aka disajikan.
Contoh notasi prefix dari notasi infix :
Infix Prefix
A + B + A B
A + B – C – + A B C
( A + B ) * ( C – D ) * + A B – C D
A – B / ( C * D ^E ) —
3. Postfix adalah notasi yang membentuk atas operator dengan operand, dimana operator berada dibelakang operand.
Contoh : A + B * C ( infix).
maka notasi postfix adalah ABC*+.
Pemecahannya:
A + B * C
Diketahui ada 3 operand yaitu : A,B,C dan 2 operator yaitu : +, *. proses dimulai dengan melihat dari hirarkhi operator.Contoh diatas operator yang tertinggi adalah * kemudian +.
Tanda * diapit oleh kedua operand yaitu B dan C yaitu B*C, postfix dengan menggabungkan operand B dan C menjadi BC,lalu memindahkan operator ke belakang operand C, sehingga fungsi B*C, notasi postfixnya menjadi BC*.Sehingga hasil sementara dari notasi postfix adalah A + BC*
Selanjutnya mencari postfix untuk operator yang berikutnya, yaitu +, dengan cara yang dilakukan sama seperti di atas, operator + diapit oleh 2 operand, yaitu : A dan BC* gabungkan operand tersebut,sehingga menjadi ABC*,lalu pindahkan operator + kebelakang operand ABC*.
Sehingga hasil akhir menjadi : ABC*+.
Secara sederhana, proses konversi dari infix menjadi prefix sebagai berikut:
- Ungkapan yang akan dikonversikan adalah ( A + B ) * ( C – D ).
- Dengan menggunakan tanda kurung bantuan, ungkapan diatas kita ubah menjadi: [ + A B ] * [ – C D ]
- Jika [ + A B ] kita misalkan P, dan [ – C D ] kita misalkan Q maka ungkapan di atas bisa ditulis sebagai berikut: P * Q
- Selanjutnya notasi infix dirubah menjadi prefix: * P Q
- Dengan mengembalikan P dan Q pada notasinya semula dan menghapus tanda kurung bantuan, kita peroleh notasi prefix dari persamaan ( A + B ) * ( C – D ) yaitu: * + A B – C D
Contoh :
- A + B * C
B * C = * B C ….. P
C * P = * C P ….. Q
Algoritma Infix Ke Prefix:
Langkah 0 :
– Baca ungkapan dalam notasi infix, misalnya S
– Tentukan panjang ungkapan tersebut, misalnya N
– Siapkan sebuah tumpukan kosong dan siapkan derajat masing-masing operator
Misalnya: ^ berderajat 3, * dan / berderajat 2, + dan – berderajat 1 dan (berderajat 0)
Langkah 1:
Dimulai dari I : N sampai 1, kerjakan langkah-langkah berikut :
- R = S ( I )
- Test nilai R. Jika R adalah:
– Operand : Langsung ditulis
– Kurung buka : Pop dan tulis semua isi tumpukan sampai ujung tumpukan = ‘)‘, pop juga tanda ini tetapi tidak perlu ditulis.
– Kurung tutup : Push kedalam tumpukan
– Operator : Jika tumpukan kosong, atau derajat R lebih tinggi
dibanding derajat ujung tumpukan, push operator
ke dalam tumpukan. Jika tidak pop ujung tumpukan dan tulis, kemudian ulangi perbandingan R dengan ujung tumpukan, lalu R di push.
Keterangan : Kurung tutup di dalam tumpukan dianggap mempunyai derajat yang lebih rendah dibanding R.
Langkah 2 : Jika akhir notasi infix telah tercapai dan tumpukan masih belum kosong, pop semua isi tumpukan dan tulis hasilnya.
Contoh:
- A + B * C
Proses ke- karakter dibaca isi stack karakter tercetak notasi prefix terbentuk
- C C C
- * *
- B * B BC
- + + * *BC
- A + A A*BC
- + +A*BC
- Notasi Postfix
Notasi lain yang merupakan kebalikan notasi prefix adalah “Notasi Postfix” atau lebih dikenal dengan Notasi Polish Terbalik (Reverse Polish Notation atau RPN). Dalam hal ini operator ditulis sesudah operand. Sama halnya dengan notasi prefix disini juga diperlukan tanda kurung pengelompokan
Proses notasi dari infix ke postfix adalah :
- Ungkapan yang akan dikonversikan adalah: (A+B)*(C–D)
- Dengan menggunakan tanda kurung bantuan, ungkapan diatas diubah menjadi: [A B+] *[CD-]
- Jika [AB+] kita misalkan P, dan [CD-] kita misalkan Q, maka ungkapan diatas dapat ditulis: P*Q
- Selanjutnya notasi infix dirubah menjadi postfix yaitu: PQ *
- Dengan mengembalikan P dan Q pada notasinya semula dan menghapus tanda kurung bantuan kita peroleh notasi postfix dari persamaan:
(A+B)*(C-D) yaitu AB+CD-*
Contoh notasi infix ke postfix:
Infix Postfix
Q : A + ( B * C – ( D / E ^ F ) * G ) * H
Tambahkan “(” ke stack dan tambahkan tanda “)” ke sentinel Q sehingga Q menjadi
Q : A + ( B * C – ( D / E ^ F ) * G ) * H )
sekian dari saya, semoga bermanfaat
Wassalamualaikum