Bài viết này sẽ hướng dẫn bạn cách phát hiện liệu một biểu thức có dấu ngoặc hợp lệ hay không bằng cách sử dụng cấu trúc dữ liệu Ngăn xếp. Phương pháp này đặc biệt hữu ích khi bạn cần phân tích cú pháp hoặc xác thực các biểu thức toán học.
Lấy một ví dụ về việc viết trình thông dịch Lisp (cụ thể là cho ngôn ngữ Scheme), có nhiều người sẽ sử dụng dấu ngoặc vuông thay cho dấu ngoặc đơn. Lý do là bởi trong một số tài liệu hướng dẫn về ngôn ngữ Scheme có sử dụng ngoặc vuông thay vì ngoặc đơn.
Tuy nhiên, vì không muốn làm cho trình phân tích cú pháp quá phức tạp mà có thể sẽ có người bỏ qua việc kiểm tra các cặp dấu ngoặc có khớp nhau hay không.
VD:
(let [(x 10]) [+ x x)]
Đoạn mã trên là một ví dụ về S-Expression, trong đó chúng ta có các token, là một chuỗi các ký tự có ý nghĩa (như let hoặc số 10), và dấu ngoặc đơn/dấu ngoặc vuông. Tuy nhiên, mã này không hợp lệ vì nó trộn lẫn các cặp dấu ngoặc đơn và dấu ngoặc vuông.
Vậy thì phải sửa lại thế nào cho đúng?
(let [(x 10)] [+ x x])
Đây là cú pháp Lisp chính xác (nếu dấu ngoặc vuông được hỗ trợ), trong đó dấu ngoặc đơn mở luôn khớp với dấu ngoặc đơn đóng và dấu ngoặc vuông mở luôn khớp với dấu ngoặc vuông đóng.
Trong bài viết này, tôi sẽ chỉ cho bạn cách phát hiện xem đầu vào có phải là S-Expression hợp lệ thứ hai hay không chứ không phải là S-Expression không hợp lệ đầu tiên.
Một trường hợp khác:
(define foo 10))))
Trong đoạn mã trên, bạn thấy cú pháp không hợp lệ với nhiều dấu ngoặc đơn đóng hơn dấu ngoặc đơn mở.
Nói một cách đơn giản, chúng ta sẽ phát hiện xem các cặp ký tự mở và đóng như (), [] và có khớp nhau trong chuỗi như "[foo () bar ]" hay không.
Giải pháp cho vấn đề này có thể hữu ích khi triển khai trình phân tích cú pháp Lisp, nhưng bạn cũng có thể sử dụng nó cho các mục đích khác (như một số loại xác thực hoặc một phần của bộ đánh giá biểu thức toán học). Nó cũng là một bài tập hay.
Sử dụng stack để ghép nối với cấu trúc dữ liệu
Bạn có thể nghĩ rằng cách đơn giản nhất để giải quyết vấn đề này là sử dụng Biểu thức chính quy (RegExp). Có thể sử dụng Regex cho các trường hợp đơn giản, nhưng chẳng bao lâu nữa nó sẽ trở nên quá phức tạp và có nhiều vấn đề hơn là giải quyết.
Trên thực tế, cách dễ nhất để ghép nối các ký tự mở và đóng là sử dụng stack. Stack là cấu trúc dữ liệu đơn giản nhất. Chúng ta có hai thao tác cơ bản: đẩy (push) nhằm để thêm một mục vào stack, và lấy ra (pop) nhằm để xóa một mục.
Điều này hoạt động tương tự như một chồng sách. Mục cuối cùng bạn đặt lên stack sẽ là mục đầu tiên mà bạn lấy ra về sau.
Với stack, việc xử lý (phân tích cú pháp) các ký tự có điểm đầu và điểm cuối sẽ dễ dàng hơn, chẳng hạn như thẻ XML hoặc dấu ngoặc đơn.
Ví dụ: giả sử chúng ta có đoạn mã XML này:
<element><item><sub-item>text</sub-item></item></element>
Khi chúng ta sử dụng stack thẻ cuối cùng chúng ta mở (ví dụ: <sub-item> bên trong) sẽ luôn là thẻ đầu tiên chúng ta cần đóng (nếu XML hợp lệ).
Vì vậy, nếu chúng ta sử dụng stack, chúng ta có thể đẩy mục <sub-item> khi chúng ta mở nó và khi chúng ta cần đóng nó, chúng ta có thể lấy nó ra khỏi stack. Chúng ta chỉ cần đảm bảo rằng mục cuối cùng trên ngăn xếp (luôn là thẻ mở) khớp với mục đóng.
Chúng ta sẽ có logic giống hệt với dấu ngoặc đơn.
Lưu ý rằng nếu chúng ta có các thẻ tự đóng XML, chúng ta có thể bỏ qua chúng vì chúng được mở và tự động đóng.
Mảng trong JavaScript có cả hai phương thức (đẩy và lấy ra), vì vậy chúng có thể được sử dụng làm stack. Nhưng sẽ thuận tiện hơn nếu tạo một lớp trừu tượng dưới dạng một lớp, vì vậy chúng ta có thể thêm các phương thức bổ sung như top() và is_empty() dễ đọc hơn.
Nhưng ngay cả khi chúng ta không thêm các phương thức mới, việc tạo các lớp trừu tượng như thế này luôn tốt hơn, vì nó làm cho mã đơn giản và dễ đọc hơn.
Hầu hết các lập trình viên đều biết các cấu trúc dữ liệu phổ biến và sẽ ngay lập tức nhận ra chúng và không cần phải suy nghĩ về chúng. Điều quan trọng nhất với lập trình là quên đi những thứ không liên quan mà được yêu cầu vào bất kỳ thời điểm nào.
class Stack { #data; constructor() { // creating new empty array as hiden property this.#data = []; } push(item) { // push method just use native Array::push() // and add the item at the end of the array this.#data.push(item); } len() { // size of the Stack return this.#data.length; } top() { // sice the items are added at the end // the top of the stack is the last item return this.#data[this.len() - 1]; } pop() { // pop is similar to push and use native Array::pop() // it removes and returns the last item in array return this.#data.pop(); } is_empty() { // this comment shortcut !0 is true // since 0 can is coerced to false return !this.len(); }
}
Đoạn mã trên sử dụng lớp ES6 (ES2015) và thuộc tính riêng tư ES2022.
Thuật toán so khớp dấu ngoặc
Bây giờ tôi sẽ mô tả thuật toán (các bước) cần thiết để phân tích cú pháp các dấu ngoặc đơn.
Chúng ta cần một vòng lặp sẽ đi qua từng token - và tốt nhất là tất cả các token khác nên được loại bỏ trước khi xử lý.
Khi chúng ta có dấu ngoặc đơn mở, chúng ta cần đẩy phần tử đó vào stack. Khi chúng ta có dấu ngoặc đơn đóng, chúng ta cần kiểm tra xem phần tử cuối cùng trên stack có khớp với phần tử chúng ta đang xử lý hay không.
Nếu phần tử khớp, chúng ta sẽ xóa nó khỏi stack. Nếu không, điều đó có nghĩa là chúng ta đã làm rối các dấu ngoặc đơn và chúng ta cần đưa ra một ngoại lệ.
Khi chúng ta có dấu ngoặc vuông đóng, nhưng không có gì trên stack, chúng ta cũng cần đưa ra một ngoại lệ, vì không có dấu ngoặc đơn mở nào khớp với dấu ngoặc đơn đóng mà chúng ta có.
Sau khi kiểm tra tất cả các ký tự (token), nếu còn lại gì đó trên stack, điều đó có nghĩa là chúng ta đã không đóng tất cả các dấu ngoặc đơn. Nhưng trường hợp này là ổn, vì người dùng có thể đang trong quá trình viết. Vì vậy, trong trường hợp này, chúng ta trả về false, không phải là một ngoại lệ.
Nếu stack trống, chúng ta trả về true. Điều này có nghĩa là chúng ta có một biểu thức hoàn chỉnh. Nếu đây là S-Expression, chúng ta có thể sử dụng trình phân tích cú pháp để xử lý nó và chúng ta sẽ không cần phải lo lắng về kết quả không hợp lệ (tất nhiên nếu trình phân tích cú pháp là chính xác).
Sau đây là đoạn mã nguồn của thuật toán:
function balanced(str) { // pairs of matching characters const maching_pairs = { '[': ']', '(': ')', '{': '}' }; const open_tokens = Object.keys(maching_pairs); const brackets = Object.values(maching_pairs).concat(open_tokens); // we filter out what is not our matching characters const tokens = tokenize(str).filter(token => { return 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()) { // there are matching characters on the stack const last = stack.top(); // the last opening character needs to match // the closing bracket we have const closing_token = maching_pairs[last]; if (token === closing_token) { stack.pop(); } else { // the character don't match throw new Error(`Syntax error: missing closing ${closing_token}`); } } else { // this case when we have closing token but no opening one, // becauase the stack is empty throw new Error(`Syntax error: not matched closing ${token}`); } } return stack.is_empty();
}
Đoạn mã trên được triển khai như một phần của trình phân tích cú pháp S-Expression của tôi, nhưng điều duy nhất tôi đã sử dụng từ bài viết đó là hàm tokenize() chia chuỗi thành các token (trong đó token là một đối tượng đơn lẻ như số 123 hoặc một chuỗi "hello"). Nếu bạn muốn xử lý các ký tự, bạn có thể sử dụng str.split(''), vì vậy các token sẽ là một mảng các ký tự.
Mã đơn giản hơn nhiều so với trình phân tích cú pháp S-Expression vì chúng ta không cần xử lý tất cả các token. Nhưng khi chúng ta sử dụng hàm tokenize() từ bài viết trên, chúng ta sẽ có thể kiểm tra đầu vào như sau:
(this "))))")
Bạn có thể tìm thấy mã nguồn đầy đủ (bao gồm cả hàm tokenize()) trên GitHub.
Kết luận
Việc khớp các dấu ngoặc đơn cũng gặp phải vấn đề tương tự như phân tích cú pháp HTML. Như bạn có thể thấy từ đoạn mã trên, đây là một vấn đề đơn giản hơn để giải quyết nếu chúng ta sử dụng ngăn xếp.
Có thể chúng ta có thể viết một Biểu thức chính quy để kiểm tra xem chuỗi ký tự có dấu ngoặc đơn khớp hay không. Nhưng nó sẽ sớm trở nên phức tạp nếu chúng ta có các chuỗi làm token (chuỗi ký tự), như với S-Expression, và các dấu ngoặc đơn bên trong các chuỗi đó sẽ bị bỏ qua. Hóa ra giải pháp thật sự khá đơn giản nếu chúng ta sử dụng các công cụ phù hợp.
Cảm ơn các bạn đã theo dõi.