Hướng dẫn khớp dấu ngoặc trong JavaScript không sử dụng Regex

Giới thiệu

Bài viết này sẽ hướng dẫn bạn cách xác định tính hợp lệ của các dấu ngoặc trong biểu thức JavaScript bằng cách sử dụng cấu trúc dữ liệu Ngăn xếp (Stack). Phương pháp này rất hữu ích trong việc phân tích cú pháp và xác thực các biểu thức toán học, đặc biệt là trong các ngôn ngữ lập trình như Lisp.

Ví dụ về biểu thức không hợp lệ

Khi viết trình thông dịch cho ngôn ngữ Lisp như Scheme, bạn có thể gặp phải cú pháp như sau:

(let [(x 10])
  [+ x x)]

Đoạn mã này không hợp lệ vì nó trộn lẫn dấu ngoặc đơn và dấu ngoặc vuông. Để sửa chữa, nên sử dụng cú pháp sau:

(let [(x 10)]
  [+ x x])

Trong cú pháp Lisp chính xác, mỗi dấu ngoặc mở cần phải có dấu ngoặc đóng tương ứng, ví dụ như dấu ngoặc đơn phải đóng bằng dấu ngoặc đơn, dấu ngoặc vuông phải đóng bằng dấu ngoặc vuông.

Chúng ta cũng có thể xem xét một ví dụ khác:

(define foo 10))))

Đoạn mã trên cho thấy cú pháp không hợp lệ vì số lượng dấu ngoặc đơn đóng nhiều hơn dấu ngoặc đơn mở.

Cách hoạt động của Ngăn xếp (Stack)

Để khớp các dấu ngoặc, cách đơn giản nhất là sử dụng cấu trúc dữ liệu Ngăn xếp. Ngăn xếp hoạt động theo nguyên tắc LIFO (Last In, First Out). Khi gặp một dấu ngoặc mở, chúng ta sẽ đẩy nó vào ngăn xếp. Khi gặp một dấu ngoặc đóng, chúng ta sẽ kiểm tra xem nó có khớp với dấu ngoặc cuối cùng trong ngăn xếp hay không.

Cấu trúc dữ liệu Ngăn xếp trong JavaScript

Mảnh mã dưới đây mô tả cách tạo lớp Ngăn xếp trong JavaScript:

class Stack {
    #data;
    constructor() {
        this.#data = [];
    }
    push(item) {
        this.#data.push(item);
    }
    len() {
        return this.#data.length;
    }
    top() {
        return this.#data[this.len() - 1];
    }
    pop() {
        return this.#data.pop();
    }
    is_empty() {
        return !this.len();
    }
}

Lớp Ngăn xếp mô tả các phương thức thiết yếu để thêm và loại bỏ phần tử, cũng như kiểm tra chiều dài và tình trạng trống của ngăn xếp.

Thuật toán kiểm tra dấu ngoặc

Sau đây là thuật toán để phân tích cú pháp các dấu ngoặc đơn:

1. Loại bỏ các ký tự không liên quan và chỉ giữ lại các dấu ngoặc.
2. Khi gặp một dấu ngoặc mở, đẩy nó vào ngăn xếp.
3. Khi gặp một dấu ngoặc đóng, kiểm tra xem phần tử cuối cùng trên ngăn xếp có khớp với nó không.
4. Nếu khớp, loại bỏ nó khỏi ngăn xếp. Nếu không, phát sinh lỗi.
5. Cuối cùng, nếu ngăn xếp trống thì chúng ta đã có một biểu thức hợp lệ, ngược lại, trả về false.

Dưới đây là đoạn mã minh họa cho thuật toán này:

function balanced(str) {
    const maching_pairs = {
        '[': ']',
        '(': ')',
        '{': '}'
    };
    const open_tokens = Object.keys(maching_pairs);
    const brackets = Object.values(maching_pairs).concat(open_tokens);
    const tokens = tokenize(str).filter(token => brackets.includes(token));
    const stack = new Stack();
    for (const token of tokens) {
        if (open_tokens.includes(token)) {
            stack.push(token);
        } else if (!stack.is_empty()) {
            const last = stack.top();
            const closing_token = maching_pairs[last];
            if (token === closing_token) {
                stack.pop();
            } else {
                throw new Error(`Syntax error: missing closing ${closing_token}`);
            }
        } else {
            throw new Error(`Syntax error: not matched closing ${token}`);
        }
    }
    return stack.is_empty();
}

Hàm tokenize() sẽ chia chuỗi đầu vào thành các token hợp lệ. Bạn có thể tìm thấy mã nguồn đầy đủ của hàm này trên GitHub.

Kết luận

Việc khớp các dấu ngoặc trong JavaScript không chỉ đơn thuần là một bài toán cú pháp. Nó cũng tương tự như phân tích cú pháp HTML. Sử dụng cấu trúc dữ liệu Ngăn xếp giúp đơn giản hóa vấn đề và mang lại mã nguồn rõ ràng, dễ duy trì. Dù có thể sử dụng Biểu thức chính quy cho các trường hợp cơ bản, nhưng với các cấu trúc phức tạp hơn, giải pháp này thực sự là một lựa chọn hợp lý.

Cảm ơn bạn đã đọc bài viết này! Hy vọng nó sẽ hữu ích cho bạn trong việc phát triển và xác thực mã JavaScript của bạn.
source: viblo