Đếm số cặp chuỗi dấu ngoặc đơn sao cho dấu ngoặc đơn là cân bằng trong C ++

Chúng ta được cung cấp một chuỗi chứa các dấu ngoặc đơn và nhiệm vụ là tính toán số lượng các cặp chuỗi ngoặc đơn có thể được tạo thành sao cho các dấu ngoặc đơn là cân bằng.

Dấu ngoặc đơn được cho là cân bằng khi có số lượng dấu ngoặc đóng và mở bằng nhau. Dấu ngoặc đơn được sử dụng một lần không thể được coi là hai lần để tạo thành cặp.

Đầu vào - string paran [] ={") () ())", "(", ") (", ") (", ")"}

Đầu ra - Số cặp dấu ngoặc đơn sao cho các cặp dấu ngoặc đơn là:1

Giải thích - chúng tôi sẽ lấy mọi tập hợp của chuỗi để tính toán tốt hơn. Cho phép lấy phần tử đầu tiên là “) () ())” trong đó có 4 dấu ngoặc đóng và 2 dấu ngoặc mở, vì vậy chúng ta sẽ tìm phần tử tiếp theo trong chuỗi có chứa chính xác 2 dấu ngoặc đóng để tạo chuỗi dấu ngoặc cân bằng không ở đó trong chuỗi, vì vậy chúng tôi sẽ loại bỏ nó và chuyển sang bước tiếp theo. Vì vậy, cặp hợp lệ có dấu ngoặc mở và đóng bằng nhau ở (2, 5) do đó số lượng là 1.

Đầu vào - string paran [] ={") () ())", "((", "(", ") (", ") (", ")"}

Đầu ra - Số cặp dấu ngoặc đơn sao cho các cặp dấu ngoặc đơn là:1

Giải thích - Các cặp dấu ngoặc đơn cân đối hợp lệ là (1, 2) và (3, 6). Do đó số lượng là 2.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Nhập chuỗi và tính độ dài của chuỗi bằng cách sử dụng hàm length () và chuyển dữ liệu cho hàm để xử lý thêm.
Lấy một số lượng biến tạm thời để lưu trữ các cặp dấu ngoặc đơn hợp lệ và tạo biến um_1 và um_2 thuộc loại unsrdered_map.
Bắt đầu một vòng lặp FOR khác từ 0 cho đến khi có kích thước bằng một chuỗi
Bên trong vòng lặp, đặt str dưới dạng paran [i] tức là phần tử đầu tiên của dấu ngoặc đơn và tính toán lại độ dài của một chuỗi.
Lấy một biến tạm thời làm đầu tiên và cuối cùng và khởi tạo chúng bằng 0
Bắt đầu một vòng lặp FOR khác từ j đến 0 cho đến hết độ dài của một chuỗi
Bên trong vòng lặp, kiểm tra IF str [j] =‘(‘ sau đó tăng giá trị đầu tiên lên 1 ELSE kiểm tra IF đầu tiên =1 sau đó giảm giá trị đầu tiên bằng 1 ELSE tăng số lượng cuối cùng là 1.
Bây giờ kiểm tra IF đầu tiên là 1 và cuối cùng là 0, sau đó đặt um_1 [đầu tiên] ++ và kiểm tra IF cuối cùng là 1 và đầu tiên là 0 sau đó đặt um_2 [lst] ++ và IF đầu tiên là 0 và cuối cùng cũng là 0 sau đó tăng số lượng bởi 1.
Đặt số lượng là số lượng / 2
Bắt đầu vòng lặp từ 0 đến um_1 và đặt số đếm là giá trị nhỏ nhất từ um_1.second và um_2.first
Trả lại số lượng
In kết quả.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int parentheses(string paran[], int size){
   int count = 0;
   unordered_map<int, int> um_1, um_2;
   for (int i = 0; i < size; i++){
      string str = paran[i];
      int len = str.length();
      int first = 0;
      int last = 0;
      for (int j = 0; j < len; j++){
         if (str[j] == '('){
            first++;
         }
         else{
            if (first==1){
               first--;
            }
            else{
               last++;
            }
         }
      }
      if(first==1 && last!=1){
         um_1[first]++;
      }
      if (last==1 && first!=1){
         um_2[last]++;
      }
      if(first!=1 && last!=1){
         count++;
      }
   }
   count = count / 2;
   for (auto it : um_1){
      count += min(it.second, um_2[it.first]);
   }
   return count;
}
int main(){
   string paran[] = { ")()())", "(", ")(", ")(", ")"};
   int size = sizeof(paran) / sizeof(paran[0]);
   cout<<"Count of pairs of parentheses sequences such that parentheses are balanced are:
"<<parentheses(paran, size);
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Count of pairs of parentheses sequences such that parentheses are balanced are: 1