Kira bilangan pasangan yang perlu dikeluarkan supaya semua urutan kurungan seimbang kosong

C pengkompil menganggap rentetan sebagai tatasusunan aksara, jadi mudah untuk mengalih keluar aksara daripada rentetan berdasarkan kedudukan. Kedudukan pertama dan terakhir rentetan mesti diperiksa untuk kehadiran kurungan dan mesti dialih keluar. Rentetan boleh disalin ke pembolehubah lain dan dipaparkan.

Terdapat banyak fungsi yang telah ditetapkan dalam C yang boleh digunakan dengan cekap untuk memanipulasi rentetan. Dalam bahasa C, memadam aksara dari kedudukan permulaan atau penamat adalah mudah dengan bantuan fungsi.

Keluarkan kurungan pembuka dan penutup daripada rentetan

Kurungan ialah aksara tunggal yang merupakan sebahagian daripada rentetan input dan boleh dikeluarkan daripada rentetan mengikut logik dan algoritma yang diberikan di bawah

Aksara

ialah sebarang kekunci abjad angka yang kita lihat pada papan kekunci dan ia disimpan dalam pembolehubah aksara dalam C.

() dipanggil kurungan dalam c. Kita perlu mengenal pasti watak ini dalam rentetan yang dimasukkan oleh pengguna dan mengeluarkannya daripada rentetan.

Susun atur ialah pembolehubah yang mempunyai banyak lokasi storan yang dialamatkan dengan satu nama dan nombor berturut-turut, manakala rentetan ialah tatasusunan aksara.

Terdapat banyak situasi di mana kita perlu mengalih keluar kurungan daripada rentetan, seperti semasa menyelesaikan ungkapan biasa.

tatabahasa

Fungsi countRemoval menerima str rentetan sebagai input dan mengembalikan nilai integer yang mewakili bilangan pasangan penyingkiran yang diperlukan untuk menjadikan semua urutan kurungan seimbang dalam rentetan kosong. Fungsi ini menggunakan kiraan pembolehubah untuk menjejaki bilangan pemadaman yang diperlukan, pada mulanya ditetapkan kepada 0. Ia juga menggunakan Baki pembolehubah untuk menjejaki keseimbangan antara bilangan kurungan pembukaan dan penutup dalam rentetan. Fungsi itu kemudiannya berulang sepanjang rentetan dan menyemak aksara pada setiap indeks. Jika aksara ialah kurungan kiri, bakinya dinaikkan sebanyak 1, dan jika ia ialah kurungan kanan, bakinya dikurangkan sebanyak 1. Jika baki menjadi negatif, ini bermakna terdapat kurungan kanan tambahan, bilangan pengalihan adalah tambah 1, dan baki ditetapkan semula kepada 0. Selepas gelung, kiraan dikemas kini untuk memasukkan baki yang tinggal dibahagikan dengan 2 sebagai jumlah pemadaman yang diperlukan untuk menjadikan semua urutan kurungan imbangan dalam rentetan kosong.

int countRemoval(string str) {
   int count = 0;
   int balance = 0;
   for (int i = 0; i < str.length(); i++) {
      if (str[i] == '(') {
         balance++;
      } else {
         balance--;
      }
      if (balance < 0) {
         count++;
         balance = 0;
      }
   }
   count += balance / 2;
   return count;
} 

Algoritma

• Langkah 1 - Isytihar str1, str2, dimulakan kepada null.

• Langkah 2 - Isytiharkan pembolehubah integer len,n,i

• Langkah 3 - Terima str1 daripada konsol

• Langkah 4 - Semak sama ada watak pertama ialah (

• Langkah 5 - jika n = 1

• Langkah 6 - Apabila n

  # 🎜🎜

• Langkah 7 - Semak sama ada aksara terakhir str2 ialah ).

• Langkah 8 - Jika ya, gantikan dengan

Langkah 9
• - Cetak str2 yang mengandungi tanda tolak rentetan input ().
  kaedah

Kaedah 1

- Rekursi brute force: Dalam kaedah pertama, kami menggunakan rekursi kekerasan brute untuk mencari semua kemungkinan susulan dan menyemak sama ada ia seimbang. Jika urutannya seimbang, kami mengeluarkan sepasang kurungan dan mengira bilangan pasangan kurungan yang dipadamkan. Kami mengira bilangan minimum pemadaman pasangan yang diperlukan untuk mengosongkan rentetan.

Kaedah 2

- Pengaturcaraan Dinamik: Kaedah kedua menggunakan pengaturcaraan dinamik untuk mengoptimumkan penyelesaian. Kita boleh menggunakan jadual DP 2D untuk menyimpan bilangan pemadaman minimum yang diperlukan untuk subrentetan daripada indeks "i" hingga "j". Kami mengulangi rentetan dan mengisi jadual DP berdasarkan kriteria yang diberikan.

Kaedah 1 Rekursi Keganasan

kod

Dalam kod ini, kami menyemak semua kemungkinan kombinasi urutan, yang menghasilkan kerumitan masa eksponen. Untuk input yang lebih besar, kaedah ini mungkin tidak cekap.

#include <iostream>
#include <string>
using namespace std;

int countRemovalsRecursion(const string &s, int index, int open) {
   if (index == s.size()) {
      return open;
   }

   if (s[index] == '(') {
      return countRemovalsRecursion(s, index + 1, open + 1);
   } else if (open > 0) {
      return countRemovalsRecursion(s, index + 1, open - 1);
   } else {
      return 1 + countRemovalsRecursion(s, index + 1, open);
   }
}

int main() {
   string s = "(()())(";
   cout << "Input string: " << s << endl;
   cout << "Minimum removals (Brute Force Recursion): " << countRemovalsRecursion(s, 0, 0) << endl;
   return 0;
}

Output

Input string: (()())(
Minimum removals (Brute Force Recursion): 1

Kaedah 2

Contoh

Penyelesaian pengaturcaraan dinamik ini mengira bilangan minimum pemadaman yang diperlukan untuk mengosongkan semua urutan kurungan seimbang. Ia berulang pada rentetan, mengemas kini jadual DP satu dimensi dengan bilangan kurungan kiri dan mengembalikan nilai DP akhir sebagai jumlah minimum untuk dialih keluar.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int countRemovalsDP(const string &s) {
   int n = s.size();
   vector<int> dp(n + 1, 0);

   for (int i = 0; i < n; ++i) {
      if (s[i] == '(') {
         dp[i + 1] = dp[i] + 1;
      } else {
         dp[i + 1] = max(dp[i] - 1, 0);
      }
   }
   return dp[n];
}

int main() {
   string s = "(()())()";
   cout << "Input string: " << s << endl;
   cout << "Minimum removals (Dynamic Programming): " << countRemovalsDP(s) << endl;
   return 0;
}

Output

Input string: (()())()
Minimum removals (Dynamic Programming): 0

KESIMPULAN

Konsep asas bahasa C, seperti apakah perbezaan antara jenis data aksara dan rentetan, pembatas rentetan, cara memulakan rentetan dan tatasusunan, pengiraan kedudukan di mana aksara pertama tatasusunan ialah indeks 0 dan digunakan dalam atur cara ini Aksara terakhir mesti kosong untuk mendapatkan output yang betul.

Penghapusan kurungan dalam program dicapai dengan melaksanakan konsep asas dan mudah pengaturcaraan C.

Atas ialah kandungan terperinci Kira bilangan pasangan yang perlu dikeluarkan supaya semua urutan kurungan seimbang kosong. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!