Bài tập về cơ chế Stack kiểm tra chuỗi cho trước có phải là một chuỗi đối xứng hay không

[Phong_nguyen_dang]

Tình hình là e đag học CSDL và giải thuật có Bt về chơ chế Stack , mà e ko hiếu mấy nên nhờ ace làm giúp để dễ hiểu hơn

Vận dụng cơ chế Stack để xây dựng giải thuật kiểm tra chuối St cho trước có phải là một chuỗi đối xứng hay ko?

thanks

[Gio (Gió)]

Giả sử 1 chuỗi có các kí tự là a₁,a₂…a_n. Khi đó push vào stack đúng theo thứ tự đó nên khi lấy ra các kí tự sẽ dc lấy theo thứ tự a_n…a₁. Như đã biết thì chuỗi đối xứng là đọc xuôi giống đọc theo chiều ngược lại. Mà việc lấy trong stack ra chính là việc đọc ngược đó. Công việc bây giờ chỉ việc lấy các phần tử trong stack xem có giống xâu đã cho hay không.
Cải tiến hơn 1 chút: xâu đôi xứng nếu nữa đầu = đảo ngược nữa cuối nên chỉ cần push vào stack 1/2 chuỗi và so sánh 1/2 chuỗi còn lại

[reoteu_ray]

stack thì áp dụng để làm mấy bài tập về tiền tố , hậu tố và cây rất hay …