Program Stack Metode Notasi Polish

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. Operand adalah data atau nilai yang membantu dalam proses sedangkan operator adalah fungsi yang digunakan dalam proses.

Contoh :

A + B * C

2 + 3 * 5

Keterangan : A, B, C, 2, 3, 5 adalah operand

+, * adalah operator

Nah… sekarang mudah-mudahan sudah dapat diketahui indikator yang membentuk suatu notasi. Selanjutnya kita harus mengetahui level/hirarkhi dari operator seperti

1. ^ (pangkat)

2. * (kali) atau / (bagi)

3. + (jumlah) atau – (kurang)

Seperti yang telah dibahas di awal, diketahui notasi pada struktur data terdiri atas 3 macam, yaitu

1. Prefix

yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada didepan operand.

Contoh : A + B * C (Infix)

maka notasi prefixnya adalah +A*BC

Pemecahannya :

A + B * C

diketahaui 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 dua operand yaitu B dan C yaitu B * C , prefixnya dengan menggabungkan operand dan memindahkan operator kedepan dari operand, sehingga fungsi B * C, notasi prefixnya menjadi *BC. Sehingga hasil sementara dari notasi prefix adalah

A + *BC

selanjutnya mencari prefix untuk operator yang berikutnya, yaitu +, cara yang dilakukan sama seperti di atas, operator +, diapit oleh 2 operand, yaitu A dan *BC, gabungkan operand, sehingga menjadi A*BC, lalu pindahkan operator kedepan operand, sehingga hasil akhir menjadi

+ A * B C

Contoh yang lain:

1. A + B – C * D

2 3 1 —–> hirarkhi level

A + B – *CD —–> 1

+AB – *CD —–> 2

– +AB *CD —–> 3

2. A * B ^ C – D

2 1 3 —–> hirarkhi

A * ^BC – D —–> 1

*A^BC – D —–> 2

-*A^BCD —–> 3

3. A + ( B – C ) * D

3 1 2 —–> hirarkhi

A + -BC * D —–> 1 (karena diapit tanda paranthesis atau kurung buka/tutup,( ) )

A + *-BCD —–> 2

+ A *-BCD —–> 3

2. Infix

yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada diantara operand. Notasi ini hanya dikenal oleh manusia dan selalu digunakan dalam perhitungan aritmatika.

Contoh : A + B * C

( A + B ) * C

A – ( B + C ) * D ^ E

3. Postfix

yaitu notasi yang terbentuk atas operator dengan operand, dimana operator berada dibelakang operand. Notasi ini hanya dikenal oleh processor dan dipahami dalam ALU.

Contoh : A + B * C (Infix)

maka notasi postfixnya adalah ABC*+

Pemecahannya :

A + B * C

diketahaui 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 dua operand yaitu B dan C yaitu B * C , postfixnya 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 +, 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 + ke belakang operand ABC*, sehingga hasil akhir menjadi

ABC*+

Contoh yang lain:

1. A + B – C * D

2 3 1 —–> hirarkhi level

A + B – CD* —–> 1

AB+ – *CD —–> 2

AB+*CD- —–> 3

2. A * B ^ C – D

2 1 3 —–> hirarkhi

A * BC^ – D —–> 1

ABC^* – D —–> 2

ABC^*D- —–> 3

3. A + ( B – C ) * D

3 1 2 —–> hirarkhi

A + BC- * D —–> 1 (karena diapit tanda paranthesis atau kurung buka/tutup,( ) )

A + BC-D* —–> 2

A BC-D*+ —–> 3

Jika ingin menguasai cara pembentukkan notasi ini caranya adalah dengan BANYAK LATIHAN KASUS.

1. A * ( B + C ) / ( D – E ), Notasi Postfix dan Prefix?

2. ABC+*DE-/, Notasi Infix dan Prefix?

3. 223+*32-, berapakah hasilnya

Contoh Program Infix ke Postfix

[sourcecode language=”pascal”]
Program KONVERSI_INFIX_KE_POSTFIX;
const Max_Elemen = 255;
type isi = string[Max_Elemen];
stack = record
hasl : isi;
top : 0..Max_Elemen
end;
var Infix : isi; {* notasi infix *}
Lagi : char;
t : stack;

procedure PUSH (var t : stack; Elemen : char);
begin
t.top := t.top + 1;
t.hasl[t.top] := Elemen
end;

function POP (var t : stack) : char;
begin
POP := t.hasl[t.top];
t.top := t.top – 1
end;

procedure KONVERSI_CETAK (Infix : isi);
var
i : integer;
temp, Kar : char;
opr : set of char;

begin
opr := [‘^’]+[‘*’]+[‘/’]+[‘+’]+[‘-‘];
for i := 1 to length(Infix) do
begin
Kar := Infix[i]; {* Kurung buka. Push ke dalam tumpukan *}
if Kar = ‘(‘ then PUSH(t, Kar)
else if Kar = ‘)’ then
begin
while T.hasl[t.top] <> ‘(‘ do
write(POP(T):2);
temp := POP(T)
end
else if Kar in opr then
begin
while (t.top <> 0) and (ALIANSI(Kar) <= ALIANSI(T.hasl[t.top])) do
write(POP(T):2);
PUSH(T, Kar)
end
else if Kar <> ‘ ‘ then
write(Kar:2)
end;
if t.top <> 0 then
repeat
write(POP(T):2)
until t.top = 0;
end;
begin
writeln(‘ =======================================’);
writeln(‘| MENGUBAH NOTASI INFIX MENJADI POSTFIX |’);
writeln(‘ =======================================’);
writeln;
repeat
write(‘Masukkan ungkapan Infix : ‘);
readln(Infix); writeln;
write(‘Hasil Ungkapan postfix : ‘);
KONVERSI_CETAK(Infix);
writeln; writeln;
write(‘Akan mencoba lagi? Y/N : ‘);
readln(Lagi);
writeln
until not (Lagi in [‘Y’, ‘y’])
end.
[/sourcecode]