Giáo án điện tử 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

BÀI 1.4: ỨNG DỤNG CỦA NGĂN XẾP

Chào mừng quý thầy cô cùng các em học sinh đến với tiết học ngày hôm nay!

A. KHỞI ĐỘNG

Cho biết cách trình bày cách để kiểm tra số dấu mở ngoặc và số dấu đóng ngoặc tương ứng trong chuỗi "(((){[]}))" có bằng nhau hay không.

Gợi ý trả lời:

Có thể kiểm tra tính hợp lệ của dấu ngoặc dựa trên ngăn xếp bằng cách kiểm tra chuỗi dấu ngoặc đơn giản "(((){[]}))". Nếu gặp dấu ngoặc mở thì thêm vào ngăn xếp, nếu gặp dấu đóng ngoặc thì lấy dấu ngoặc mở ở đỉnh ra khỏi ngăn xếp. Nếu sau quá trình trên, ngăn xếp rỗng thì chuỗi dấu ngoặc hợp lệ.

…

B. HÌNH THÀNH KIẾN THỨC

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

+ 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?

Dự kiến sản phẩm:

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ự.

………………………………………………….

Hoạt động 2. Thực hành

- Nhiệm vụ 1 SGK tr.23 và thực hành cá nhân theo hướng dẫn.

- Nhiệm vụ 2. Viết chương trình tính giá trị của biểu thức số học với biểu thức đầu vào là biểu thức hậu tố

Dự kiến sản phẩm:

2. THỰC HÀNH 

Nhiệm vụ 1. Chuyển biểu thức dạng trung tố sang hậu tố 

- Hàm isOperator():

- Hàm getPriority():

- Hàm inFixtoPostfix():

Nhiệm vụ 2. Viết chương trình tính giá trị của biểu thức số học với biểu thức đầu vào là biểu thức hậu tố 

- Hàm tính b op a, với a, b là toán hạng, op là toán tử:

- Hàm tính giá trị biểu thức dạng hậu tố:

C. LUYỆN TẬP

Hoàn thành phiếu bài tập sau:

Khoanh tròn vào chữ cái đứng trước câu trả lời đúng nhất:

Câu 1. Phương án nào sau đây không phải là một ứng dụng của ngăn xếp?

A. Theo dõi quá trình thực hiện của thuật toán quay lui.

B. Cơ chế hoàn tác/làm lại.

C. Sắp xếp các tiến trình chờ xử lí của CPU.

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

Câu 2. Thao tác push sẽ thêm mới phần tử vào vị trí nào của ngăn xếp?

A. Vị trí bất kì của ngăn xếp.      

B. Đỉnh ngăn xếp.            

C. Chính giữa ngăn xếp.             

D. Đáy ngăn xếp.

Câu 3. Phát biểu nào sau đây đúng? 

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

B. Khi 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 đáy ngăn xếp.

C. Khi 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 ở cuối 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.                 

D. Khi 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.

Câu 4. Biểu thức dạng trung tố x + y * z có dạng tiền tố là

A. xyz * +.

B. + xz * y.

C. + x * yz.

D. * x + yz.

Câu 5. Để lấy ra kí tự ở đỉnh ngăn xếp, ta sử dụng thao tác nào?

A. push.

B. top.

C. front.

D. pop.………………………..

Gợi ý trả lời:

D. VẬN DỤNG

Yêu cầu: Viết chương trình chuyển một biểu thức dạng trung tố inFix sang dạng tiền tố preFix.

Dữ liệu vào: chuỗi biểu thức dạng trung tố.

Dữ liệu ra: chuỗi biểu thức dạng tiền tố.

Ví dụ:

HƯỚNG DẪN VỀ NHÀ

- Xem lại kiến thức đã học ở Bài 1.4.

- Xem trước nội dung Bài 2.1: Cây và cây nhị phân.