Dãy ngoặc đúng

Nguồn: CLUE OJ – Chương 15: Ngăn xếp, Hàng đợi Độ khó: Dễ Ngăn xếp Xâu

Đề bài

TRUEBRACK – Dãy ngoặc đúng.

Một dãy ngoặc đúng sẽ là một dãy ngoặc đúng về số lượng ngoặc đóng, mở, thứ tự ưu tiên ngoặc và tính đúng đắn của một cặp ngoặc đóng, mở.
Ví dụ: {[()]} là một dãy ngoặc đúng vì đảm bảo thứ tự ưu tiên {, [, ( và đủ số cặp ngoặc. Hãy kiểm tra xem một dãy ngoặc cho trước là đúng hay sai.

Dữ liệu vào:

Một dòng duy nhất gồm một xâu $S$ $(1 \le |S| \le 10^5)$ với $|S|$ là độ dài của xâu $S$.
Chắc chắn rằng tất cả các chữ cái trong xâu $S$ chỉ gồm các dấu ngoặc nhọn, vuông, tròn.

Dữ liệu ra:

Một dòng duy nhất, xuất ra Yes nếu $S$ là một dãy ngoặc đúng, ngược lại xuất ra No.

Ví dụ 1 – input

{[()]}

Ví dụ 1 – output

Yes

Ví dụ 2 – input

{}[]()

Ví dụ 2 – output

Yes

Ví dụ 3 – input

{[(])}

Ví dụ 3 – output

No

Hiểu đúng chữ "thứ tự ưu tiên" trong đề

Đề nhắc tới "thứ tự ưu tiên {, [, (" chỉ để giải thích ví dụ {[()]}. Thật ra điều kiện cần kiểm tra chỉ là: mỗi ngoặc đóng phải khớp đúng loại với ngoặc mở gần nhất chưa được đóng, và cuối cùng không còn ngoặc nào thừa. Ví dụ 2 {}[]() cho thấy các cặp ngoặc đứng cạnh nhau theo thứ tự nào cũng được. Mình đã kiểm tra trên bộ test: lời giải theo định nghĩa chuẩn này (không quan tâm loại nào nằm trong loại nào) đúng toàn bộ 100 test.

Lời mở đầu

Đây là bài "kinh điển nhất" để mở đầu chương Ngăn xếp. Mình sẽ đi từ cách nghĩ rất tự nhiên: cứ thấy cặp ngoặc kề nhau khớp thì xoá đi, chạy thật xem nó chậm ở đâu, rồi từ đó thấy vì sao ngăn xếp (stack) lại là công cụ "sinh ra để dành" cho bài này.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 test Ý tưởngLIFO Cách 1O(n²)Cách 2Ngăn xếp O(n)

Bộ testBộ test chính thức có gì?

Test	Độ dài $\|S\|$	Đáp án Yes	Đáp án No	Độ sâu lồng nhau (test Yes)
1 – 30	6 … 20	19	11	1 … 6
31 – 100	100.000 … 100.000	31	39	24.786 … 25.196

Bộ test có 100 test. Đề không chia subtask, nhưng bộ test chia rõ 2 mức: test 1–30 là xâu rất ngắn ($|S| \le 20$), test 31–100 đều có đúng $|S| = 10^5$.
Mọi test đều có độ dài chẵn – nên không có test nào "No" chỉ vì lẻ số ký tự; code phải thực sự kiểm tra khớp loại ngoặc.
Các test "Yes" lớn lồng nhau rất sâu (độ sâu tới hàng chục nghìn, kiểu ([{{{([[((...). Đây chính là kiểu test làm khó Cách 1 bên dưới.

Kết quả chạy thật của từng cách trên từng mức (ô ghi số test đúng):

Mức	Điều kiện	Các test	Cách 1 (C++) xoá cặp kề nhau	Cách 2 (C++) ngăn xếp
Nhỏ	$\|S\| \le 20$	1 – 30	30/30	30/30
Lớn	$\|S\| = 10^5$	31 – 100	25/70	70/70

Ý tưởngNgoặc đóng phải khớp với ngoặc mở GẦN NHẤT

Nhìn ví dụ {[()]}: khi gặp ) thì nó phải ghép với ( ngay trước – ngoặc mở mở sau cùng mà chưa được đóng. Ghép xong thì ] tiếp theo lại ghép với [, rồi } ghép với {. Ngoặc mở sau thì được đóng trước – đúng nguyên tắc "vào sau, ra trước" (LIFO) của ngăn xếp.

Thuật toán ngăn xếp

Duyệt từng ký tự từ trái sang phải:

Gặp ngoặc mở ( [ { → đẩy vào ngăn xếp.
Gặp ngoặc đóng → nếu ngăn xếp rỗng (không có ai để ghép) hoặc đỉnh không cùng loại → No. Ngược lại lấy đỉnh ra (đã ghép xong một cặp).
Duyệt hết mà ngăn xếp vẫn còn ngoặc mở → No. Còn lại → Yes.

Với ví dụ 3 {[(])}: sau khi đẩy { [ (, gặp ] nhưng đỉnh là ( → không khớp → No. Em nhập dãy ngoặc rồi bấm Tiếp để xem ngăn xếp thay đổi thế nào:

Dãy ngoặc S:

Ví dụ nhanh:

Cách 1Xoá dần các cặp kề nhau – O(n²)

Cách nghĩ đầu tiên của nhiều bạn: trong một dãy ngoặc đúng, chắc chắn có một cặp (), [] hoặc {} đứng kề nhau (cặp trong cùng). Xoá cặp đó đi thì phần còn lại vẫn là dãy ngoặc đúng. Vậy cứ lặp lại: tìm một cặp kề nhau khớp → xoá. Khi không xoá được nữa, nếu xâu rỗng thì Yes, còn sót ký tự thì No.

C++▶ Chạy tay từng dòng codeCách 1: lặp lại việc tìm một cặp ngoặc kề nhau khớp rồi xoá – O(n²).

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

Biến changed ghi nhớ lượt vừa rồi có xoá được gì không; không xoá được nữa thì dừng vòng while.
Mỗi lần xoá xong ta break và tìm lại từ đầu xâu – mỗi lượt tốn $O(n)$ cho việc tìm và erase. Có tới $n/2$ cặp phải xoá → tổng $O(n^2)$.
Bản Python dùng replace xoá tất cả cặp kề nhau trong một lượt (nhanh hơn), nhưng với xâu lồng sâu kiểu ((((...)))) mỗi lượt chỉ xoá được đúng 1 cặp → vẫn là $O(n^2)$.

Không gian$O(n)$

Thời gian$O(n^2)$

Kết quả chạy thật: bản C++ đúng 55/100 test (quá 1 giây ở 45 test: 31–33, 36, 38–40, 43, 45, 48, 50, 54, 56–57, 60–62, 64–65, 67–72, 74–75, 77, 79, 82, 84–86, 89–100), test đúng chạy lâu nhất 0.996s; bản Python đúng 69/100 test (quá thời gian ở 31 test: 31–33, 36, 40, 43, 45, 48, 54, 56, 60, 62, 65, 69–71, 74–75, 79, 82, 85–86, 90–91, 94–100), lâu nhất 0.031s.

Các test bị quá thời gian chủ yếu là các test "Yes" lồng sâu, hoặc test "No" mà lỗi nằm ở rất xa phía sau – lúc đó máy phải xoá hàng chục nghìn cặp trước khi kết luận. Test 1–30 thì quá nhẹ. Thú vị là bản Python lại đúng nhiều test hơn bản C++: mỗi lượt nó xoá mọi cặp kề nhau cùng lúc và hàm replace chạy ở tốc độ của C, nên với các xâu không lồng quá sâu số lượt ít hơn hẳn. Nhưng gặp xâu lồng sâu thì cả hai đều chịu.

Cách 2Ngăn xếp – O(n)

Cài đặt đúng thuật toán ở phần ý tưởng. Hàm moTuongUng(c) trả về ngoặc mở cùng loại với ngoặc đóng c để so với đỉnh ngăn xếp.

C++▶ Chạy tay từng dòng codeCách 2: ngăn xếp chứa các ngoặc mở chưa được đóng – O(n).

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

Điều kiện st.empty() || st.top() != moTuongUng(c): phải kiểm tra st.empty() trước, vì gọi st.top() trên ngăn xếp rỗng là lỗi (chương trình có thể bị dừng đột ngột). Nhờ || "ngắt mạch", khi ngăn xếp rỗng máy không gọi top() nữa.
Gặp lỗi là break luôn, không cần duyệt tiếp.
Dòng if(!st.empty()) ok = false; bắt trường hợp thừa ngoặc mở, ví dụ (() hay {[. Hay bị quên lắm nha!

Không gian$O(n)$

Thời gian$O(n)$

Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.004s; bản Python đúng 100/100 test, lâu nhất 0.029s.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất (test đúng)	Ghi chú
1. Xoá cặp kề nhau	C++	55/100	0.996s	Quá thời gian ở 45 test: 31–33, 36, 38–40, 43, 45, 48, 50, 54, 56–57, 60–62, 64–65, 67–72, 74–75, 77, 79, 82, 84–86, 89–100
	Python	69/100	0.031s	Quá thời gian ở 31 test: 31–33, 36, 40, 43, 45, 48, 54, 56, 60, 62, 65, 69–71, 74–75, 79, 82, 85–86, 90–91, 94–100
2. Ngăn xếp	C++	100/100	0.004s	Full điểm
	Python	100/100	0.029s	Full điểm

Ghi chú của mình: thời gian trong bảng là thời gian CPU đo trên máy của mình (giới hạn 1 giây/test). Cách 2 full điểm với cả C++ lẫn Python và chạy chưa tới vài phần trăm giây. Mẹo nhớ: thấy bài "ghép cặp, cái mở sau phải đóng trước" là nghĩ ngay tới ngăn xếp. Bài sau trong chương – Xâu con hợp lệ dài nhất – sẽ dùng lại đúng ý tưởng này nhưng cất chỉ số vào ngăn xếp thay vì ký tự.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Lập Trình Thuật Toán