Bài học

Ngăn xếp cơ bản — kiểm tra ngoặc và định giá biểu thức hậu tố

Mục tiêu bài học

Sau bài này, em dùng list của Python làm ngăn xếp — LIFO, vào sau ra trước — để kiểm tra một chuỗi ngoặc nhiều loại lồng nhau có hợp lệ hay không trong $O(n)$ , định giá một biểu thức hậu tố (postfix) bằng ngăn xếp số, và đếm số ngoặc tối thiểu cần thêm để một chuỗi trở nên hợp lệ.

Sau bài này, em dùng `list` của Python làm ngăn xếp — LIFO, vào sau ra trước — để kiểm tra một chuỗi ngoặc nhiều loại lồng nhau có hợp lệ hay không trong $O(n)$, định giá một biểu thức hậu tố (postfix) bằng ngăn xếp số, và đếm số ngoặc tối thiểu cần thêm để một chuỗi trở nên hợp lệ.

Cần nhớ trước

Ở Tin học 10 em đã biết list hỗ trợ append() (thêm vào cuối) và pop() (lấy ra từ cuối). Hai thao tác này đúng là những gì một ngăn xếp cần — bây giờ em dùng chúng có chủ đích: append() = đẩy (push), pop() = lấy đỉnh (pop). Không có công cụ mới, chỉ có cách dùng mới.

Ở Tin học 10 em đã biết `list` hỗ trợ `append()` (thêm vào cuối) và `pop()` (lấy ra từ cuối). Hai thao tác này đúng là những gì một ngăn xếp cần — bây giờ em dùng chúng có chủ đích: `append()` = đẩy (push), `pop()` = lấy đỉnh (pop). Không có công cụ mới, chỉ có cách dùng mới.

So với mức chuẩn: đề chuẩn lớp 10 thường chỉ kiểm tra MỘT loại ngoặc, và nhiều lời giải chỉ đếm số ngoặc mở trừ số ngoặc đóng bằng một biến đếm — sai ngay khi gặp biểu thức có nhiều loại ngoặc lồng nhau, vì phép đếm không phân biệt được [(]) với ([]). Đề HSG cho chuỗi có nhiều loại ngoặc (), [], {} lồng nhau tuỳ ý, và còn yêu cầu định giá biểu thức chứ không chỉ kiểm tra hợp lệ.

So với mức chuẩn: đề chuẩn lớp 10 thường chỉ kiểm tra MỘT loại ngoặc, và nhiều lời giải chỉ đếm số ngoặc mở trừ số ngoặc đóng bằng một biến đếm — sai ngay khi gặp biểu thức có nhiều loại ngoặc lồng nhau, vì phép đếm không phân biệt được `[(])` với `([])`. Đề HSG cho chuỗi có nhiều loại ngoặc `()`, `[]`, `{}` lồng nhau tuỳ ý, và còn yêu cầu định giá biểu thức chứ không chỉ kiểm tra hợp lệ.

Bài toán mở đầu — vì sao đếm số lượng không đủ

Xét chuỗi "([)]". Số ngoặc tròn mở bằng số ngoặc tròn đóng (đều là 1), số ngoặc vuông cũng vậy — nếu chỉ đếm số lượng, chuỗi này có vẻ "cân bằng". Nhưng chuỗi này KHÔNG hợp lệ: ngoặc vuông mở ở vị trí thứ hai chưa kịp đóng thì ngoặc tròn ở vị trí đầu đã đóng trước — sai thứ tự lồng. Bài toán thật sự cần theo dõi không chỉ số lượng mà cả THỨ TỰ: ngoặc nào đang mở, ngoặc nào phải đóng trước. Đó chính xác là điều một ngăn xếp làm tốt — phần tử đẩy vào sau cùng phải được lấy ra trước tiên.

Xét chuỗi `"([)]"`. Số ngoặc tròn mở bằng số ngoặc tròn đóng (đều là 1), số ngoặc vuông cũng vậy — nếu chỉ đếm số lượng, chuỗi này có vẻ "cân bằng". Nhưng chuỗi này KHÔNG hợp lệ: ngoặc vuông mở ở vị trí thứ hai chưa kịp đóng thì ngoặc tròn ở vị trí đầu đã đóng trước — sai thứ tự lồng. Bài toán thật sự cần theo dõi không chỉ số lượng mà cả THỨ TỰ: ngoặc nào đang mở, ngoặc nào phải đóng trước. Đó chính xác là điều một ngăn xếp làm tốt — phần tử đẩy vào sau cùng phải được lấy ra trước tiên.

Ý tưởng cốt lõi — ngăn xếp lưu đúng thứ tự lồng

Duyệt chuỗi từ trái sang phải. Gặp ngoặc MỞ thì đẩy vào ngăn xếp. Gặp ngoặc ĐÓNG thì so sánh với đỉnh ngăn xếp: nếu đỉnh đúng là ngoặc mở tương ứng, lấy nó ra — một cặp vừa khớp; nếu không khớp, hoặc tệ hơn, ngăn xếp đang RỖNG mà đã gặp ngoặc đóng, chuỗi chắc chắn không hợp lệ, dừng ngay tại đó. Cuối cùng, nếu ngăn xếp còn sót phần tử thì vẫn không hợp lệ — còn ngoặc mở nào đó chưa từng được đóng.

Ngăn xếp lưu đúng thứ tự các ngoặc đang chờ đóng — mỗi bước một kí tự.

Ví dụ

Kiểm tra chuỗi ngoặc nhiều loại lồng nhau

1
Đề chuẩn chỉ cho MỘT loại ngoặc và chấp nhận lời giải đếm số lượng. Ở đây có ba loại ngoặc lồng nhau, và một cặp số lượng bằng nhau vẫn có thể sai thứ tự — như "([)]" đã thấy ở phần mở đầu.
2
Ánh xạ mỗi ngoặc đóng tới ngoặc mở tương ứng bằng một dict: {')': '(', ']': '[', '}': '{'}. Đẩy ngoặc mở vào ngăn xếp; gặp ngoặc đóng thì so đỉnh ngăn xếp với giá trị tra trong dict — khớp thì lấy ra, không khớp (hoặc ngăn xếp rỗng) thì trả False ngay.
Ánh xạ mỗi ngoặc đóng tới ngoặc mở tương ứng bằng một `dict`: `{')': '(', ']': '[', '}': '{'}`. Đẩy ngoặc mở vào ngăn xếp; gặp ngoặc đóng thì so đỉnh ngăn xếp với giá trị tra trong `dict` — khớp thì lấy ra, không khớp (hoặc ngăn xếp rỗng) thì trả `False` ngay.
3
```
def is_valid_brackets(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    opens = set(pairs.values())
    stack = []
    for ch in s:
        if ch in opens:
            stack.append(ch)          # ngoặc mở: đẩy vào
        elif ch in pairs:
            # ngoặc đóng: ngăn xếp rỗng HOẶC đỉnh không khớp -> sai
            if not stack or stack.pop() != pairs[ch]:
                return False
        # kí tự khác (chữ, số...): bỏ qua
    return not stack   # còn sót ngoặc mở chưa đóng -> vẫn sai
```
```python def is_valid_brackets(s: str) -> bool: pairs = {')': '(', ']': '[', '}': '{'} opens = set(pairs.values()) stack = [] for ch in s: if ch in opens: stack.append(ch) # ngoặc mở: đẩy vào elif ch in pairs: # ngoặc đóng: ngăn xếp rỗng HOẶC đỉnh không khớp -> sai if not stack or stack.pop() != pairs[ch]: return False # kí tự khác (chữ, số...): bỏ qua return not stack # còn sót ngoặc mở chưa đóng -> vẫn sai ```
4
Với "({[]})": đẩy (, đẩy {, đẩy [, gặp ] khớp [ (lấy ra), gặp } khớp { (lấy ra), gặp ) khớp ( (lấy ra) — ngăn xếp rỗng ở cuối → True. Với "([)]": đẩy (, đẩy [, gặp ) nhưng đỉnh đang là [ — không khớp pairs[')'] == '(' → trả về False ngay tại kí tự thứ ba, không cần đọc tiếp.
Với `"({[]})"`: đẩy `(`, đẩy `{`, đẩy `[`, gặp `]` khớp `[` (lấy ra), gặp `}` khớp `{` (lấy ra), gặp `)` khớp `(` (lấy ra) — ngăn xếp rỗng ở cuối → `True`. Với `"([)]"`: đẩy `(`, đẩy `[`, gặp `)` nhưng đỉnh đang là `[` — không khớp `pairs[')'] == '('` → trả về `False` ngay tại kí tự thứ ba, không cần đọc tiếp.
5
Mỗi kí tự được xử lý đúng một lần — hoặc một lần đẩy vào, hoặc một lần lấy ra, hoặc bị bỏ qua — nên thuật toán chạy trong $O(n)$ thời gian và $O(n)$ bộ nhớ trong trường hợp xấu nhất (toàn ngoặc mở). Vậy is_valid_brackets("({[]})") = True và is_valid_brackets("([)]") = False.
Mỗi kí tự được xử lý đúng một lần — hoặc một lần đẩy vào, hoặc một lần lấy ra, hoặc bị bỏ qua — nên thuật toán chạy trong $O(n)$ thời gian và $O(n)$ bộ nhớ trong trường hợp xấu nhất (toàn ngoặc mở). Vậy `is_valid_brackets("({[]})") = True` và `is_valid_brackets("([)]") = False`.

Ngăn xếp không chỉ dùng để kiểm tra ngoặc. Một biểu thức hậu tố (postfix) — toán tử đứng SAU hai toán hạng của nó, ví dụ 3 4 + nghĩa là $3+4$ — định giá được bằng đúng một ngăn xếp số, không cần biết độ ưu tiên toán tử hay dấu ngoặc nào cả, vì thứ tự viết đã quyết định thứ tự tính.

Ngăn xếp không chỉ dùng để kiểm tra ngoặc. Một biểu thức hậu tố (postfix) — toán tử đứng SAU hai toán hạng của nó, ví dụ `3 4 +` nghĩa là $3+4$ — định giá được bằng đúng một ngăn xếp số, không cần biết độ ưu tiên toán tử hay dấu ngoặc nào cả, vì thứ tự viết đã quyết định thứ tự tính.

Ví dụ

Định giá biểu thức hậu tố bằng ngăn xếp số

1
Đề chuẩn định giá biểu thức TRUNG TỐ quen thuộc, tính từ trái theo độ ưu tiên. Ở đây thứ tự tính đã được "mã hoá" sẵn vào vị trí toán tử — học sinh phải hiểu ĐÚNG quy tắc lấy ra hai số gần nhất rồi mới áp toán tử, chứ không được đọc theo thói quen trung tố.
2
Gặp số thì đẩy vào ngăn xếp. Gặp toán tử thì lấy ra đúng hai số gần nhất — số lấy ra SAU là toán hạng bên trái, số lấy ra TRƯỚC là toán hạng bên phải — áp toán tử rồi đẩy kết quả trở lại ngăn xếp. Hết biểu thức, ngăn xếp chỉ còn đúng một số: đáp số.
3
```
def eval_postfix(tokens: list[str]) -> float:
    stack = []
    for tok in tokens:
        if tok in '+-*/':
            b = stack.pop()   # toán hạng phải (lấy ra sau)
            a = stack.pop()   # toán hạng trái (lấy ra trước)
            if tok == '+': stack.append(a + b)
            elif tok == '-': stack.append(a - b)
            elif tok == '*': stack.append(a * b)
            else: stack.append(a / b)
        else:
            stack.append(float(tok))
    return stack[0]
```
```python def eval_postfix(tokens: list[str]) -> float: stack = [] for tok in tokens: if tok in '+-*/': b = stack.pop() # toán hạng phải (lấy ra sau) a = stack.pop() # toán hạng trái (lấy ra trước) if tok == '+': stack.append(a + b) elif tok == '-': stack.append(a - b) elif tok == '*': stack.append(a * b) else: stack.append(a / b) else: stack.append(float(tok)) return stack[0] ```
4
Với "3 4 + 2 *": đẩy 3, đẩy 4 → ngăn xếp [3, 4]; gặp +, b=4, a=3 → 3+4=7, đẩy lại → [7]; đẩy 2 → [7, 2]; gặp *, b=2, a=7 → 7*2=14, đẩy lại → [14]. Kết quả 14.
Với `"3 4 + 2 *"`: đẩy `3`, đẩy `4` → ngăn xếp `[3, 4]`; gặp `+`, `b=4, a=3` → `3+4=7`, đẩy lại → `[7]`; đẩy `2` → `[7, 2]`; gặp `*`, `b=2, a=7` → `7*2=14`, đẩy lại → `[14]`. Kết quả `14`.
5
Vậy eval_postfix("3 4 + 2 *".split()) = 14. Chú ý thứ tự a, b = stack.pop() lần 2, lần 1 — với phép trừ và chia, đảo thứ tự sẽ ra kết quả sai (xem mục Bẫy thường gặp bên dưới).

Bẫy thường gặp

Ba lỗi học sinh hay mắc: (1) pop khi ngăn xếp đang rỗng — Python sẽ ném lỗi IndexError, nhưng về mặt thuật toán, gặp ngoặc đóng khi ngăn xếp rỗng nghĩa là KHÔNG có ngoặc mở nào để khớp, phải trả False ngay, luôn kiểm tra if not stack trước khi pop. (2) chỉ kiểm tra lúc gặp ngoặc đóng mà quên kiểm tra ngăn xếp RỖNG ở cuối — chuỗi "(((" không bao giờ gặp ngoặc đóng nên vòng lặp trôi qua êm ru, nhưng ngăn xếp còn 3 phần tử ở cuối nghĩa là còn 3 ngoặc mở chưa đóng. (3) với hậu tố, lấy nhầm thứ tự trừ/chia: phải tính a - b, không phải b - a, vì a được đẩy vào TRƯỚC nên nó là toán hạng bên trái.

Ba lỗi học sinh hay mắc: (1) pop khi ngăn xếp đang rỗng — Python sẽ ném lỗi `IndexError`, nhưng về mặt thuật toán, gặp ngoặc đóng khi ngăn xếp rỗng nghĩa là KHÔNG có ngoặc mở nào để khớp, phải trả `False` ngay, luôn kiểm tra `if not stack` trước khi pop. (2) chỉ kiểm tra lúc gặp ngoặc đóng mà quên kiểm tra ngăn xếp RỖNG ở cuối — chuỗi `"((("` không bao giờ gặp ngoặc đóng nên vòng lặp trôi qua êm ru, nhưng ngăn xếp còn 3 phần tử ở cuối nghĩa là còn 3 ngoặc mở chưa đóng. (3) với hậu tố, lấy nhầm thứ tự trừ/chia: phải tính `a - b`, không phải `b - a`, vì `a` được đẩy vào TRƯỚC nên nó là toán hạng bên trái.

Mở rộng dành cho HSG — đếm số ngoặc tối thiểu cần thêm

Mở rộng dành cho HSG: một dạng bài không hỏi "có hợp lệ không" mà hỏi "cần thêm ÍT NHẤT bao nhiêu ngoặc để hợp lệ". Với một loại ngoặc duy nhất (ngoặc tròn), không cần lưu cả ngăn xếp — chỉ cần ĐẾM số ngoặc mở đang "chờ đóng". Gặp ( thì tăng biến đếm; gặp ) thì nếu biến đếm dương, giảm nó đi (khớp được một cặp có sẵn); nếu biến đếm đã bằng 0, dấu ) này THỪA — phải thêm một ( ngay trước nó, cộng vào kết quả. Cuối chuỗi, biến đếm còn lại chính là số dấu ) còn thiếu cho những dấu ( chưa khớp.

Mở rộng dành cho HSG: một dạng bài không hỏi "có hợp lệ không" mà hỏi "cần thêm ÍT NHẤT bao nhiêu ngoặc để hợp lệ". Với một loại ngoặc duy nhất (ngoặc tròn), không cần lưu cả ngăn xếp — chỉ cần ĐẾM số ngoặc mở đang "chờ đóng". Gặp `(` thì tăng biến đếm; gặp `)` thì nếu biến đếm dương, giảm nó đi (khớp được một cặp có sẵn); nếu biến đếm đã bằng 0, dấu `)` này THỪA — phải thêm một `(` ngay trước nó, cộng vào kết quả. Cuối chuỗi, biến đếm còn lại chính là số dấu `)` còn thiếu cho những dấu `(` chưa khớp.

Ví dụ

Đếm số ngoặc tối thiểu cần thêm để chuỗi hợp lệ

1
Bài này không hỏi đúng/sai mà hỏi một CON SỐ — mức độ "gần hợp lệ" của chuỗi. Không thể trả lời chỉ bằng is_valid_brackets.
2
Không cần ngăn xếp thật — chỉ cần một biến đếm open_needed (số ( đang chờ )) và một biến inserts (số ( phải thêm). Kĩ thuật này CHỈ áp dụng được cho một loại ngoặc duy nhất, vì với nhiều loại ngoặc, thứ tự đóng phải đúng nên không thể chỉ đếm.
Không cần ngăn xếp thật — chỉ cần một biến đếm `open_needed` (số `(` đang chờ `)`) và một biến `inserts` (số `(` phải thêm). Kĩ thuật này CHỈ áp dụng được cho một loại ngoặc duy nhất, vì với nhiều loại ngoặc, thứ tự đóng phải đúng nên không thể chỉ đếm.
3
```
def min_insertions_to_balance(s: str) -> int:
    open_needed = 0   # so '(' dang cho ')'
    inserts = 0       # so '(' phai them
    for ch in s:
        if ch == '(':
            open_needed += 1
        elif ch == ')':
            if open_needed > 0:
                open_needed -= 1
            else:
                inserts += 1   # ')' du, them '(' ngay truoc no
    return inserts + open_needed
```
```python def min_insertions_to_balance(s: str) -> int: open_needed = 0 # so '(' dang cho ')' inserts = 0 # so '(' phai them for ch in s: if ch == '(': open_needed += 1 elif ch == ')': if open_needed > 0: open_needed -= 1 else: inserts += 1 # ')' du, them '(' ngay truoc no return inserts + open_needed ```
4
Với ")(()": ) gặp open_needed=0 → inserts=1; ( → open_needed=1; ( → open_needed=2; ) → open_needed=1. Cuối chuỗi: inserts(1) + open_needed(1) = 2.
Với `")(()"`: `)` gặp `open_needed=0` → `inserts=1`; `(` → `open_needed=1`; `(` → `open_needed=2`; `)` → `open_needed=1`. Cuối chuỗi: `inserts(1) + open_needed(1) = 2`.
5
Vậy min_insertions_to_balance(")(()") = 2 — cần thêm một ( trước dấu ) đầu tiên và một ) ở cuối để khớp ( còn dư.
Vậy `min_insertions_to_balance(")(()") = 2` — cần thêm một `(` trước dấu `)` đầu tiên và một `)` ở cuối để khớp `(` còn dư.

Ghi nhớ: ngăn xếp lưu GIÁ TRỊ thô — kí tự ngoặc, con số — là đủ cho hai bài toán này, vì câu hỏi chỉ cần biết "phần tử gần nhất còn đang mở là gì". Bài tiếp theo đặt một câu hỏi khác hẳn: "phần tử LỚN HƠN gần nhất là ai" — để trả lời nhanh, ngăn xếp phải giữ các phần tử theo một THỨ TỰ GIÁ TRỊ nhất định, không còn tuỳ ý nữa.