Pada operasi matematika sering dijumpai penggunaan tanda kurung. Bahkan terkadang melibatkan sejumlah tanda kurung dalam satu operasi matematik, sehingga terkadang ada pasangan tanda kurung yang lupa. Apabila kita menggunakan alat bantu kalkulator atau komputer maka kesalahan penulisan tanda kurung akan menyebabkan error perhitungan karena unbalanced.
Penggunaan tanda kurung (atau simbol sejenisnya) juga sering digunakan pada saat mengetikkan sebuah source code program pada sebuah IDE (Interface Development Environment). Uniknya sebuah IDE mampu mendeteksi apabila terjadi unbalanced bracket sehingga dapat memberikan semacam "early warning" bila terjadi unbalanced bracket.
Salah satu cara untuk memeriksa pasangan tanda kurung adalah menggunakan "stack". Stack adalah suatu bentuk struktur data yang mengadopsi sifat "stack" atau "tumpukan". Sebuah contoh stack pada kehidupan nyata adalah "tumpukan piring". Tumpukan piring ini memiliki sifat jika diletakkan piring baru maka akan diletakkan pada bagian atasnya, sedangkan bila akan mengambil piring maka yang terambil duluan adalah bagian paling atas. Sifat ini dikenal dengan istilah LIFO (Last In First Out) atau yang pertama kali masuk maka dialah yang pertama kali keluar.
Dengan karakter stack seperti itu maka ada dua operasi umum pada stack yaitu menumpuk (push) dan mengambil (pop). Pada operasi push hanya dilakukan penyimpanan data pada stack. Sedangkan pada operasi pop dilakukan pengambilan data (ada output data yang dikeluarkan).
Pada penerapan stack kali ini, operasi pop dibuat hanya untuk mengeluarkan data dari tumpukan tanpa ada output yang dihasilkan atau dengan kata lain hanya "membuang data" dari stack, hal ini dilakukan karena output data tidak diperlukan. Saya menyebut hal ini dengan "pop_kosong" karena tidak ada output atau void.
Singkat Cerita
Perhatikan operasi matematika berikut:
(a+b)*(2*(3*a+7)-(3-c))
atau bisa disederhanakan menjadi:
()(()())
Secara umum terdapat dua jenis tanda kurung yaitu tanda kurung kiri "(" dan tanda kurung kanan ")". Algoritmanya adalah jika ditemukan tanda kurung kiri "(" maka dilakukan operasi "push" pada stack. Sedangkan bila ditemukan tanda kurung kanan ")" maka dilakukan operasi "pop" pada stack.
Pendeteksian kesalahan diperoleh dengan mengecek apabila ditemukan tanda ")" tetapi stack sudah kosong sehingga tidak bisa dilakukan operasi "pop". Pendeteksian kesalahan berikutnya adalah apabila isi stack masih ada tetapi tanda ")" sudah habis.
Source Code
#include <iostream>
#include <string>
using namespace std;
struct node{
char value;
node *next;
};
struct stack{
node *head=NULL;
void push(char data){
node* node_data=new node();
node_data->value=data;
node_data->next=head;
head=node_data;
}
void pop_kosong(){
if(head!=NULL){
node *buff=head;
head=head->next;
delete buff;
}
}
};
bool cek(string data){
stack data_stack;
int n=data.size();
for(int i=0;i<n;i++){
if(data[i]=='('){
data_stack.push(data[i]);
}
else if(data[i]==')'){
if(data_stack.head==NULL) return false;
data_stack.pop_kosong();
}
}
if(data_stack.head!=NULL) return false;
return true;
}
int main(){
int T; //jumlah test case
cin >> T;
cout << endl;
while(T--){
string S;
cin >> S;
string result="Input masih salah";
if(cek(S)) result="Input sudah benar";
cout << result << endl << endl;
}
return 0;
}
Hasil Running
Pertanyaan
Pertanyaannya adalah bukannya bisa saja digunakan algoritma sederhana seperti pengecekkan jumlah kurung "(" dan jumlah kurung ")". Apabila jumlahnya sama maka benar dan apabila jumlahnya tidak sama maka salah. Masuk akal sih.. Mmm.. tapi bagaimana bila kasusnya adalah ada input seperti berikut :
))((
Secara jumlah maka hasilnya akan sama antara tanda "(" dan ")". Dan akan terdeteksi benar oleh program. Hal ini berbeda bila menggunakan implementasi dari struktur data "stack" karena akan langsung terdeteksi salah bila ada tanda ")" tapi stack dalam keadaan kosong.
Special thanks to Samsung Academy SRIN Lecturer:
1. Pak Risman Adnan Mattotorang
2. Mas Leonardi
3. Mas Gilang
4. Mas Susanto Tedja
