Cấu trúc dữ liệu và Giải thuật Bài 34: Ứng dụng Stack: Kiểm tra chuỗi dấu ngoặc hợp lệ (Valid Parentheses).

Bất cứ khi nào bạn viết code bằng Golang, PHP hay C++ và vô tình quên đóng một dấu ngoặc nhọn }, ngay lập tức trình biên dịch (Compiler) hoặc IDE (như VS Code) sẽ bôi đỏ dòng code đó và báo lỗi Syntax Error. Hoặc khi bạn gửi một payload JSON lên API, backend ngay lập tức từ chối vì cấu trúc JSON bị thiếu dấu ngoặc vuông ].

Hệ thống đã làm cách nào để quét qua hàng ngàn dòng text và phát hiện ra sự bất hợp lý đó trong chớp mắt? Thuật toán đằng sau tính năng này chính là Valid Parentheses (Kiểm tra chuỗi dấu ngoặc hợp lệ) – bài toán kinh điển top 1 của cấu trúc Stack (LeetCode 20).

1. Cái bẫy của tư duy "Đếm số lượng"

Yêu cầu bài toán: Cho một chuỗi chỉ chứa 6 loại ký tự: (, ), {, }, [ và ]. Một chuỗi được xem là hợp lệ nếu:

1. Các dấu ngoặc mở phải được đóng bởi dấu ngoặc đóng cùng loại.

2. Các dấu ngoặc mở phải được đóng theo đúng thứ tự.

Nếu chỉ đọc lướt qua, phản xạ của người mới học là dùng 3 biến đếm (Counters) cho 3 loại ngoặc: Cứ gặp ngoặc mở thì tăng biến đếm lên 1, gặp ngoặc đóng thì giảm đi 1. Cuối cùng, nếu cả 3 biến đều bằng 0 thì chuỗi hợp lệ.

Sự sụp đổ của biến đếm:

Hãy thử chuỗi này: [(])

Nếu đếm, chúng ta có 1 ngoặc vuông và 1 ngoặc tròn. Kết quả bằng 0. Nhưng rõ ràng chuỗi này sai cú pháp vì ngoặc vuông [ bị đóng bởi ngoặc tròn ) nằm đan chéo nhau. Tư duy biến đếm hoàn toàn bất lực trước yêu cầu về "Thứ tự".

2. LIFO: Chiếc chìa khóa giải mã trật tự

Nhìn kỹ lại quy luật của ngôn ngữ lập trình, bạn sẽ nhận ra một nguyên lý tối thượng: Dấu ngoặc nào được mở ra SAU CÙNG, bắt buộc phải được đóng lại ĐẦU TIÊN.

Ví dụ: Trong chuỗi { [ ( ) ] }, dấu ( được mở cuối cùng, nên nó phải gặp dấu ) đầu tiên. Tiếp theo mới đến [, và cuối cùng là {.

Vào sau $\rightarrow$ Ra trước. Đây chính xác là định nghĩa vật lý của Stack (Ngăn xếp - LIFO).

Quy trình quét chuỗi bằng Stack:

1. Duyệt qua từng ký tự của chuỗi từ trái sang phải.

2. Nếu gặp dấu ngoặc MỞ: Đẩy (Push) nó vào Stack.

3. Nếu gặp dấu ngoặc ĐÓNG:

   • Kiểm tra Stack. Nếu Stack đang rỗng, chứng tỏ có dấu ngoặc đóng bị thừa (Ví dụ: ]). Chuỗi không hợp lệ.

   • Nếu Stack không rỗng, Lấy (Pop) phần tử trên đỉnh Stack ra. Kiểm tra xem phần tử vừa Pop ra có "khớp" (cùng loại) với dấu ngoặc đóng hiện tại không. Nếu không khớp (Ví dụ: Đỉnh là (, nhưng hiện tại là ]), chuỗi không hợp lệ.

4. Sau khi duyệt hết chuỗi, Stack phải ở trạng thái Rỗng. Nếu trong Stack vẫn còn sót lại phần tử, chứng tỏ có dấu ngoặc mở nhưng chưa bao giờ được đóng (Ví dụ: (()). Chuỗi không hợp lệ.

3. Triển khai thuật toán bằng Golang

Để mã nguồn thanh lịch và loại bỏ các câu lệnh if-else dài dòng, chúng ta sử dụng một Bảng băm (map) để thiết lập sẵn từ điển ghép cặp giữa ngoặc đóng và ngoặc mở.

Go

func isValid(s string) bool {
    // Nếu độ dài chuỗi là số lẻ, chắc chắn không thể ghép cặp hoàn hảo
    if len(s) % 2 != 0 {
        return false
    }

    // Khởi tạo Stack bằng một Slice
    stack := []rune{}
    
    // Từ điển ghép cặp: Key là ngoặc đóng, Value là ngoặc mở tương ứng
    bracketsMap := map[rune]rune{
        ')': '(',
        ']': '[',
        '}': '{',
    }

    for _, char := range s {
        // Nếu ký tự hiện tại có trong keys của map -> Nó là ngoặc ĐÓNG
        if matchingOpen, isClose := bracketsMap[char]; isClose {
            // Kiểm tra Stack rỗng hoặc đỉnh Stack không khớp với ngoặc mở tương ứng
            if len(stack) == 0 || stack[len(stack)-1] != matchingOpen {
                return false
            }
            // Khớp thành công, Pop phần tử trên đỉnh ra khỏi Stack
            stack = stack[:len(stack)-1]
        } else {
            // Nếu không có trong keys của map -> Nó là ngoặc MỞ -> Push vào Stack
            stack = append(stack, char)
        }
    }

    // Cuối cùng, Stack phải rỗng hoàn toàn
    return len(stack) == 0
}

• Độ phức tạp thời gian: $O(n)$ vì chúng ta chỉ duyệt qua chuỗi đúng 1 lần. Thao tác Push, Pop và tra cứu Map đều tốn thời gian $O(1)$.

• Độ phức tạp không gian: $O(n)$ trong trường hợp xấu nhất (chuỗi toàn dấu ngoặc mở như (((((, Stack sẽ chứa toàn bộ chuỗi).

4. Ứng dụng ở tầng Kiến trúc Hệ thống

Bài toán Valid Parentheses không chỉ dừng lại ở bài tập vỡ lòng. Logic đằng sau nó là lõi của các module phân tích cú pháp khổng lồ:

• Trình phân tích cú pháp JSON (JSON Parser): Khi bạn dùng hàm json.Unmarshal() trong Golang, bộ phân tích cú pháp (Parser) bên dưới sử dụng chính cơ chế Stack này để kiểm tra xem cấu trúc lồng nhau của các Object {} và Array [] có hợp lệ hay không trước khi chuyển đổi chúng thành Struct.

• AST (Abstract Syntax Tree): Các trình biên dịch (như Go Compiler, V8 Engine của Node.js) khi đọc mã nguồn của bạn, bước đầu tiên (Lexical Analysis & Syntax Analysis) là dùng Stack để gom nhóm các khối lệnh (Code Blocks) nằm giữa các dấu ngoặc nhọn { } lại với nhau để tạo thành cấu trúc cây.

• Máy tính biểu thức toán học: Hệ thống dùng Stack để ưu tiên tính toán các phép toán nằm sâu bên trong dấu ngoặc đơn ( ) trước khi xử lý các phép tính bên ngoài.

Qua bài học này, bạn đã thấy khả năng "nhớ lại quá khứ gần nhất" của Stack giải quyết bài toán lồng ghép một cách hoàn hảo. Nhưng sức mạnh của Stack chưa dừng lại ở đó. Nếu chúng ta kết hợp Stack với một quy luật so sánh khắt khe (ví dụ: các phần tử trong Stack luôn phải tăng dần hoặc giảm dần), chúng ta sẽ tạo ra được một cỗ máy thời gian dự đoán được tương lai.