Một biểu thức cân bằng của ngoặc là biểu thức chứa cặp ngoặc đúng thứ tự. Điều này có nghĩa là với mỗi ngoặc mở có một ngoặc đóng theo thứ tự đúng.
Biểu thức - {([][]{})({}[]{})}
Kết quả - cân bằng
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ể từ số lượng ngoặc cho trước. Và điều kiện là các vị trí cho trước phải có ngoặc mở.
Cho số nguyên n và mảng vị trí ngoặc độ dài 2n, tìm số biểu thức cân bằng độ dài 2n sao cho các vị trí được đánh dấu bằng 1 sẽ có ngoặc mở '{'.
Ví dụ
Đầu vào: n = 2, position [1, 0, 0, 0]
Đầu ra: 2
Giải thích: Tất cả kết quả có thể: {{}}, {}{}.
THUẬT TOÁN
- Tất cả vị trí có giá trị 1 là ngoặc mở.
- Sử dụng vòng lặp đệ quy với các quy tắc sau:
- Nếu (số ngoặc mở - số ngoặc đóng) < 0, trả về 0.
- Sau khi lặp đến n và nếu tổng ngoặc sau push/pop là 0, trả về 1 (tìm thấy giải pháp). Ngược lại trả về 0.
- Nếu 1 được gán trước cho biểu thức, gọi đệ quy tăng chỉ số và tăng tổng ngoặc.
- Ngược lại, gọi hàm đệ quy bằng cách chèn ngoặc mở tại vị trí chỉ số và sau đó chèn ngoặc đóng cho nó, giảm tổng ngoặc và chuyển sang chỉ số 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;
}
Kết quả đầu ra
3