List berantai adalah salah satu jenis struktur data, yang tersusun dari objek yang terkait satu sama lain oleh pointer. Pada bagian sebelumnya, kita menggunakan list berantai untuk menyimpan String terurut, dan kita juga mengimplementasikan operasi sisip, hapus dan cari pada list tersebut.
Akan tetapi kita juga bisa menyimpan list String pada array atau ArrayList. Kita bisa juga mengimplementasikan operasi sisip,hapus, dan cari. Implementasi operasi tersebut akan berbeda, akan tetapi antar muka dan perilakunya akan tetap sama.
Istilah tipe data abstrak (abstract data type, atau ADT) adalah kumpulan nilai dan operasi yang bisa dilakukan pada nilai tersebut, tanpa perlu mengetahui bagaimana nilai tersebut disimpan dan bagaimana operasi tersebut diimplementasikan.
Suatu "list terurut yang berisi string" adalah contoh tipe data abstrak. Ada banyak cara untuk mengimplementasikan tipe data abstrak yang sama, misalnya seperti disebut di atas, list terurut berisi string bisa diimplementasikan dalam bentuk list berantai atau array.
Program yang menggunakan tipe data ini bisa menggunakannya tanpa mengetahui dengan detail tentang implementasinya. Lebih jauh, implementasi TDA bisa diganti tanpa mempengaruhi jalannya program secara keseluruhan. Dengan cara ini, program bisa lebih mudah untuk dipelihara dan didebug. TDA adalah alat penting dalam rekayasa perancang lunak.
Pada bagian ini dan yang akan datang, kita akan lihat TDA lain, yaitu tumpukan dan antrian. Tumpukan dan antrian sering diimplementasikan dalam bentuk list berantai, akan tetapi ini bukan satu-satunya cara implementasi. Mari kita anggap bagian ini sebagai studi kasus dari TDA.
Tumpukan (stack) terdiri dari kumpulan item yang disusun sedemikian rupa sehingga satu item ditumpuk di atas item lainnya, mirip seperti tumpukan boks. Hanya item paling atas yang bisa diakses pada suatu saat.
Item tersebut bisa diambil dari tumpukan dengan operasi yang disebut "ambil" (atau dalam bahasa Inggris, istilah untuk mengeluarkan item dari tumpukan disebut "pop"). Item di bawah hanya bisa diambil jika semua item di atasnya telah dikeluarkan dari tumpukan. Suatu item hanya bisa ditambahkan di atas tumpukan dengan perintah "dorong" (atau "push").
Kita bisa membuat tumpukan dari berbagai macam data. Misalnya, jika itemnya bertipe int, maka operasi dorong dan keluar bisa diimplementasikan dalam metode instansi
Kita tidak bisa mengambil item dari tumpukan yang kosong, jadi kita juga perlu memberi tahu apakah suatu tumpukan kosong atau tidak. Kita perlu operasi lain untuk mengujinya, yang diimplementasikan dalam metode instansi
Ilustrasi berikut menggambarkan tumpukan int, sebagai tipe data abstrak. TDA ini bisa diimplementasikan dengan berbagai cara, akan tetapi gambar tumpukan di dalam imaginasi kita akan tetap sama.
Pada implementasi dengan list berantai, tumpukan atas adalah simpul kepala dari list. Kita bisa menambah dan mengurangi simpul pada kepala list berantai -- jauh lebih mudah daripada menyisipkan atau menghapus simpul dari tengah-tengah list.
Berikut ini adalah kelas "tumpukan int" yang mengimplementasikan TDA menggunakan list berantai. (Kelas ini menggunakan kelas bertingkat sebagai kelas simpul dari list berantai. Lihat bagian sebelumnya tentang kelas bertingkat. Jika Anda masih belum paham atau merasa tidak nyaman menggunakan kelas bertingkat, Anda bisa juga memisahkannya sebagai kelas terpisah.)
Anda perlu memahami bagaimana operasi dorong dan ambil dilaksanakan. Mungkin sedikit oret-oretan akan membantu. Lihat bahwa list berantai merupakan bagian private dari kelas TumpukanInt. Program yang menggunakan kelas ini tidak perlu tahu bahwa list berantai digunakan dalam implementasinya.
Sekarang, kita bisa juga mengimplementasikan tumpukan dalam bentuk array, bukan hanya list berantai. Karena banyaknya item di dalam tumpukan bervariasi dan tidak bisa ditentukan, maka kita perlu memiliki variabel lain yang melacak berapa banyak tempat dalam array yang sudah digunakan.
Jika variabel ini kita namakan atas, maka item akan disimpan dalam tumpukan pada posisi 0, 1, ..., atas - 1. Item pada posisi 0 adalah item paling bawah dalam tumpukan, sedangkan item atas - 1 adalah item paling atas.
Untuk mendorong item baru ke dalam tumpukan, kita bisa meletakkan item di posisi atas kemudian nilai atas ditambahkan 1. Jika kita tidak ingin memberi limit banyaknya item di dalam tumpukan, kita bisa menggunakan array dinamis yang telah dibahas sebelumnya.
Berikut ini adalah implementasi kelas TumpukanInt dengan menggunakan array dinamis:
Sekali lagi, implementasi tumpukan (dalam bentuk array) bersifat private. Kedua versi kelas TumpukanInt bisa digunakan dalam suatu program. Jika suatu program menggunakan versi pertama, maka kita bisa menggantinya dengan versi kedua tanpa mengubah isi program lain. Akan tetapi, ada satu kasus di mana kedua kelas akan berbeda, yaitu jika mencoba mengambil item dari tumpukan kosong, maka versi pertama akan melemparkan NullPointerException sedangkan versi kedua akan melemparkan ArrayIndexOutOfBoundsException.
Mungkin akan lebih baik untuk mendefinisikan jenis pengecualian baru, misalnya EmptyStackException di kedua versi. Dan sebetulnya TDA harusnya memberikan spesifikasi apa yang harus dilakukan jika program mencoba mengambil item dari tumpukan kosong. Ini yang sering dilupakan ketika seseorang membuat spesifikasi untuk interface, yang akhirnya masalah lain akan muncul di kemudian hari.
Apa contoh kegunaan tumpukan dalam keadaan sehari-hari? Misalnya, lihat apa yang terjadi jika suatu rutin memanggil subrutin. Rutin pertama akan dihentikan sementara ketika subrutin yang dipanggil dieksekusi, dan akan diteruskan apabila subrutin yang dipanggil selesai dijalankan.
Sekarang, misalnya subrutin tersebut memanggil subrutin kedua, dan subrutin kedua memanggil subrutin ketiga, dan seterusnya. Setiap subrutin akan berhenti untuk sementara ketika subrutin berikutnya dipanggil. Komputer harus bisa melacak subrutin yang dihentikan. Bagaimana caranya? Yaitu dengan menggunakan tumpukan.
Ketika subrutin dipanggil, catatan aktivasi (activation record) dibuat untuk subrutin tersebut. Catatan aktivasi ini berisi informasi yang relevan tentang eksekusi dari subruti tersebut, misalnya parameter dan variabel lokalnya. Catatan aktivasi ini ditempatkan dalam tunpukan. Catatan ini akan dibuang ketika subrutin selesai dipanggil.
Jika subrutin ini memanggil subrutin lain, maka catatan aktivasi dari subrutin kedua akan didorong ke dalam tumpukan, di atas catatan aktivasi subrutin pertama. Tumpukan akan semakin besar jika semakin banyak subrutin yang dipanggil, dan semakin kecil jika subrutin-subrutin itu selesai dijalankan.
Contoh lainnya, tumpukan digunakan untuk mengevaluasi ekspresi postfix (postfix expresssion). Ekspresi matematika biasa seperti2+(15-12)*17 disebut ekspresi infix. Dalam ekspresi infix, operator berada di tengah nilai yang akan dihitung, misalnya "2 + 2". Dalam ekspresi postfix, operator ada di akhir nilai, misalnya "2 2 +".
Ekspresi 2+(15-12)*17" dapat ditulis dalam bentuk postfix menjadi "2 15 12 - 17 * +". Di sini operator "-" dilakukan pada dua nilai sebelumnya, yaitu "15" dan "12". Tanda * dilakukan pada dua nilai sebelumnya, yaitu "15 12 -" dan "17". Dan operator "+" dilakukan pada 2 dan "15 12 - 17 *". Hasilnya akan persis sama dengan ekspresi infix awalnya.
Meskipun lebih mudah bagi manusia untuk melakukan perhitungan dengan ekspresi infix, ekspresi postfix memiliki beberapa keuntungan. Satu hal, ekspresi postfix tidak memerlukan tanda kurung atau aturan perhitungan (tanda kali harus dilakukan lebih dulu sebelum tambah misalnya). Aturan penghitungan hanya ditentukan berdasarkan urutannya saja. Sehingga algoritma yang menghitung ekspresi postfix dapat menjalankannya dengan lebih cepat dan tepat.
Sekarang misalnya kita akan menghitung ekspresi "2 15 12 - 17 * +" dari kiri ke kanan. Nilai yang kita temui pertama adalah 2, tapi apa yang bisa kita lakukan dengan 2? Di sini kita belum tahu operatornya, dan selain itu kita juga belum tahu nilai lainnya. Kita akan ingat nilai 2 ini untuk sementara, yaitu dengan mendorongnya ke dalam tumpukan.
Berikutnya, kita akan melihat nilai 15, yang kita juga masukkan ke dalam tumpukan di atas nilai 2. Kemudian nilai 12 juga dimasukkan ke dalam tumpukan di atas 15.
Sekarang kita sampai pada operator "-". Operasi ini dilakukan pada dua nilai sebelumnya. Kita telah menyimpan 2 nilai sebelumnya ke dalam tumpukan, yaitu 15 dan 12. Sekarang kita ambil 2 nilai tersebut dari dalam tumpukan, dan kita lakukan perhitungan 15- 12 yaitu 3.
Nilai 3 ini kita simpan lagi ke dalam tumpukan. Ingat bahwa 15 dan 12 sudah diambil dari dalam tumpukan, sehingga hanya nilai 2 yang ada di dalam tumpukan. Setelah nilai 3 dimasukkan ke dalam tumpukan, maka 3 ada di atas 2 di dalam tumpukan.
Item berikutnya adalah 17, yang juga dimasukkan ke dalam tumpukan di atas nilai 3. Untuk menghitung item berikutnya "*", kita ambil 2 nilai dari dalam tumpukan, yaitu 3 dan 17. Hasil dari 3 * 17, yaitu 51 dimasukkan kembali ke dalam tumpukan (di atas 2 yang masih ada di dalam tumpukan).
Item berikutnya adalah "+", yang akan mengambil 51 dan 2 dari dalam tumpukan, menghitung hasilnya, yaitu 53, kemudian menyimpannya lagi ke dalam tumpukan. Sekarang kita sampai pada akhir ekspresi. Nilai pada tumpukan itu adalah hasil perhitungan keseluruhan ekspresi. Kita cukup mengambil nilainya dan melaporkan hasilnya, yaitu 53.
Algoritma untuk melakukan perhitungan ekspresi postfix adalah sebagai berikut :
Kesalahan ekspresi dapat dideteksi dengan mudah. Misalnya, dalam ekspresi "2 3 + *", tidak cukup nilai untuk menghitung operasi "*". Ini akan dideteksi oleh algoritma ketika mencoba mengambil nilai kedua dari dalam tumpukan, karena pada saat itu tumpukan sudah kosong.
Kesalahan lain bisa juga muncul ketika menghitung ekspresi "2 3 4 +", di mana tidak cukup operator untuk menghitung semua nilai. Ini akan dideteksi ketika 2 masih ada di dalam tumpukan di akhir algoritma.
Ekspresi postfix sering digunakan secara internal oleh komputer. Dan sebenarnya, mesin virtual Java adalah "mesin tumpukan", yang menggunakan tumpukan untuk melakukan perhitungan yang telah kita diskusikan. Algoritma ini bisa diperluas untuk menangani variabel dan konstanta. Ketika variabel ditemukan di dalam ekspresi, isi variabel ini didorong ke dalam tumpukan.
Algoritma ini juga bisa dikembangkan untuk operator yang membutuhkan kurang atau lebih dari dua operator. Banyaknya nilai yang diambil dari dalam tumpukan bisa disesuaikan dengan berapa banyak nilai yang dibutuhkan. Misalnya, operator "-" sebagai operator negasi, misalnya "-x" hanya membutuhkan satu nilai.
Akan tetapi kita juga bisa menyimpan list String pada array atau ArrayList. Kita bisa juga mengimplementasikan operasi sisip,hapus, dan cari. Implementasi operasi tersebut akan berbeda, akan tetapi antar muka dan perilakunya akan tetap sama.
Istilah tipe data abstrak (abstract data type, atau ADT) adalah kumpulan nilai dan operasi yang bisa dilakukan pada nilai tersebut, tanpa perlu mengetahui bagaimana nilai tersebut disimpan dan bagaimana operasi tersebut diimplementasikan.
Suatu "list terurut yang berisi string" adalah contoh tipe data abstrak. Ada banyak cara untuk mengimplementasikan tipe data abstrak yang sama, misalnya seperti disebut di atas, list terurut berisi string bisa diimplementasikan dalam bentuk list berantai atau array.
Program yang menggunakan tipe data ini bisa menggunakannya tanpa mengetahui dengan detail tentang implementasinya. Lebih jauh, implementasi TDA bisa diganti tanpa mempengaruhi jalannya program secara keseluruhan. Dengan cara ini, program bisa lebih mudah untuk dipelihara dan didebug. TDA adalah alat penting dalam rekayasa perancang lunak.
Pada bagian ini dan yang akan datang, kita akan lihat TDA lain, yaitu tumpukan dan antrian. Tumpukan dan antrian sering diimplementasikan dalam bentuk list berantai, akan tetapi ini bukan satu-satunya cara implementasi. Mari kita anggap bagian ini sebagai studi kasus dari TDA.
Tumpukan (stack) terdiri dari kumpulan item yang disusun sedemikian rupa sehingga satu item ditumpuk di atas item lainnya, mirip seperti tumpukan boks. Hanya item paling atas yang bisa diakses pada suatu saat.
Item tersebut bisa diambil dari tumpukan dengan operasi yang disebut "ambil" (atau dalam bahasa Inggris, istilah untuk mengeluarkan item dari tumpukan disebut "pop"). Item di bawah hanya bisa diambil jika semua item di atasnya telah dikeluarkan dari tumpukan. Suatu item hanya bisa ditambahkan di atas tumpukan dengan perintah "dorong" (atau "push").
Kita bisa membuat tumpukan dari berbagai macam data. Misalnya, jika itemnya bertipe int, maka operasi dorong dan keluar bisa diimplementasikan dalam metode instansi
void dorong(int itemBaru) // Tambah itemBaru di atas tumpukan int ambil() // Mengambil int paling atas pada tumpukan
boolean isKosong() // Kembalikan true jika tumpukan kosong
Berikut ini adalah kelas "tumpukan int" yang mengimplementasikan TDA menggunakan list berantai. (Kelas ini menggunakan kelas bertingkat sebagai kelas simpul dari list berantai. Lihat bagian sebelumnya tentang kelas bertingkat. Jika Anda masih belum paham atau merasa tidak nyaman menggunakan kelas bertingkat, Anda bisa juga memisahkannya sebagai kelas terpisah.)
public class TumpukanInt { private static class Simpul { // Objek dengan tipe Simpul menyimpan // satu item di dalam list berantai int item; Simpul berikut; } // Referensi ke simpul paling atas dari tumpukan // jika atas == null, maka tumpukan tidak berisi // apa-apa (kosong) private Simpul atas; public void dorong( int N ) { // Letakkan N di tumpukan paling atas Simpul atasBaru; // Simpul baru untuk menyimpan item baru atasBaru = new Simpul(); atasBaru.item = N; // Simpan N di simpul baru atasBaru.berikut = atas; // Simpul baru menunjuk pada atas lama atas = atasBaru; // Simpul baru sekarang menjadi atas } public int ambil() { // Ambil item paling atas dari dalam tumpukan // dan kembalikan nilainya. Catatan bahwa rutin ini akan // melempar NullPointerException jika kita mencoba untuk // mengambil item dari tumpukan kosong int itemAtas = atas.item; // Item yang akan diambil atas = atas.berikut; // Item yang dulunya di posisi kedua sekarang di atas return itemAtas; } public boolean isKosong() { // Kembalikan true jika tumpukan kosong. // Kembalikan false jika ada satu atau lebih item di dalam tumpukan return (atas == null); } } // akhir kelas TumpukanInt
Anda perlu memahami bagaimana operasi dorong dan ambil dilaksanakan. Mungkin sedikit oret-oretan akan membantu. Lihat bahwa list berantai merupakan bagian private dari kelas TumpukanInt. Program yang menggunakan kelas ini tidak perlu tahu bahwa list berantai digunakan dalam implementasinya.
Sekarang, kita bisa juga mengimplementasikan tumpukan dalam bentuk array, bukan hanya list berantai. Karena banyaknya item di dalam tumpukan bervariasi dan tidak bisa ditentukan, maka kita perlu memiliki variabel lain yang melacak berapa banyak tempat dalam array yang sudah digunakan.
Jika variabel ini kita namakan atas, maka item akan disimpan dalam tumpukan pada posisi 0, 1, ..., atas - 1. Item pada posisi 0 adalah item paling bawah dalam tumpukan, sedangkan item atas - 1 adalah item paling atas.
Untuk mendorong item baru ke dalam tumpukan, kita bisa meletakkan item di posisi atas kemudian nilai atas ditambahkan 1. Jika kita tidak ingin memberi limit banyaknya item di dalam tumpukan, kita bisa menggunakan array dinamis yang telah dibahas sebelumnya.
Berikut ini adalah implementasi kelas TumpukanInt dengan menggunakan array dinamis:
public class TumpukanInt { private int[] item = new int[10]; // Menyimpan item dalam tumpukan private int atas = 0; // Banyaknya item dalam tumpukan public void dorong( int N ) { // Tambahkan N ke dalam tumpukan if (atas == item.length) { // Array sudah penuh, jadi buat array yang lebih besar dan // kopi isi tumpukan sekarang ke dalam array baru int[] arrayBary = new int[ 2*item.length ]; System.arraycopy(item, 0, arrayBary, 0, item.length); item = arrayBaru; } item[atas] = N; // Letakkan N di tempat kosong berikutnya atas++; // Jumlah item bertambah 1 } public int ambil() { // Mengambil item teratas dari tumpukan dan mengembalikannya // Ingat bahwa rutin ini akan melempar pengecualian // ArrayIndexOutOfBoundsException jika mencoba mengambil // item dari tumpukan kosong int itemAtas = item[top - 1] // Item teratas di dalam tumpukan atas--; // Jumlah item dalam tumpukan berkurang 1 return itemAtas; } public boolean isKosong() { // Kembalikan true jika tumpukan kosong // Kembalikan false jika ada satu atau lebih item di dalam tumpukan return (atas == 0); } } // akhir kelas TumpukanInt
Sekali lagi, implementasi tumpukan (dalam bentuk array) bersifat private. Kedua versi kelas TumpukanInt bisa digunakan dalam suatu program. Jika suatu program menggunakan versi pertama, maka kita bisa menggantinya dengan versi kedua tanpa mengubah isi program lain. Akan tetapi, ada satu kasus di mana kedua kelas akan berbeda, yaitu jika mencoba mengambil item dari tumpukan kosong, maka versi pertama akan melemparkan NullPointerException sedangkan versi kedua akan melemparkan ArrayIndexOutOfBoundsException.
Mungkin akan lebih baik untuk mendefinisikan jenis pengecualian baru, misalnya EmptyStackException di kedua versi. Dan sebetulnya TDA harusnya memberikan spesifikasi apa yang harus dilakukan jika program mencoba mengambil item dari tumpukan kosong. Ini yang sering dilupakan ketika seseorang membuat spesifikasi untuk interface, yang akhirnya masalah lain akan muncul di kemudian hari.
Apa contoh kegunaan tumpukan dalam keadaan sehari-hari? Misalnya, lihat apa yang terjadi jika suatu rutin memanggil subrutin. Rutin pertama akan dihentikan sementara ketika subrutin yang dipanggil dieksekusi, dan akan diteruskan apabila subrutin yang dipanggil selesai dijalankan.
Sekarang, misalnya subrutin tersebut memanggil subrutin kedua, dan subrutin kedua memanggil subrutin ketiga, dan seterusnya. Setiap subrutin akan berhenti untuk sementara ketika subrutin berikutnya dipanggil. Komputer harus bisa melacak subrutin yang dihentikan. Bagaimana caranya? Yaitu dengan menggunakan tumpukan.
Ketika subrutin dipanggil, catatan aktivasi (activation record) dibuat untuk subrutin tersebut. Catatan aktivasi ini berisi informasi yang relevan tentang eksekusi dari subruti tersebut, misalnya parameter dan variabel lokalnya. Catatan aktivasi ini ditempatkan dalam tunpukan. Catatan ini akan dibuang ketika subrutin selesai dipanggil.
Jika subrutin ini memanggil subrutin lain, maka catatan aktivasi dari subrutin kedua akan didorong ke dalam tumpukan, di atas catatan aktivasi subrutin pertama. Tumpukan akan semakin besar jika semakin banyak subrutin yang dipanggil, dan semakin kecil jika subrutin-subrutin itu selesai dijalankan.
Contoh lainnya, tumpukan digunakan untuk mengevaluasi ekspresi postfix (postfix expresssion). Ekspresi matematika biasa seperti2+(15-12)*17 disebut ekspresi infix. Dalam ekspresi infix, operator berada di tengah nilai yang akan dihitung, misalnya "2 + 2". Dalam ekspresi postfix, operator ada di akhir nilai, misalnya "2 2 +".
Ekspresi 2+(15-12)*17" dapat ditulis dalam bentuk postfix menjadi "2 15 12 - 17 * +". Di sini operator "-" dilakukan pada dua nilai sebelumnya, yaitu "15" dan "12". Tanda * dilakukan pada dua nilai sebelumnya, yaitu "15 12 -" dan "17". Dan operator "+" dilakukan pada 2 dan "15 12 - 17 *". Hasilnya akan persis sama dengan ekspresi infix awalnya.
Meskipun lebih mudah bagi manusia untuk melakukan perhitungan dengan ekspresi infix, ekspresi postfix memiliki beberapa keuntungan. Satu hal, ekspresi postfix tidak memerlukan tanda kurung atau aturan perhitungan (tanda kali harus dilakukan lebih dulu sebelum tambah misalnya). Aturan penghitungan hanya ditentukan berdasarkan urutannya saja. Sehingga algoritma yang menghitung ekspresi postfix dapat menjalankannya dengan lebih cepat dan tepat.
Sekarang misalnya kita akan menghitung ekspresi "2 15 12 - 17 * +" dari kiri ke kanan. Nilai yang kita temui pertama adalah 2, tapi apa yang bisa kita lakukan dengan 2? Di sini kita belum tahu operatornya, dan selain itu kita juga belum tahu nilai lainnya. Kita akan ingat nilai 2 ini untuk sementara, yaitu dengan mendorongnya ke dalam tumpukan.
Berikutnya, kita akan melihat nilai 15, yang kita juga masukkan ke dalam tumpukan di atas nilai 2. Kemudian nilai 12 juga dimasukkan ke dalam tumpukan di atas 15.
Sekarang kita sampai pada operator "-". Operasi ini dilakukan pada dua nilai sebelumnya. Kita telah menyimpan 2 nilai sebelumnya ke dalam tumpukan, yaitu 15 dan 12. Sekarang kita ambil 2 nilai tersebut dari dalam tumpukan, dan kita lakukan perhitungan 15- 12 yaitu 3.
Nilai 3 ini kita simpan lagi ke dalam tumpukan. Ingat bahwa 15 dan 12 sudah diambil dari dalam tumpukan, sehingga hanya nilai 2 yang ada di dalam tumpukan. Setelah nilai 3 dimasukkan ke dalam tumpukan, maka 3 ada di atas 2 di dalam tumpukan.
Item berikutnya adalah 17, yang juga dimasukkan ke dalam tumpukan di atas nilai 3. Untuk menghitung item berikutnya "*", kita ambil 2 nilai dari dalam tumpukan, yaitu 3 dan 17. Hasil dari 3 * 17, yaitu 51 dimasukkan kembali ke dalam tumpukan (di atas 2 yang masih ada di dalam tumpukan).
Item berikutnya adalah "+", yang akan mengambil 51 dan 2 dari dalam tumpukan, menghitung hasilnya, yaitu 53, kemudian menyimpannya lagi ke dalam tumpukan. Sekarang kita sampai pada akhir ekspresi. Nilai pada tumpukan itu adalah hasil perhitungan keseluruhan ekspresi. Kita cukup mengambil nilainya dan melaporkan hasilnya, yaitu 53.
Algoritma untuk melakukan perhitungan ekspresi postfix adalah sebagai berikut :
Mulai dengan tumpukan kosong untuk setiap item di dalam ekspresi: jika item berupa bilangan: Dorong item ke dalam tumpukan jika item berupa operator Ambil dua nilai dari tumpukan // bisa terjadi kesalahan Lakukan perhitungan dua nilai dengan operator tersebut Dorong hasil perhitungan ke dalam tumpukan else Ada kesalahan dalam ekspresi Ambil nilai dari tumpukan Jika tumpukan tidak kosong: Ada kesalahan dalam ekspresi else: Nilai terakhir adalah hasil perhitungan
Kesalahan ekspresi dapat dideteksi dengan mudah. Misalnya, dalam ekspresi "2 3 + *", tidak cukup nilai untuk menghitung operasi "*". Ini akan dideteksi oleh algoritma ketika mencoba mengambil nilai kedua dari dalam tumpukan, karena pada saat itu tumpukan sudah kosong.
Kesalahan lain bisa juga muncul ketika menghitung ekspresi "2 3 4 +", di mana tidak cukup operator untuk menghitung semua nilai. Ini akan dideteksi ketika 2 masih ada di dalam tumpukan di akhir algoritma.
Ekspresi postfix sering digunakan secara internal oleh komputer. Dan sebenarnya, mesin virtual Java adalah "mesin tumpukan", yang menggunakan tumpukan untuk melakukan perhitungan yang telah kita diskusikan. Algoritma ini bisa diperluas untuk menangani variabel dan konstanta. Ketika variabel ditemukan di dalam ekspresi, isi variabel ini didorong ke dalam tumpukan.
Algoritma ini juga bisa dikembangkan untuk operator yang membutuhkan kurang atau lebih dari dua operator. Banyaknya nilai yang diambil dari dalam tumpukan bisa disesuaikan dengan berapa banyak nilai yang dibutuhkan. Misalnya, operator "-" sebagai operator negasi, misalnya "-x" hanya membutuhkan satu nilai.
Tidak ada komentar:
Posting Komentar