PROGRAM STACK METODE NOTASI POLISH

  1. Program  Stack Metode Notasi Polish
   Seorang ahli matematika “Jan Lukasiewicz“ mengembangkan satu cara penulisan ungkapan numeris yang selanjutnya disebut “Notasi Polish“ atau “Notasi Prefix” yang artinya: operator ditulis sebelum kedua operand yang akan disajikan.
   Dalam struktur data yang banyak dipelajari, kita ketahui adanya 3 notasi operasi yang dilakukan untuk suatu operasi aritmatika, yaitu prefix, infix, dan postfix.
   Sebelum kita kupas mengenai notasi di atas, perlu dipahami terlebih dahulu indikator yang membentuk terjadinya notasi dalam struktur data. Notasi terbentuk dari operand dan operator. Operandadalah data atau nilai yang membantu dalam proses sedangkan operator adalah fungsi yang digunakan dalam proses.

A.1. Notasi Prefix

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

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.

Listing Program

{  Program Name                    : Konversi.Pas

Authors                                : Oke Hendradhy

Version                                : 1.0

}

Uses crt;

const

Noelstack = 80;

Makschar = 80;

Type

Eon = char;

stack = Record

Top  : array[1…Noelstack] of Eon;

Noel : 0… Noelstack;

End;

Tipeindex = 0… makschar;

Typeeks = array[1… Noelstack] of char

Var

lagi : char;

{Bentuk-bentuk operasi stack}

Function isempty(Var s : stack):Boolean;

Begin

IsEmpty : = s. noel = 0

End;

Procedure create (var s. stack);

Begin

  1. Noel : = 0;

End;

procedure buatkosong (Var s. stack);

Begin

  1. Noel : = 0;

End ;

Procedure stack Error (tingkat Error: integer);

Begin

Case tingkat error of

1 : Writeln (isi stack sudah terlalu penuh);

2 : Writeln (isi stack kosong);

End

End;

Procedure push( var s : stack; tipebaru : Eon);

Begin

If s. Noel = Noel stack then

stack Error(1)

Else

Begin

s.Noel : = s. Noel+1 ;

s.Top[s.Noel] : = tipebaru

End

End;

Procedure pop(var s: stack ;

var nilaistack : Eon);

Begin

If s. Noel = 0 then

Stack error(2)

Else

Begin

Nilaistack : = s.top[s.Noel];

S.Noel : = s. Noel – 1;

End

End;

{proses konversi suatu ekspresi}

Function puncak stack(s : stack) : Eon;

Begin

Puncak stack : = s.top[s.noel]

End;

Function isidlmstack (operator: char); integer;

Begin

case operator of

‘(‘       : isidlmstack : = 0;

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

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

End

End;

Function stackyangdibaca (operator : char): integer

Begin

Case operator of

‘)’      : stackyangdibaca : =0;

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

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

‘(‘      : stackyangdibaca : = 5;

End

End;

Procedure simpanchar(ch:char; Var ekspost : Tipeks;Var indekspost ; Tipeindex);

Begin

Indekspost : = indeks post+1;

ekspost [indekspost]: = ch;

End;

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, ‘(‘);

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;

produce konversi ekspresi;

var

indeks panjangdlm, panjang post :tipe index;

eksdlm,ekspot      :tipe eks

begin

lagi :=’y’;

While (upcase(lagi) =’x’ do

Begin

clsscr;

panjangdlm := 0

while not eoln do

begin

panjangdlm:=panjangdlm +1;

read(eksdlm[panjangdlm])

end;

readln ;

write(‘ekspresi infix:’);

for index := 1 to panjangdlm do

write(eksdlm[index]);

writeln;

konversiinfixkePostfix(eksdlm, panjangdlm, ekspost, panjang post);

write (‘dalam bentuk Postfix’)

for indeks := 1 to panjangpost do

write (ekspost [indeks]);

writeln;

writeln;

write (‘ada data lagi<y/t>.’); readln (lagi)

end;

End;

begin

konversi ekspresi;

end.

Post Navigation

 

Leave a Reply

Your email address will not be published. Required fields are marked *