Biểu thức cân bằng của dấu ngoặc là một biểu thức chứa các cặp dấu ngoặc đơn với nhau theo một thứ tự đúng. điều này có nghĩa là đối với mọi dấu ngoặc đơn mở, có một dấu ngoặc đơn đóng theo thứ tự thích hợp của dấu ngoặc đơn, tức là {}.
Biểu thức - {([] [] {}) ({} [] {})}
Đầu ra - cân bằng
Bây giờ, trong bài toán này, chúng ta phải tạo tất cả các biểu thức cân bằng có thể có từ số lượng dấu ngoặc đã cho và điều kiện là vị trí đã cho có dấu ngoặc mở.
Trong bài toán này, chúng ta được cung cấp một số nguyên n và một mảng vị trí của các dấu ngoặc có độ dài 2n và chúng ta phải tìm số biểu thức cân bằng có độ dài 2n sao cho các vị trí được đánh dấu bởi dấu ngoặc mở sẽ có dấu ngoặc mở ' {'.
Ví dụ -
Input : n = 2 , position [1, 0 , 0 , 0].
Output : 2
Explanation : All possible outcomes are : {{}} , {}{}. THUẬT TOÁN
-
Tất cả các vị trí có một là dấu ngoặc mở.
-
Sử dụng vòng lặp đệ quy bằng các quy tắc sau,
-
Nếu (số lượng dấu ngoặc mở - số lượng dấu ngoặc đóng)> 0, trả về 0.
-
Sau khi lặp lại cho đến n và nếu tổng số dấu ngoặc sau khi đẩy và bật là 0, thì trả về 1 tức là độ phân giải thu được. Nếu không thì trả về 0.
-
Nếu 1 được gán trước cho biểu thức, hãy gọi đệ quy khi tăng chỉ số và tăng tổng số dấu ngoặc.
-
Nếu không, hãy gọi hàm một cách đệ quy bằng cách chèn dấu ngoặc mở vào vị trí chỉ mục, sau đó chèn dấu ngoặc đóng cho nó và giảm tổng số dấu ngoặc và chuyển sang chỉ mục tiếp theo.
-
CHƯƠNG TRÌNH
#include <bits/stdc++.h>
using namespace std;
int find(int index, int openbrk, int n, int expression[]){
if (openbrk < 0)
return 0;
if (index == n){
if (openbrk == 0)
return 1;
else
return 0;
}
if (expression[index] == 1) {
return find(index + 1, openbrk + 1, n, expression);
} else {
return find(index + 1, openbrk + 1, n, expression) + find(index + 1, openbrk - 1, n, expression);
}
}
int main() {
int n = 3;
int expression[6] = { 1, 0, 1, 0, 0, 0};
cout << find(0, 0, 2 * n, expression) <<endl;
return 0;
}