struktur data

STRUKTUR DATA PERTEMUAN 5

[email protected]

ARRAY (LARIK)STACK / TUMPUKAN

• Contoh penggunaan STACK salah satunya adalah pada program konversi aritmatik mengubah bentuk INFIX ke POSTFIX ataupun INFIX ke PREFIX.

• Bentuk ini adalah bentuk aritmatik yang digunakan oleh komputer.

• Bentuk INFIX yang ditulis dalam bahasa pemrograman, akan dikompilasi menjadi bentuk POSTFIX atau PREFIX oleh compiler.

OPERATOR


A + B * C

DERAJAT OPERATOR

OPERAND dan OPERATOR

OPERAND

PANGKAT $KALI & BAGI * /

TAMBAH & KURANG + -KURUNG BUKA & TUTUP ( )


INFIX POSTFIX PREFIX A + B AB + + AB A + B * C ABC *+ *+ ABC

• INFIX = bentuk aritmatik yang Operatornya ada diantara (di dalam) dua buah Operand.

• POSTFIX = bentuk aritmatik yang Operatornya ada sesudah dua Operand.

• PREFIX = bentuk aritmatik yang Operatornya ada sebelum dua Operand.


• Saat dikompilasi, bahasa pemrograman tidak menggunakan tanda kurung buka ataupun kurung tutup lagi.

• Urutan pelaksanaan dilakukan tergantung dari letak Operator dan Operandnya, bukan bergantung dari derajat nilai / kekuatan Operator.


1. Hanya OPERATOR yang disimpan ke Stack2. Bila isi variabelnya OPERAND, maka langsung cetak variabel3. Operator kurung buka dan kurung tutup bisa disimpan ke Stack, namun

tidak ditulis ke layar4. Bila isi variabelnya Kurung Buka ‘(‘, maka simpan (PUSH) Kurung Buka ke

Stack.5. Bila isi variabelnya OPERATOR maka periksa :

a. Bila Stack kosong, maka simpan Operator sekarang ke Stackb. Bila Stack paling atas berisi Operator selain tanda kurung, maka

bandingkan derajat di Stack dengan variabel sekarang.i. Bila lebih rendah di Stack, maka variabel langsung di-PUSHii. Bila lebih tinggi di Stack, maka Stack paling atas di-POP / dicetak,

kemudian variabel sekarang masuk/ di-PUSH.

INFIX ke POSTFIX


iii. Bila Stack paling atas isinya kurung buka ‘(’, maka variabel sekarang langsung di-PUSH/ disimpan ke Stack.

iv. Bila variabel sekarang isinya kurung tutup ‘)‘, maka cetak semua Operator di Stack hingga bertemu tanda kurung buka ‘(’.

v. Bila variabel yang ada telah habis diproses dan Stack masih berisi, maka cetak semua Operator yang ada di dalam Stack hingga Stack kosong melomponk

INFIX ke POSTFIX

STACK / TUMPUKAN

INFIX A - B + C

POSTFIX

4

3

2

1

0

A B - C +-

T.Atas := 0

T.Atas := 1

+

PANGKAT $KALI & BAGI * /TAMBAH &

KURANG + -KURUNG BUKA &

TUTUP ( )

STACK / TUMPUKAN

Contoh :Ubahlah notasi INFIX berikut ke notasi POSTFIX.

A + (B / C) KARAKTER TUMPUKAN CETAK

A A+ + A( + ( AB + ( A B/ + ( / A BC + ( / A B C) + ( / ) A B C

+ A B C /A B C / +


INFIX• A + B – C• A + B * C• (A + B) * C• A + B – C * D• A + (B - C) * D• (A + B) * (C - D)• A – B / (C * D $ E)

POSTFIX• A B + C -• A B C * +• A B + C *• A B + C D * - • A B C - D * +• A B + C D - *• A B C D E $ * / -


• (A + B * C (D - E)) / ((F + G) / H)• A B C D E - * + F G + H / /

• (A + B) / ((C - D) * E $ F) $ G - H• A B + C D – E F $ * G $ / H -

• A – B + C * (D $ E / (F - G) + H) - I• A B – C D E $ F G - / H + * + I -


DEKLARASI AWAL STACKconst MaxElemen = 255;

type StringKata = string[MaxElemen];Tumpukan = record

Isi : StringKata;Atas : 0..MaxElemen;

end;

var Infix = StringKata; {*untuk menyimpan

masukan*}


Penentuan Derajat Nilai dari Operator :

{* Fungsi untuk mengembalikan nilai derajat dari operator *}function DERAJAT(Tanda_Op : char) : integer; begin

case Tanda_Op of‘$’ : DERAJAT := 3; {* Pangkat *}‘*’ , ‘/’ : DERAJAT := 2; {* Kali & Bagi *}‘+’ , ‘-’ : DERAJAT := 1; {* Tambah & Kurang

*}‘(’ : DERAJAT := 0; {* Kurung Buka *}

endend;

INFIX ke POSTFIX


{* Prosedur PUSH *}procedure PUSH (var T : Tumpukan; Elemen = char);Begin

T.Atas := T.Atas + 1; T.Isi[T.Atas] := Elemen;end;

{* Fungsi POP -> untuk mengembalikan nilai POP *}function POP (var T : Tumpukan) : char;begin

POP := T.Isi[T.Atas];T.Atas := T.Atas - 1;end;


Prosedure INFIX ke POSTFIX :

procedure KONVERSI_POSTFIX(Infix : StringKata);var I : integer

Operator : set of char;Temp, Kar : char;T : Tumpukan;

begin{* Deklarasikan Operator yang diijinkan *}Operator := [‘$’] + [‘*’] + [‘/’] + [‘+’] + [‘-’];

for I:=1 to length(Infix) dobegin

Kar := Infix(I);

INFIX ke POSTFIX



{* Jika variabel adalah tanda ‘(’, maka PUSH ke Stack*}if Kar = ‘(’ then PUSH(T,Kar)

{* Jika variabel adalah tanda ‘)’, maka POP dan tulis *} {* semua isi Stack hingga ketemu tanda ‘(’ *}else if Kar = ‘)’ thenbegin

while T.Isi[T.Atas] <> ‘(’ do write(POP(T) : 2);Temp := POP(T)

end

INFIX ke POSTFIX


Prosedure INFIX ke POSTFIX :{*Jika variabel adalah tanda Operator selain tanda kurung} {*maka bandingkan operator di Stack dengan variabel *}

else if Kar in Operator thenbegin

while (T.Atas] <> 0) and (DERAJAT(Kar) <= DERAJAT(T.Isi[T.Atas])) do

write(POP(T) : 2);PUSH(T,Kar)

end

{*Jika Operand, maka langsung di cetak}else if Kar <> ‘ ‘ thenwrite(Kar : 2)

end; {* Akhir dari perulangan FOR *}

INFIX ke POSTFIX



{*Jika Stack masih isi, POP / cetak semua isinya *}If T.Atas <> 0 then

repeat write(POP(T) : 2)

until T.Atas = 0;

end; {* Akhir dari Procedure KONVERSI_POSTFIX *}

INFIX ke POSTFIX

Tugas 4Ubahlah notasi INFIX berikut ke notasi POSTFIX.

1. (70 * 20) / (15 * 3)2. B $ 2 – (4 * A) * C3. (A – B / C + E) / (A + B)4. W + (5 * 30 + P / (5 $ 8))

Tugas 4Contoh :Ubahlah notasi INFIX berikut ke notasi POSTFIX.

(A + B) / CKARAKTER TUMPUKAN CETAK

( (A ( A+ ( + AB ( + A B) ( + ) A B

A B +/ / A B +C / A B + C

A B + C /

• THE END OF THIS DAY• KANGGOANG Biin NAAAHHH,,,,!!!!

DEAL???DEEEAAALLLL,,,,,

struktur data

Documents