Trình tự dấu ngoặc thông thường bao gồm dấu ngoặc mở và đóng của một hoặc nhiều loại, với mỗi dấu ngoặc mở có một dấu ngoặc đóng và (trong trường hợp có nhiều loại) loại của chúng không trùng nhau.
SP chính xác:
( ( ) ) ( ) ( )
{ } [ ( ) ] ( )
{ [ ( { } ) ] }
SP không hợp lệ:
) ) ( ( ) ) ( (
{ [ ( ] ) }
( ( ] }
Để kiểm tra xem một chuỗi dấu ngoặc vuông có cùng loại hay không, chỉ cần kiểm tra số dư.
Tức là chúng ta bắt đầu một biến bằng 0 (số dư). Sau đó, chúng tôi chạy qua chuỗi (nếu bạn không biết cách thực hiện việc này - CHẠY, NGỐT LẠI!), Tăng số dư khi nó gặp dấu ngoặc mở và giảm khi nó gặp dấu ngoặc đóng. Nếu ở bất kỳ giai đoạn nào, số dư trở thành số âm hoặc ở cuối số dư không bằng 0, thì trình tự đó là sai.
|
Trong trường hợp có nhiều loại dấu ngoặc, mọi thứ trở nên phức tạp hơn một chút. Chúng tôi tạo một ngăn xếp để hoạt động như biến số dư đó. Điều này là cần thiết vì dấu ngoặc đơn không thể chồng lên nhau. Khi chúng ta đi qua một dòng và gặp một dấu ngoặc đơn mở, chúng ta đẩy nó vào ngăn xếp. Khi chúng tôi gặp một dấu ngoặc nhọn đóng, chúng tôi cố gắng bật dấu ngoặc mở của loại đó ra khỏi ngăn xếp. Nếu một dấu ngoặc nhọn thuộc loại khác nằm trên ngăn xếp, trình tự không hợp lệ. Nếu ngăn xếp không trống ở cuối, trình tự cũng không hợp lệ.
|
Việc tạo các chuỗi dấu ngoặc chính xác diễn ra trực tiếp từ cách kiểm tra được thực hiện - chúng ta chỉ cần thêm các dấu ngoặc mới mà không vi phạm tính chính xác. Điều này được thực hiện bằng phép lặp đệ quy. Nếu bạn không biết anh ấy - BE... à, không, bạn có thể cố gắng hiểu bằng cách đọc thêm. Đây là một mẫu mã cho một loại dấu ngoặc:
#include <vector>
#include <iostream>
sử dụng không gian tên std;
int n; // Nửa chiều dài
véc tơ<ký tự> trả lời; // Câu trả lời của chúng tôi
void rec(int balance) {
if (ans.size() == 2 * n) { // Nếu có, thì chúng tôi xong
cho (int i = 0; i < 2 * n; i++)
cout << ans[i] << " ";
cout << "\n";
}
if (ans.size() + balance + 2 <= n * 2) { // Kiểm tra, chúng tôi chúng ta sẽ đóng dấu ngoặc mở mới
// Bây giờ hãy chú ý tay của bạn: chúng ta không cần tạo một vectơ riêng cho từng chuỗi
ans.push_back('(');
rec(số dư + 1);
ans.pop_back(); // Để hiểu điều này, bạn cần biết về đệ quy. Đầu tiên, chúng tôi thêm một dấu ngoặc đơn vào vectơ, sau đó chúng tôi thực thi lại tất cả mã này.
// Nghĩa là, thêm dấu ngoặc đơn một lần nữa, nếu có thể.
// Và điều này sẽ xảy ra cho đến khi chúng ta bắt đầu bỏ đệ quy - tức là cho đến khi chúng ta đạt được độ dài mong muốn.
// Sau đó, các dấu ngoặc sẽ bắt đầu được gỡ bỏ. Nếu bạn hiểu điều này - tôi xin chúc mừng bạn, bạn thật tuyệt vời.
}
if (balance > 0) { // Nếu chúng tôi có thể đóng một dấu ngoặc, chúng tôi sẽ đóng nó.
ans.push_back(')');
rec(số dư - 1);
ans.pop_back();
}
}
int main()
{
cin>> N;
rec(0);
trả về 0;
}
Và bây giờ là lúc khó khăn - bạn sẽ phải TỰ viết thuật toán cho một số loại dấu ngoặc! Muahahahahahahahahahahahahah!
|