Giáo án chuyên đề Khoa học máy tính 12 chân trời Bài 1.4: Ứng dụng của ngăn xếp

HOẠT ĐỘNG CỦA GV - HS

DỰ KIẾN SẢN PHẨM

Bước 1: GV chuyển giao nhiệm vụ học tập

- GV yêu cầu HS hoạt động cá nhân và trả lời các câu hỏi:

+ Cơ chế hoạt động của ngăn xếp là gì? 

+ Em hãy nêu một số ứng dụng của ngăn xếp mà em biết?

- GV chia lớp thành 4 nhóm học tập, mỗi nhóm tìm hiểu về một ứng dụng phổ biến của ngăn xếp:

+ Em hãy trình bày và minh hoạ một số ứng dụng phổ biến của ngăn xếp. Phân tích ví dụ minh hoạ của mỗi ứng dụng.

-  GV yêu cầu HS vận dụng kiến thức vừa tìm hiểu, thực hiện hoạt động Làm SGK tr.22:

Em hãy minh hoạ:

a) Kiểm tra tính hợp lệ của dấu ngoặc trong chuỗi [2 * (4 + 3) – 5] bằng cách sử dụng ngăn xếp.

b) Chuyển biểu thức (1 – 4) * 2 + 7 sang dạng hậu tố bằng cách sử dụng ngăn xếp.

Bước 2: HS thực hiện nhiệm vụ học tập

- HS tìm hiểu nội dung mục 1 SGK tr.18 – 22 và trả lời các câu hỏi mà GV đưa ra.

- GV quan sát và trợ giúp HS (nếu cần thiết).

Bước 3: Báo cáo kết quả hoạt động và thảo luận

- HS lần lượt trả lời các câu hỏi.

- Đại diện các nhóm HS trình bày kết quả thảo luận.

- HS khác nhận xét, bổ sung. 

Bước 4: Đánh giá kết quả, thực hiện nhiệm vụ học tập

- Từ nội dung trả lời, thảo luận của HS, GV nhận xét, đánh giá quá trình HS thực hiện nhiệm vụ.

- GV chính xác hoá lại các nội dung kiến thức.

- GV chốt kiến thức theo hoạt động Ghi nhớ:

• Một số ứng dụng phổ biến của ngăn xếp là: kiểm tra tính hợp lệ của dấu ngoặc trong biểu thức; tính giá trị biểu thức số học,...

• Ngăn xếp cũng được ứng dụng trong các vấn đề thực tiễn như cơ chế hoàn tác hay làm lại, lịch sử duyệt web,...

1. Một số ứng dụng của ngăn xếp

- Ngăn xếp hoạt động theo cơ chế LIFO (Last In, First Out) – vào sau ra trước.

- Ngăn xếp được ứng dụng trong:

+ Tác vụ hoàn tác/làm lại.

Ví dụ: Chức năng Undo khi soạn thảo văn bản.

+ Lịch sử duyệt web trong các ứng dụng.

+ Giải quyết một số bài toán như tính giá trị của biểu thức số học, kiểm tra dấu ngoặc.

+ Theo dõi quá trình thực hiện của thuật toán quay lui, khử đệ quy,…

- Một số ứng dụng phổ biến của ngăn xếp:

+ Kiểm tra tính hợp lệ của dấu ngoặc: 

• Ngăn xếp có thể được sử dụng để kiểm tra các dấu ngoặc và đảm bảo tính hợp lệ của một biểu thức toán học hoặc lời gọi hàm trong ngôn ngữ lập trình.

• Một chuỗi có dấu ngoặc cân bằng khi mỗi dấu mở ngoặc được theo sau bởi một dấu đóng ngoặc tương ứng được đặt ở vị trí thích hợp và ngược lại. 

Ví dụ: 

• Các chuỗi "(((){[]}))", "({})([])" có dấu ngoặc cân bằng.

• Các chuỗi "((()]}", "((())" có dấu ngoặc không cân bằng. 

• Để kiểm tra tính hợp lệ của chuỗi bằng ngăn xếp cần duyệt qua từng kí tự:

Nếu kí tự là dấu mở ngoặc ("(" hoặc "{" hoặc "[") thì thêm vào ngăn xếp với thao tác push.

Nếu kí tự là dấu đóng ngoặc (")" hoặc "}" hoặc "]") thì lấy ra kí tự ở đỉnh ngăn xếp với thao tác pop. Sau đó kiểm tra:

• Nếu kí tự được pop là dấu mở ngoặc tương ứng với dấu đóng ngoặc đang xét thì tiếp tục quá trình duyệt chuỗi.

• Ngược lại thì trả về kết quả chuỗi có dấu ngoặc không cân bằng.

Bỏ qua nếu kí tự không phải là mở ngoặc hay đóng ngoặc.

Sau khi hoàn thành duyệt chuỗi, kiểm tra ngăn xếp: 

• Nếu rỗng  chuỗi có dấu ngoặc cân bằng. 

• Nếu không rỗng  chuỗi có dấu ngoặc không cân bằng. 

Ví dụ: Bảng 1 minh hoạ quá trình sử dụng ngăn xếp để kiểm tra tính hợp lệ các dấu ngoặc của chuỗi [(2+3)*5].

Bảng 1. Minh hoạ quá trình sử dụng ngăn xếp để kiểm tra tính hợp lệ của dấu ngoặc

+ Tính giá trị các biểu thức số học: 

• Ngăn xếp được sử dụng để tính giá trị các biểu thức số học bao gồm các toán hạng và toán tử, các dấu mở ngoặc và đóng ngoặc.  

• Tính giá trị biểu thức số học gồm hai bước:

Chuyển biểu thức dạng trung tố sang dạng tiến tố (toán tử nằm trước toán hạng) hoặc hậu tố (toán tử nằm sau toán hạng). 

Lưu ý: Thông thường, để chuyển từ biểu thức từ trung tố sang dạng tiền tố hay hậu tố, em cần phải phân tích các thành phần của biểu thức thành các phần tử: toán hạng, toán tử, dấu mở ngoặc, dấu đóng ngoặc,... Kết quả biểu thức dạng tiền tố hay hậu tố phải cho thấy sự tách biệt của các phần tử này (chẳng hạn, các phần tử tách nhau bởi khoảng trống). Tuy nhiên, việc phân tích các phần tử trong chuỗi biểu thức đòi hỏi một số kĩ thuật xử lí chuỗi, nên trong bài học này, em có thể giả sử các toán tử và toán hạng trong biểu thức chỉ bao gồm một kí tự.

Ví dụ: Biểu thức dạng trung tố A + B có dạng tiền tố là +AB và dạng hậu tố là AB+. Bảng 2 minh hoạ quá trình sử dụng ngăn xếp để chuyển biểu thức dạng trung tố 2 * (4 + 3) – 5 sang dạng hậu tố 2 4 3 + * 5 –.

Bảng 2. Minh hoạ quá trình sử dụng ngăn xếp để chuyển từ biểu thức dạng trung tố sang dạng hậu tố

Sử dụng ngăn xếp để tính giá trị biểu thức dạng hậu tố. 

Với mỗi kí tự trong biểu thức dạng hậu tố:

• Nếu là toán hạng thì được thêm vào ngăn xếp. 

• Nếu là toán tử, thì hai toán hạng ở đầu ngăn xếp được lấy ra để thực hiện tính giá trị với toán tử đó, sau đó giá trị tính được sẽ được thêm vào đỉnh ngăn xếp. 

Quá trình này tiếp tục cho đến khi ngăn xếp chỉ còn một phần tử, cũng chính là giá trị của biểu thức. 

Ví dụ: Bảng 3 minh hoạ quá trình sử dụng ngăn xếp để tính giá trị của biểu thức dạng hậu tố 
2 4 3 + * 5 –.

Bảng 3. Minh hoạ quá trình sử dụng ngăn xếp để tính giá trị của biểu thức dạng hậu tố

Hướng dẫn trả lời câu hỏi hoạt động Làm SGK tr.22:

a)

b)