Tutorial — Khôi phục cấu trúc

Vì các thao tác chỉ được phép thay thế ký hiệu mở thành ký hiệu mở và ký hiệu đóng thành ký hiệu đóng, vị trí của các ký hiệu mở và đóng trong chuỗi là hoàn toàn cố định. Do đó, một chuỗi chỉ có thể biến đổi thành chuỗi lồng hợp lệ nếu cấu trúc vị trí mở và đóng của nó vốn đã thỏa mãn dạng một dãy ngoặc chuẩn.

Trong một dãy ngoặc chuẩn, mỗi ký hiệu đóng chỉ có duy nhất một ký hiệu mở tương ứng ghép đôi với nó theo quy tắc đóng mở lồng nhau. Vì mỗi cặp ghép đôi độc lập với các cặp khác, chi phí tối thiểu để biến đổi chuỗi chính là số lượng cặp ghép có loại ký hiệu không trùng khớp nhau.

Sử dụng một ngăn xếp để lưu các ký hiệu mở khi duyệt chuỗi từ trái sang phải. Khi gặp một ký hiệu đóng, ta lấy ký hiệu mở gần nhất trên đỉnh ngăn xếp ra để ghép cặp và tăng biến đếm nếu hai ký hiệu khác loại, hoặc thông báo `Impossible` nếu ngăn xếp rỗng.