Một dãy ngoặc đúng là một xâu ký tự được định nghĩa đệ quy như sau:
Xâu rỗng (không có ký tự nào) là một dãy ngoặc đúng
Nếu là một dãy ngoặc đúng thì cũng là một dãy ngoặc đúng, ở đây là xâu tạo thành bằng cách chèn thêm ký tự vào đầu và ký tự vào cuối xâu
Nếu và là hai dãy ngoặc đúng thì cũng là một dãy ngoặc đúng, ở đây là xâu tạo thành bằng cách nối xâu vào cuối xâu
Những xâu ký tự không thể xây dựng được theo quy tắc trên không phải là dãy ngoặc đúng.
Với một xâu ký tự chỉ gồm các ký tự , ta gọi trọng số của xâu đó là số ký tự ít nhất cần chèn thêm vào xâu ở các vị trí hợp lý để ta thu được một dãy ngoặc đúng. Ví dụ trọng số của xâu ((() cũng như xâu ())(() đều là vì chúng cần chèn thêm ít nhất ký tự mới trở thành dãy ngoặc đúng. Dưới đây là một trong những phương án chèn: ((()()()(); ())(()(())(()).
Cho xâu ký tự chỉ gồm các ký tự (chú ý là các ký tự trong xâu đánh số từ trở đi), người ta thực hiện tuần tự lệnh (đánh số từ tới ) thuộc một trong ba loại:
: Đảo ký tự từ ký tự thành ký tự và ngược lại
: Cho biết trọng số của xâu con gồm các ký tự liên tiếp
: Phục hồi lại xâu như tình trạng trước khi thực hiện lệnh thứ ( là một số nguyên dương nhỏ hơn hoặc bằng chỉ số lệnh hiện tại)
Yêu cầu: Hãy mô phỏng quá trình thực hiện lệnh và cho biết câu trả lời cho các lệnh
Dữ liệu vào:
Dòng đầu chứa xâu gồm không quá ký tự
Dòng thứ hai chứa số nguyên dương là số lệnh
dòng tiếp theo chứa thông tin về một lệnh theo mô tả trên.
Dữ liệu ra:
Với mỗi lệnh , ghi ra một số nguyên duy nhất trên một dòng là câu trả lời cho lệnh đó.
Ví dụ:
Dữ liệu vào:
((()))
10
C 1
Q 2 5
C 5
Q 1 6
U 3
C 4
Q 3 6
U 5
C 1
Q 1 5
