Stack adalah suatu urutan elemen data yang elemennya dapat diambil dan ditambah hanya pada posisi akhir (top) saja. analogi stuck dalam kehidupan sehari-hari adalah tumpukan piring dimana pada umumnya tumpukannya ditambah di atas dan jika diambil juga dari atas. Data dalam stack disimpan dengan konsep LIFO(Last In First Out).
Operasi yang umum digunakan dalan stack ada 3:
- pop() mengeluarkan elemen paling atas
- push() memasukan elemen di paling atas
- top() mereturn nilai dari elemen paling atas
Implementasi penggunaan stack pada umumnya untuk:
•Infix
evaluation
•Postfix
evaluation
•Prefix
evaluation
•Infix
to Postfix conversion
•Infix
to Prefix conversion
•Depth
First Search
Sebelum mengetahui apa itu prefix,infix dan postfix, Ada baiknya kita mengetahui apa itu operator dan operand.
Operand adalah nilai asal yang digunakan didalam proses operasi
operator adalah instruksi yang diberikan untuk mendapatkan hasil dari proses tersebut.
prefix berarti operator nya di taruh sebelum operand
infix berarti operatornya berada di tengah operand(seperti yang biasa ditulis (contoh = 5+2))
postfix berarti operatornya diratuh di akhir operand
contoh:
|
Prefix
|
Infix
|
Postfix
|
|
*
4 10
|
4
* 10
|
4
10 *
|
|
+
5 * 3 4
|
5
+ 3 * 4
|
5
3 4 * +
|
|
+
4 /
* 6 – 5 2 3
|
4
+ 6 * (5 – 2) / 3
|
4
6 5 2 – * 3 / +
|
operator bila di sajikan atau ditulis dengan prefix dan postfix kita tidak usah menuliskan "( )" untuk yang ingin dikerakan dahulu, selain itu postfix dan prefix lebih mudah dimengerti oleh komputer sehingga dapat mempersingkat run time
cara mengevaluasi notasi infix :
*dikerjakan dengan string
4 + 6 * (5 – 2) / 3
4
+ 6 * (5 – 2) / 3 cari precedence
operator terbesar yaitu( )
4
+ 6 * 3 / 3 cari precedence
operator terbesar yaitu *
4
+ 18 / 3 cari precedence
operator terbesar yaitu /
4
+ 6 cari precedence
operator terbesar yaitu +
10 (hasil)
cara mengevaluasi notasi postfix:
kerjakan dari kiri ke kanan
7 6
5 x 3
2 ^ – + , scan hingga sampai operator
7 6
5 x
3 2 ^
– + , hitung 6 x 5
7 30
3 2 ^
– + , lanjurkan scan hingga sampai operator
7 30
3 2 ^ – + , hitung 32
7 30
9 – + , lanjutkan scan hingga sampai operator
7 30 9 –
+ , hitung 30 – 9
7 21 + , scan lagi
7
21
+ ,
hitung 7 + 24
28 ,
finish
cara ini dapat ditulis dengan menggunakan stack:- scan string dari kiri ke kanan
- jika ketemu operand push itu ke stack
- jika operator lakukan pop 2x
kompleksitas O(n^2)
Cara mengevaluasi prefix
+ 7
– x 6
5 ^ 3 2
+ 7
– x 6
5 ^
3 2
+ 7
– x 6
5 9
+ 7
– x
6 5
9
+ 7
– 30 9
+ 7 – 30
9
+ 7 21
+
7 21
28untuk algoritma bila menggunakan stack sama dengan postfix hanya saja scan dari kanan ke kiri
cara mengubah infix ke prefix
cari operator dengan tingkat tertinggi dan ubah ke prefix lakukan untuk semua operator
untuk lebih jelasnya dapat dilihat di contoh:
A
+ B – C x D
^ E / F
A
+ B – C x ^ D E / F
A
+ B – C
x ^ D E / F
A
+ B – x C ^ D E / F
A
+ B – x
C ^ D E / F
A
+ B – / x C ^ D E F
A + B – / x C ^ D E F
+
A B – / x C ^ D E F
+ A B – / x C ^ D E F
–
+ A B / x C ^ D E F , prefix
Dept First Search(DFS)
merupakan algoritma untuk mentraversing atau mencari data dari graf atau root
dilakukan dengan konsep rekursif
berikut algoritma nya:
- Masukkan root ke dalam stack dengan push
- simpan isi elemen root ke stack
- Hapus isi stack teratas dengan pop
- Periksa apakah root pohon yang disimpan tadi memiliki cabang
- Jika ya, push semua cabangl yang dibangkitkan ke dalam stack
- Jika stack kosong stop(base case dari rekursif), tapi jika tidak kembali ke langkah dua
prosedur pengecekan DFS dapat diketik seperti:
void DFS_printPreOrder(simpul *root){ if(root!=NULL){ stack S; createEmptyStack(&S); push(root, &S); while(isStackEmpty(S) != 1){ printf("%c ", S.top->elemen->huruf); simpul *node = peek(S); pop(&S); if(node->right != NULL){ push(node->right, &S); } if(node->left != NULL){ push(node->left, &S); } } printf("\n"); }}Nama : Benedick Asdyo
NIM : 2101631090
Tidak ada komentar:
Posting Komentar