Algoritma Balanced Brackets di Java

1. Ikhtisar

Balanced Brackets, juga dikenal sebagai Balanced Parentheses, adalah masalah pemrograman yang umum.

Dalam tutorial ini, kami akan memvalidasi apakah tanda kurung dalam string yang diberikan seimbang atau tidak.

Jenis string ini adalah bagian dari apa yang dikenal sebagai bahasa Dyck.

2. Pernyataan Masalah

Tanda kurung dianggap salah satu dari karakter berikut - "(", ")", "[", "]", "{", "}".

Seperangkat tanda kurung dianggap pasangan yang cocok jika kurung buka , "(", "[", dan "{", muncul di sebelah kiri dari kurung tutup yang sesuai , ")", "]", dan "} ”, Masing-masing.

Namun, string yang berisi pasangan braket tidak seimbang jika set braket yang dilingkupinya tidak cocok .

Demikian pula, string yang berisi karakter non-kurung seperti az, AZ, 0-9 atau karakter khusus lainnya seperti #, $, @ juga dianggap tidak seimbang .

Misalnya, jika inputnya adalah "{[(])}", pasangan tanda kurung siku, "[]", mengapit satu kurung siku bukaan tidak seimbang, "(". Demikian pula, pasangan tanda kurung siku, "() ", Mengapit satu kurung siku penutup tidak seimbang,"] ". Dengan demikian, string masukan" {[(])} "tidak seimbang.

Oleh karena itu, string yang berisi karakter braket dikatakan seimbang jika:

  1. Tanda kurung buka yang cocok muncul di sebelah kiri setiap tanda kurung tutup yang sesuai
  2. Tanda kurung yang diapit oleh tanda kurung seimbang juga seimbang
  3. Ini tidak berisi karakter non-kurung apa pun

Ada beberapa kasus khusus yang perlu diingat: null dianggap tidak seimbang, sedangkan string kosong dianggap seimbang .

Untuk mengilustrasikan lebih lanjut definisi kami tentang tanda kurung siku, mari lihat beberapa contoh tanda kurung seimbang:

() [()] {[()]} ([{{[(())]}}])

Dan beberapa yang tidak seimbang:

abc[](){} {{[]()}}}} {[(])}

Sekarang setelah kita memiliki pemahaman yang lebih baik tentang masalah kita, mari kita lihat cara mengatasinya!

3. Pendekatan Solusi

Ada berbagai cara untuk mengatasi masalah ini. Dalam tutorial ini, kita akan melihat dua pendekatan:

  1. Menggunakan metode kelas String
  2. Menggunakan implementasi Deque

4. Penyiapan dan Validasi Dasar

Mari pertama-tama buat metode yang akan mengembalikan nilai true jika input seimbang dan false jika input tidak seimbang:

public boolean isBalanced(String str)

Mari pertimbangkan validasi dasar untuk string input:

  1. Jika masukan null dilewatkan, maka itu tidak seimbang.
  2. Agar senar seimbang, pasangan tanda kurung buka dan tutup harus cocok. Oleh karena itu, akan aman untuk mengatakan bahwa string input yang panjangnya ganjil tidak akan diseimbangkan karena akan berisi setidaknya satu braket yang tidak cocok.
  3. Sesuai pernyataan masalah, perilaku yang seimbang harus diperiksa di antara tanda kurung. Oleh karena itu, string input apa pun yang berisi karakter non-braket adalah string yang tidak seimbang.

Dengan aturan ini, kita dapat mengimplementasikan validasi:

if (null == str || ((str.length() % 2) != 0)) { return false; } else { char[] ch = str.toCharArray(); for (char c : ch) { if (!(c == '' || c == ']' || c == ')')) { return false; } } }

Sekarang string input divalidasi, kita dapat melanjutkan untuk menyelesaikan masalah ini.

5. Menggunakan Metode String.replaceAll

Dalam pendekatan ini, kita akan melakukan perulangan melalui string masukan untuk menghapus kemunculan "()", "[]", dan "{}" dari string menggunakan String.replaceAll. Kami melanjutkan proses ini sampai tidak ada kejadian lebih lanjut yang ditemukan dalam string input.

Setelah proses selesai, jika panjang string kita nol, semua pasangan tanda kurung yang cocok telah dilepas dan string input seimbang. Namun, jika panjangnya tidak nol, maka beberapa tanda kurung buka atau tutup yang tidak cocok masih ada dalam string. Oleh karena itu, string masukan tidak seimbang.

Mari kita lihat implementasi lengkapnya:

while (str.contains("()") || str.contains("[]") || str.contains("{}")) { str = str.replaceAll("\\(\\)", "") .replaceAll("\\[\\]", "") .replaceAll("\\{\\}", ""); } return (str.length() == 0);

6. Menggunakan Deque

Deque adalah bentuk Antrian yang menyediakan operasi tambah, ambil, dan intip di kedua ujung antrian. Kami akan memanfaatkan fitur pesanan Last-In-First-Out (LIFO) dari struktur data ini untuk memeriksa saldo dalam string input.

Pertama, mari buat Deque kita :

Deque deque = new LinkedList();

Perhatikan bahwa kami telah menggunakan LinkedList di sini karena menyediakan implementasi untuk antarmuka Deque .

Sekarang deque kita dibuat, kita akan mengulang melalui setiap karakter dari string input satu per satu. Jika karakter tersebut adalah kurung buka, maka kami akan menambahkannya sebagai elemen pertama di Deque :

if (ch == '{' || ch == '[' || ch == '(') { deque.addFirst(ch); }

Tapi, jika karakternya adalah kurung tutup, maka kami akan melakukan beberapa pemeriksaan pada LinkedList .

Pertama, kami memeriksa apakah LinkedList kosong atau tidak. Daftar kosong berarti braket penutup tidak tertandingi. Oleh karena itu, string input tidak seimbang. Jadi kami mengembalikan false .

Namun, jika LinkedList tidak kosong, maka kita mengintip karakter last-in-nya menggunakan metode peekFirst . Jika dapat dipasangkan dengan kurung tutup, maka kami menghapus karakter paling atas ini dari daftar menggunakan metode removeFirst dan melanjutkan ke iterasi loop berikutnya:

if (!deque.isEmpty() && ((deque.peekFirst() == '{' && ch == '}') || (deque.peekFirst() == '[' && ch == ']') || (deque.peekFirst() == '(' && ch == ')'))) { deque.removeFirst(); } else { return false; }

Pada akhir pengulangan, semua karakter diperiksa keseimbangannya, sehingga kita dapat mengembalikan nilai true . Di bawah ini adalah implementasi lengkap dari pendekatan berbasis Deque :

Deque deque = new LinkedList(); for (char ch: str.toCharArray()) { if (ch == '{' || ch == '[' || ch == '(') { deque.addFirst(ch); } else { if (!deque.isEmpty() && ((deque.peekFirst() == '{' && ch == '}') || (deque.peekFirst() == '[' && ch == ']') || (deque.peekFirst() == '(' && ch == ')'))) { deque.removeFirst(); } else { return false; } } } return true;

7. Kesimpulan

Dalam tutorial ini, kami membahas pernyataan masalah Balanced Brackets dan menyelesaikannya menggunakan dua pendekatan berbeda.

Seperti biasa, kode tersedia di Github.