LAPORAN PRAKTIKUMALGORITMA PEMROGRAMAN & STRUKTUR DATA

MODUL VIII

DISUSUN OLEHNAMA : DEVINIM : 2012081043KELAS : TI2012A

LABORATORIUM KOMPUTERFAKULTAS ILMU KOMPUTERUNIVERSITAS KUNINGAN

2012

I. PEMBAHASAN

A. Dasar Teori

Stack merupakan bagian dari struktur data yang dikategorikan ke dalam

bentuk linear data, dimana operasi pemasukan maupun pengeluaran data selalu

dilakukan pada salah satu sisinya[1]. Dalam dunia komputer, penggunaan stack

(tumpukan) merupakan suatu hal yang umum digunakan seperti untuk penentuan

alamat memory, penempatan ruang data dan aplikasi lain. Sebagai bagian dari

struktur data, aplikasi stack juga digunakan untuk berbagai macam keperluan

seperti pengujian kalimat palindrome, penguji tanda kurung (matching

parentheses), dan juga berfungsi sebagai konversi dari notasi infix menjadi notasi

postfix.

Pada perhitungan aritmatika, notasi infix adalah notasi yang menempatkan

operator ditengah dua operand sedangkan notasi Postfix adalah notasi yang

menempatkan operator setelah dua operand. Penggunaan notasi infix merupakan

hal yang lumrah digunakan dalam perhitungan aritmatika dibandingkan dengan

penggunaan notasi Postfix, akan tetapi bagi mesin kompilasi notasi Postfix

merupakan notasi yang digunakan untuk melakukan suatu perhitungan.

Tulisan ini dibuat untuk memberikan gambaran secara jelas proses simulasi

konversi atas dua notasi aritmatika tersebut, berdasarkan studi literatur dari

beberapa buku dan dituangkan dengan bantuan bahasa pemrograman Pascal.

Adapun proses konversi ini ditujukan untuk menjelaskan bagaimana mesin

kompilasi dapat merubah notasi infix yang biasa digunakan oleh berbagai

kalangan menjadi notasi Postfix yang dimengerti oleh mesin kompilasi sehingga

suatu proses perhitungan aritmatika dapat dilaksanakan oleh komputer.

1. Definisi

Dalam dunia komputer, penggunaan stack atau tumpukan merupakan salah

satu komponen penting untuk menjamin proses penanganan suatu data disamping

hal lain seperti Queue (antrian), linked list, dan tree.

Definisi 1

Stack adalah suatu koleksi atau kumpulan item data yang teroganisasi dalam

bentuk urutan linear, yang operasi pemasukan dan penghapusan datanya

dilakukan pada salah satu sisinya[1]

Definisi 2

Diberikan suatu himpunan yang terurut himpunan sebagai S = {S1, S2, ...,

ST}, T pada anggota S merupakan linear order, sehingga stack dari himpunan

tersebut memiliki informasi sebagai berikut [1] :

1. Elemen puncak dari stack dalam himpunan S dikatakan sebagai TOP, sehingga:

TOP[S} = ST ............................................................................(1)

2. Banyaknya elemen stack dalam himpunan S dikatakan sebagai NOEL, sehingga

NOEL = T, dimana himpunan dari S tersebut dapat disusun sebagai :

S = {S1, S2, ..., SNOEL} .............................(2)

Dari dua definisi tersebut di atas maka suatu stack dapat digambarkan sebagai

berikut :

1. Suatu stack dalam keadaan kosong akan memiliki informasi NOEL(S) = 0 dan

TOP(S)= undefined.

   

S

2. Untuk stack yang bukan kosong, maka akan memiliki informasi seperti yang

digambarkan di bawah ini dimana informasi yang ada adalah NOEL(S) = 1 dan

TOP(S) = Merah

 

     

S

Untuk stack yang berisi lebih dari n jumlah data maka informasi yang ada pada

stack tersebut berisikan NOEL(S) = 2 (jika berisi 2 data) dan TOP(S) = Biru

seperti ditunjukan pada gambar di bawah ini :

      

S

Elemen-elemen yang berada dalam stack tersebut di atas, memiliki prinsip

dasar dalam pengoperasiannya yaitu prinsip LIFO (Last In First Out) atau yang

masuk paling belakang akan memiliki prioritas untuk keluar paling depan.

Suatu stack dapat digambarkan sebagai suatu array (larik) berdimensi satu

yang elemen-elemennya berkisar antara 1 sampai n elemen. Dengan demikian jika

suatu stack didefinisikan dengan n elemen maka dapat dikatakan jumlah

maksimum dari stack atau NOEL(S) nya adalah n, sehingga penambahan elemen

stack yang ke n+1 tidak diperkenankan atau stack tersebut dalam kondisi

overflow. Hal tersebut juga berlaku untuk stack dengan nilai minimum yaitu

NOEL(S) dari stack dalam kondisi 0, jika dilakukan operasi pengambilan elemen

atas stack tersebut akan mengakibatkan stack tersebut dalam kondisi underflow.

Dua kondisi tersebut merupakan dasar dalam merancang suatu aplikasi

pemrograman komputer.

2. Operasi-operasi Stack

Dalam penggunaannya suatu stack memiliki beberapa operasi yang dapat

diterapkan seperti membuat stack, penambahan eleme ke dalam stack,

menghapusan elemen dari dalam stack, dan operasi lain yang berhubungan dengan

stack tersebut. Adapun operasi-operasi dasar dari suatu stack adalah :

1. Create (Stack)

Operasi Create(Stack) digunakan untuk membuat suatu stack baru dengan

nama stack, yang nilai elemen saat stack tersebut dibuat adalah NOEL(S) = 0,

TOP(S) = NULL (tidak terdefinisikan)

2. IsEmpty (Stack)

Operasi ini merupakan operasi untuk mencek isi dari suatu stack dalam

keadaan kosong atau berisi. Operasi ini memiliki 2 (dua) kondisi boolean yaitu :

a. True jika stack tersebut kosong atau dapat dikatakan NOEL(S) = 0

b. False jika stack tersebut tidak dalam kondisi kosong atau dapat dikatakan

NOEL(S) > 0

3. Push (Stack, Elemen)

Operasi ini merupakan operasi untuk menambahkan satu elemen dengan

nilai X pada puncak suatu stack, sehingga posisi TOP(S) akan bernilai X,

penerapan operasi push pasa suatu stack S akan berakibat overflow jika NOEL(S)

dari stack tersebut telah bernilai maksimum.

4. Pop (Stack)

Operasi ini berfungsi untuk menghapus satu elemen dari stack S, sehingga

posisi NOEL(S) akan berkurang satu elemen, dan TOP(S) akan berubah. Operasi

pop dapat menyebabkan kondisi underflow jika suatu stack S yang berada dalam

kondisi minimum dikenakan operasi pop.

5. IsFull

IsFull digunakan untuk mengecek apakah stack sudah penuh dengan cara

memeriksa top of stacknya,jika = 1 maka stack penuh

6. Clear

Clear digunakan untuk mengosongkan stack

 

3. Notasi Infix dan Postfix

Suatu perhitungan aritmatika biasanya berhubungan dengan operand dan

operator. Operand merupakan suatu karakter atau elemen yang nilainya

dioperasikan dengan bantuan suatu operator untuik menghasilkan suatu solusi.

Misalkan jika diberikan suatu ekspresi aritmatika 2 * 3, maka elemen ‘dua’ dan

elemen ‘tiga’ merupakan operand dari ekspresi tersebut dan elemen ‘*’

merupakan operator perkalian atas dua operand yang menghasilkan suatu solusi.

Suatu ekspresi aritmatika dapat dibedakan dalam tiga bentuk notasi perhitungan

yaitu :

1) Notasi prefix, jika operator ditempatkan sebelum dua operand

2) Notasi infix, jika operator ditempatkan diantara dua operand

3) Notasi postfix, jika operator ditempatkan setelah dua operand

Dalam penggunaannya, dalam kehidupan sehari-hari notasi infix merupakan

notasi aritmatika yang paling banyak digunakan untuk mengekspresikan suatu

perhitungan artimatik dibanding dengan dua notasi yang lain, akan tetapi notasi

Postfix merupakan notasi yang digunakan oleh mesin kompilasi pada komputer

dengan maksud untuk mempermudah proses pengkodean, sehingga mesin

kompilasi membutuhkan stack untuk proses translasi ekspresi tersebut.

Konversi notasi infix ke postfix

Berdasarkan teori yang diterangkan tersebut di atas, proses konversi infix menjadi

notasi Postfix dalam implementasinya membutuhkan stack pada proses

konversinya, adapun proses tersebut memiliki 3 (tiga) aturan yang digunakan,

yaitu :

Jika ditemukan simbol kurung buka “(“

Operasi push pada stack akan digunakan untuk menyimpan simbol tersebut

ke dalam stack.

Jika ditemukan simbol kurung buka “)”

Operasi pop digunakan untuk mengeluarkan operator-operator yang berada

di dalam stack.

Jika terdapat simbol operator

Jika dalam suatu untai notasi infix ditemukan simbol operator maka operasi

yang dilakukan pada stack terbagi atas :

1. Jika TOP(S) dari stack tersebut kosong atau berisi simbol “(“ maka operasi

push akan digunakan untuk memasukan operator tersebut pada posisi di

TOP(S)

2. Jika operator yang berada dipuncak stack merupakan elemen yang memiliki

tingkat yang sama atau lebih tinggi maka operasi pop digunakan untuk

mengeluarkan operator tersebut diikuti operasi push untuk menyimpan

operator hasil scanning untai.

3. Jika operator yang berada di puncak stack memiliki tingkat yang lebih

rendah dari operator yang discan, maka operator baru akan langsung

dimasukan ke dalam stack dengan operasi push.

B. Praktikum

Praktikum 1

Di bawah ini merupakan sintaks:

Menulis source kode Program C++

Melakukan Kompilasi

Pilih menu project, lalu pilih submenu compile atau denngan menekan

ALTF9. Maka akan muncul seperti gambar di bawah ini.

#include<conio.h>#include<string.h>#include<stdio.h>void main(){

char*str = "LIKU LIKU LAKI LAKI TAK LAKU LAKU";printf("%s\r\n",strrev(str));printf("%s\r\n",str);

}

Menjalankan Program

Menjalankan program dengan cara pilih menu Debug, lalu submenu Run

atau dengan cara menekan CTRL+F9. Maka akan muncul gambar seperti di

bawah ini.

Pembahasan:

Program diatas adalah program untuk membalikan kata. Header yang

digunakan dalam sintaks diatas ada yaitu stdio,string dan conio. Pada baris ke-

6 terdapat pernyataan char*str = "LIKU LIKU LAKI LAKI TAK LAKU

LAKU"; artinya adalah untuk mendefinisikan pointer yang menunjuk ke suatu

string yang bertipe character. Yang dimaksud pointer pada pernyataan diatas

adalah “str”. Didalam sintaks tersebut terdapat fungsi “strrev” yang digunakan

untuk membalikan kata yang berada pada pointer “str”, fungsi tersebut berada

pada file header string. Kode format yang digunakan adalah %s karena bertipe

char/string. Untuk menampilkan hasil outputnya digunakan funngsi printf

yang berada pada file header stdio. Karena stack bersifat LIFO (Last in First

Out) maka dapat dilihat pada hasil running diatas, dan fungsi strrev tersebut

akan membalikan kata tersebut.

Praktikum 2

Dibawah ini merupakan sintaks:

Menulis source kode Program C++

Melakukan Kompilasi

#include<stdio.h>#define N 20main( ){ int nilai [N],i,jml; printf("jmlh maksimal tumpukan (<=20)="); scanf("%d",&jml); for(i=0; i<=jml; i++) { if (i>=jml) printf("tumpukan penuh"); else { printf("data ke-%d=",i+1);scanf("%d",&nilai[i]); } } for(i=0; i<jml; i++) { printf("\ndata ke-%d=%d",i+1,nilai[i]); } return 0;}

Menjalankan Program

Pembahasan:

Program diatas adalah program untuk menampilkan Tumpukan Data yang

diinput melalui piranti masukan. Header yang digunakan adalah stdio.

Statement yang terdapat pada baris ke-2 adalah ketetapan tumpukan yang akan

dilaksanakan maksimal 20 tumpukan. Di dalam fungsi main terdapat 3

variabel yaitu, nilai [N], I dan jml yang bertipe integer. Operasi Input output

yang digunakan dalam program tersebut adalah printf dan scanf yang berada

pada file header yang telah dideklarasikan sebelumnya, yaitu stdio. Fungsi

printf adalah untuk menampilkan suatu keluaran pada layar. Fungsi scanf

digunakan untuk menginput data berupa data numerik, karakter dan string

secara terformat. Kode format adalah untuk konversi data, data pada sintaks

tersebut bertipe integer maka kode format yang digunakan untuk menginput

data tersebut adalah %d.

Sintaks diatas menggunakan struktur perulangan / looping, struktur yang

digunakan adalah for karena jumlah perulangan yang akan dikerjakan telah

diketahui yaitu perulangan sebanyak 20 kali, indeks dimulai dari 0 karena

variable nilai bertipe array. Misalkan kita menginputkan tumpukan sebanyak 3

maka kita akan mengisikan data sebanyak 3 kali, setelah kita tekan enter maka

data yang tadi kita input akan ditampilkan lagi. Dan jika kita menginputkan

data lebih dari 20 maka kita akan mengisikan data sebanyak 20 kali selebihnya

maka akan muncul statement “Tumpukan Penuh” karena batas perulangannya

adalah sebanyak 20 kali. Bisa dilihat dari output tersebut data-data yang di

inputkan menumpuk dan bersifat LIFO.

II. TUGAS

1. Buatlah program tumpukan (stack) untuk membalik kata dengan tampilan

sebagai berikut:

Masukan kata : STACK

Setelah dibalik : KCATS

Menulis source kode Program C++

Melakukan Kompilasi

Menjalankan Program

Pembahasan:

Program diatas sama seperti praktikum 1 yang telah dibahas sebelumnya,

namunprogram ini meminta user untuk menginputkan kata yang akan dibalik.

Struktur yang digunakan sama seperti praktikum 1, hanya pada tugas ini

digunakan operasi input output untuk menginput dan menampilkan kata yang

akan dibalik. I/O yang digunakan adalah scanf dan printf. Karena scanf

menginputkan data secara terformat maka menggunkan kode format %s

karena variabelnya bertipe string. Scanf hanya bisa membaca kata tanpa

adanya spasi, jika kita menginputkan data menggunakan spasi maka tidak

akan ditampilkan kata setelah spasi tersebut.

2. Buatlah program kalkulator SCIENTIFIC

Misalkan operasi : 3 + 2 * 5

Operasi diatas disebut operasi infiks, notasi infiks tersebut harus diubah lebih

dahulu menjadi notasi postfix

3 + 2 * 5 notasi postfiksnya adalah 3 2 5 * +

Menulis source kode Program C++

Melakukan Kompilasi

Menjalankan Program

Pembahasan:

Program diatas adalah program kalkulator SCIENTIFIC atau program

perhitungan sederhana. Header yang digunakan adalah stdio. Didalam fungsi

main terdapat 4 variabel yang bertipe integer. Untuk menampilkan dan

menginput data digunakan printf dan scanf yang berada pada file header stdio.

Kode format yang digunakan untuk menampilkan dan menginput data tersebut

adalah %d karena variable yang dideklarasikan berupa integer.

Suatu perhitungan aritmatika biasanya berhubungan dengan operand dan

operator. Operand merupakan suatu karakter atau elemen yang nilainya

dioperasikan dengan bantuan suatu operator untuik menghasilkan suatu solusi.

Misalkan jika diberikan suatu ekspresi aritmatika 3 + 2 * 5, maka elemen ‘3’

,elemen ‘2’ dan elemen ‘5’ merupakan operand dari ekspresi tersebut dan

elemen ‘+’ dan ‘*’ merupakan operator penjumlahan dan perkalian atas tiga

operand yang menghasilkan suatu solusi. Suatu ekspresi aritmatika dapat

dibedakan dalam tiga bentuk notasi perhitungan yaitu :

Notasi prefix, jika operator ditempatkan sebelum dua operand

Notasi infix, jika operator ditempatkan diantara dua operand

Notasi postfix, jika operator ditempatkan setelah dua operand

Dalam penggunaannya, dalam kehidupan sehari-hari notasi infix

merupakan notasi aritmatika yang paling banyak digunakan untuk

mengekspresikan suatu perhitungan artimatik dibanding dengan dua notasi

yang lain, akan tetapi notasi Postfix merupakan notasi yang digunakan oleh

mesin kompilasi pada komputer dengan maksud untuk mempermudah proses

pengkodean, sehingga mesin kompilasi membutuhkan stack untuk proses

translasi ekspresi tersebut.

III. KESIMPULAN

Dari Praktikum dan tugas praktikum diatas dapat disimpulkan Stack /

Tumpukan adalah sekumpulan data yang diletakan diatas data lain. Data-data

tersebut memiliki prinsip dasar dalam pengoperasiannya yaitu prinsip LIFO (Last

In First Out) atau yang masuk paling belakang akan memiliki prioritas untuk

keluar paling depan.

Operasi-operasi dalam Stack adalah sebagai berikut:

1. Create (Stack)

Operasi Create(Stack) digunakan untuk membuat suatu stack baru dengan

nama stack, yang nilai elemen saat stack tersebut dibuat adalah NOEL(S) = 0,

TOP(S) = NULL (tidak terdefinisikan)

2. IsEmpty (Stack)

Operasi ini merupakan operasi untuk mencek isi dari suatu stack dalam

keadaan kosong atau berisi. Operasi ini memiliki 2 (dua) kondisi boolean yaitu :

a. True jika stack tersebut kosong atau dapat dikatakan NOEL(S) = 0

b.False jika stack tersebut tidak dalam kondisi kosong atau dapat dikatakan

NOEL(S) > 0

3. Push (Stack, Elemen)

Operasi ini merupakan operasi untuk menambahkan satu elemen dengan

nilai X pada puncak suatu stack, sehingga posisi TOP(S) akan bernilai X,

penerapan operasi push pasa suatu stack S akan berakibat overflow jika NOEL(S)

dari stack tersebut telah bernilai maksimum.

4. Pop (Stack)

Operasi ini berfungsi untuk menghapus satu elemen dari stack S, sehingga

posisi NOEL(S) akan berkurang satu elemen, dan TOP(S) akan berubah. Operasi

pop dapat menyebabkan kondisi underflow jika suatu stack S yang berada dalam

kondisi minimum dikenakan operasi pop.

5. IsFull

IsFull digunakan untuk mengecek apakah stack sudah penuh dengan cara

memeriksa top of stacknya,jika = 1 maka stack penuh

6. Clear

Clear digunakan untuk mengosongkan stack

Notasi Infix dan Postfix adalah notasi atau ekspresi perhitungan aritmatika.

Ada 3 notasi perhitungan aritmatika yaitu, prefix, infix dan postfiks. Notasi infix

merupakan notasi aritmatika yang paling banyak digunakan untuk

mengekspresikan suatu perhitungan artimatik dibanding dengan dua notasi yang

lain, akan tetapi notasi Postfix merupakan notasi yang digunakan oleh mesin

kompilasi pada komputer dengan maksud untuk mempermudah proses

pengkodean, sehingga mesin kompilasi membutuhkan stack untuk proses translasi

ekspresi tersebut.

IV. Daftar Pustaka

http://boycreations.wordpress.com

Pemrograman Turbo C++, Abdul Kadir

http://mugi.or.id