programming python

Thêm dấu ngoặc đơn vào chuỗi Python

Đưa ra một chuỗi dấu ngoặc đơn, việc kiểm tra xem tổ hợp dấu ngoặc đơn có hợp lệ hay không là một câu hỏi phỏng vấn mã hóa phổ biến. Và trong vài phút tới, bạn sẽ học kỹ thuật để giải quyết câu hỏi này, đồng thời viết mã một hàm Python để xác thực một chuỗi đã cho

Vấn đề dấu ngoặc đơn hợp lệ là gì?

Hãy bắt đầu cuộc thảo luận của chúng ta bằng cách trả lời câu hỏi, vấn đề về dấu ngoặc đơn hợp lệ là gì?

Cho một chuỗi chứa các ký tự dấu ngoặc đơn, dấu ngoặc nhọn và dấu ngoặc vuông.
# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"
4, bạn phải kiểm tra xem tổ hợp dấu ngoặc đã cho có hợp lệ hay không

Một chuỗi dấu ngoặc đơn hợp lệ thỏa mãn hai điều kiện sau

Mỗi dấu ngoặc mở phải có một dấu ngoặc đóng phù hợp cùng loại
Các dấu ngoặc phải được đóng theo đúng thứ tự

Dưới đây là một vài ví dụ về chuỗi dấu ngoặc đơn hợp lệ và không hợp lệ

test_str = "{}]" --> INVALID, ] was never opened
test_str = "[{}]" --> VALID
test_str = "[]" --> VALID
test_str = "[]{}" --> VALID
test_str = "[{]}" --> INVALID, brackets closed incorrectly!

Theo phương pháp giải quyết vấn đề của chúng tôi, ngăn xếp là cấu trúc dữ liệu sẽ đóng vai trò then chốt. Hãy xem lại kiến thức cơ bản về ngăn xếp trong phần tiếp theo

Cấu trúc dữ liệu ngăn xếp được xem lại

Ngăn xếp là cấu trúc dữ liệu vào sau ra trước [LIFO], trong đó bạn có thể thêm các phần tử vào đầu ngăn xếp và cũng có thể xóa chúng khỏi đầu ngăn xếp

Khi bạn thêm phần tử vào đỉnh ngăn xếp, bạn thực hiện thao tác đẩy, khi bạn xóa phần tử khỏi đỉnh ngăn xếp, bạn thực hiện thao tác bật

Chúng tôi sẽ sử dụng hai quy tắc sau để đưa ra một tập hợp các hoạt động mà chúng tôi có thể thực hiện trên chuỗi dấu ngoặc đơn

Đẩy tất cả các dấu ngoặc mở vào ngăn xếp
Nếu bạn bắt gặp một dấu ngoặc đóng, hãy bật ra khỏi ngăn xếp trên cùng

Hãy tiến hành giải bài toán kiểm tra dấu ngoặc đơn hợp lệ

Kết hợp tất cả các quan sát từ các ví dụ trên, chúng ta có những điều sau đây

Kiểm tra độ dài của chuỗi dấu ngoặc đơn. Nếu lẻ, chuỗi không hợp lệ

Vì mọi dấu ngoặc mở đều phải có dấu ngoặc đóng, nên một chuỗi hợp lệ phải chứa số ký tự chẵn. Nếu độ dài của chuỗi là số lẻ, bạn có thể kết luận ngay nó có tổ hợp dấu ngoặc đơn không hợp lệ

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

Tiếp theo, hãy xem cách chúng ta có thể xử lý khi số lượng ký tự trong chuỗi là số chẵn

Độ dài của chuỗi dấu ngoặc đơn là chẵn. tiếp theo là gì?

Bước 1. Đi qua chuỗi từ trái sang phải. Hãy gọi chuỗi

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

5 và các ký tự riêng lẻ trong chuỗi

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

Bước 2. Nếu ký tự đầu tiên

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

6 là dấu ngoặc mở [, { hoặc [, hãy đẩy ký tự đó lên đầu ngăn xếp và chuyển sang ký tự tiếp theo trong chuỗi

Bước 3. Bây giờ, hãy kiểm tra xem ký tự tiếp theo [

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

6] là dấu ngoặc mở hay đóng

Bước 3. 1. Nếu đó là dấu ngoặc mở, hãy đẩy lại vào ngăn xếp

Bước 3. 2. Thay vào đó, nếu bạn gặp dấu ngoặc đóng, hãy bật ngăn xếp trên cùng và chuyển sang bước 4

Bước 4. Một lần nữa, có 3 khả năng dựa trên giá trị bật ra khỏi ngăn xếp

Bước 4. 1. Nếu là một dấu ngoặc mở cùng loại, lặp lại bước 3

Bước 4. 2. Nếu đó là dấu ngoặc mở thuộc loại khác, bạn có thể kết luận lại rằng đó không phải là chuỗi dấu ngoặc đơn hợp lệ

Bước 4. 3. Khả năng cuối cùng là ngăn xếp trống. Một lần nữa, đây là trường hợp của một chuỗi không hợp lệ, vì bạn đã chạy vào một dấu ngoặc đóng không có dấu ngoặc mở phù hợp

Ví dụ chuỗi dấu ngoặc đơn hợp lệ Hướng dẫn

Bây giờ, hãy lấy ba ví dụ và thực hiện các bước trên

📑 Nếu bạn đã hiểu rõ cách thức hoạt động của tính năng này, vui lòng chuyển sang phần tiếp theo

#1. Như một ví dụ đầu tiên, hãy để

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

0 là ký tự đầu tiên và là dấu ngoặc mở, vì vậy bạn đẩy nó vào ngăn xếp

Ký tự tiếp theo [ cũng là một dấu ngoặc mở, vì vậy hãy tiếp tục và đẩy nó vào ngăn xếp
Ký tự thứ ba trong chuỗi ] là dấu ngoặc đóng, vì vậy bạn phải bật ra khỏi ngăn xếp trên cùng, ký tự này sẽ trả về [
Tại thời điểm này, bạn đã đi đến cuối chuỗi. Nhưng ngăn xếp vẫn chứa phần mở đầu { , không bao giờ được đóng. Vì vậy, chuỗi ngoặc đơn đã cho
```
# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"
```
5 không hợp lệ

#2. Trong ví dụ thứ hai này, hãy để

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

Ký tự đầu tiên

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

3 là dấu ngoặc mở;

Ký tự thứ hai

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

4 là dấu ngoặc đóng; . Chuyển sang ký tự tiếp theo

Ký tự thứ ba

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

5 là dấu ngoặc vuông đóng và bạn nên bật ra khỏi ngăn xếp một lần nữa. Tuy nhiên, như bạn có thể thấy, ngăn xếp trống—có nghĩa là không có dấu ngoặc mở phù hợp

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

6. Do đó, chuỗi này không hợp lệ

#3. Trong ví dụ cuối cùng này,

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

Hai ký tự đầu tiên

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

8 đang mở ngoặc, vì vậy hãy đẩy chúng vào ngăn xếp

Ký tự thứ ba là

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

4 đang đóng, vì vậy hãy bật ra khỏi ngăn xếp trên cùng –

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

Ký tự tiếp theo

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

21 là một dấu ngoặc nhọn đóng và khi bạn bật ngăn xếp lên trên cùng, bạn nhận được

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

0 – một dấu ngoặc nhọn mở

Sau khi bạn đã duyệt qua toàn bộ chuỗi, ngăn xếp trống và

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

5 là hợp lệ. ✅

📌 Tôi đã tổng hợp sơ đồ sau phác thảo các bước trong bài toán kiểm tra dấu ngoặc đơn hợp lệ. Bạn có thể lưu nó để tham khảo nhanh

Trong phần tiếp theo, hãy xem cách dịch khái niệm của chúng ta sang mã Python

Chương trình Python để kiểm tra dấu ngoặc đơn hợp lệ

Trong Python, bạn có thể sử dụng danh sách để mô phỏng ngăn xếp

Bạn có thể sử dụng phương thức

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

24 để thêm phần tử vào cuối danh sách. Điều này tương tự như đẩy lên đỉnh ngăn xếp

Phương thức

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

25 trả về phần tử cuối cùng từ danh sách và điều này tương tự như việc bật ra khỏi đầu ngăn xếp – để xóa phần tử được thêm vào cuối cùng

Vì vậy, bây giờ bạn đã biết cách triển khai các thao tác đẩy và bật trên danh sách Python, mô phỏng ngăn xếp

Bước tiếp theo, hãy trả lời câu hỏi. làm thế nào để phân biệt giữa mở và đóng ngoặc?

Chà, bạn có thể sử dụng từ điển Python - với dấu ngoặc mở

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

26 làm khóa của từ điển và dấu ngoặc đóng tương ứng

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

27 làm giá trị. Bạn có thể sử dụng phương pháp

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

28 để truy cập các khóa riêng lẻ trong từ điển

Hãy sử dụng tất cả những gì chúng ta đã học để viết định nghĩa của hàm

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

Hiểu định nghĩa hàm

Đọc qua ô mã sau có chứa định nghĩa hàm. Bạn có thể thấy rằng chúng tôi đã sử dụng các bước trong lưu đồ song song với phần giải thích ở trên

Ngoài ra, chúng tôi cũng đã thêm một chuỗi tài liệu bao gồm

một mô tả ngắn về chức năng
các đối số trong lời gọi hàm
các giá trị trả về từ hàm

▶ Bạn có thể sử dụng

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

00 hoặc

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

01 để truy xuất chuỗi tài liệu

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

Hàm Python

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

02 kiểm tra xem chuỗi ngoặc đơn có hợp lệ hay không và nó hoạt động như sau

Hàm

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

02 nhận một tham số,

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

5 là chuỗi dấu ngoặc đơn được xác thực. Nó trả về

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

05 hoặc

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

06 tùy thuộc vào việc chuỗi

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

5 có hợp lệ hay không

Ở đây,

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

08 là danh sách Python mô phỏng ngăn xếp

Và

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

09 là từ điển Python, với dấu ngoặc mở là khóa và dấu ngoặc đóng là giá trị tương ứng

Trong khi duyệt chuỗi, nếu chúng ta gặp bất kỳ điều kiện nào khiến chuỗi ngoặc không hợp lệ, hàm sẽ trả về

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

06 và thoát

Sau khi duyệt qua tất cả các ký tự trong chuỗi,

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

41 kiểm tra xem

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

08 có trống không. Nếu có,

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

5 hợp lệ và hàm trả về

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

05. Khác, hàm trả về

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

Bây giờ, hãy tiếp tục và thực hiện một vài lệnh gọi hàm để xác minh rằng hàm của chúng ta hoạt động chính xác

# len[test_str] = 3 [odd]; ] does not have an opening [
test_str = "{}]"

# len[test_str] = 3 [odd]; [ does not have a closing ]
test_str = "[[]"

# len[test_str] = 5 [odd]; there's a spurious ]
test_str = "{[]]}"

Từ đoạn mã trên, chúng tôi có thể kết luận rằng chức năng hoạt động như mong đợi

Phần kết luận

Dưới đây là tóm tắt nhanh về những gì bạn đã học được

Đầu tiên, bạn đã được giới thiệu về vấn đề kiểm tra dấu ngoặc đơn hợp lệ
Tiếp theo, bạn đã học được cách tiếp cận để giải quyết vấn đề bằng cách sử dụng ngăn xếp làm cấu trúc dữ liệu được lựa chọn
Sau đó, bạn đã học cách xác thực kết hợp dấu ngoặc đơn bằng từ điển Python. với dấu ngoặc mở, khóa và dấu ngoặc đóng tương ứng làm giá trị
Cuối cùng, bạn đã định nghĩa hàm Python để kiểm tra xem chuỗi dấu ngoặc đơn đã cho có hợp lệ không

Bước tiếp theo, hãy thử viết mã sự cố trên trình soạn thảo Python trực tuyến của Geekflare. Vui lòng xem lại hướng dẫn này nếu bạn cần trợ giúp

Chúng ta có thể sử dụng dấu ngoặc trong Python không?

Các dấu ngoặc vuông cho Python biết rằng đây là cách hiểu danh sách, tạo ra một danh sách. Nếu bạn sử dụng dấu ngoặc nhọn, bạn sẽ nhận được một tập hợp hoặc một lệnh ngược và nếu bạn sử dụng dấu ngoặc đơn thông thường, bạn sẽ nhận được một biểu thức trình tạo [xem bên trên]

Dấu ngoặc vuông trong Python là gì?

Toán tử lập chỉ mục [Python sử dụng dấu ngoặc vuông để đặt chỉ mục] chọn một ký tự đơn từ chuỗi. Các ký tự được truy cập theo vị trí hoặc giá trị chỉ mục của chúng. Ví dụ: trong chuỗi hiển thị bên dưới, 14 ký tự được lập chỉ mục từ trái sang phải từ vị trí 0 đến vị trí 13.

Dấu ngoặc đơn là gì?

Nói chung, 'dấu ngoặc đơn' đề cập đến dấu ngoặc tròn [ ] và 'dấu ngoặc vuông' là dấu ngoặc vuông [ ].