Hãy giải thích cách ứng dụng Cấu trúc dữ liệu Ngăn xếp (Stack) để kiểm tra tính hợp lệ của các dấu ngoặc đóng mở trong một chuỗi biểu thức?

Question

Accepted Answer

Ngăn xếp hoạt động theo nguyên lý LIFO (Last In, First Out - Vào sau, Ra trước), cực kỳ thích hợp để kiểm tra các cấu trúc lồng nhau như dấu ngoặc.

Thuật toán:
Khởi tạo một stack rỗng.
Duyệt qua từng ký tự của chuỗi biểu thức từ trái sang phải.
Nếu gặp dấu ngoặc mở ((, [, {), ta đẩy (push) nó vào stack.
Nếu gặp dấu ngoặc đóng (), ], }):
Kiểm tra nếu stack rỗng: Trả về false ngay lập tức (thừa ngoặc đóng).
Lấy phần tử đỉnh stack ra (pop) và kiểm tra xem nó có phải là dấu ngoặc mở tương ứng cùng loại hay không. Nếu không khớp, trả về false.

Sau khi duyệt hết chuỗi, nếu stack trống hoàn toàn thì chuỗi hợp lệ (trả về true). Nếu stack vẫn còn phần tử thì chuỗi không hợp lệ (thừa ngoặc mở, trả về false).

Độ phức tạp: Thời gian O(n) và không gian O(n) cho việc lưu trữ stack.

Hãy giải thích cách ứng dụng Cấu trúc dữ liệu Ngăn xếp (Stack) để kiểm tra tính hợp lệ của các dấu ngoặc đóng mở trong một chuỗi biểu thức?

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi Stacks liên quan cùng chủ đề