Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Bài tập 3.1: Viết chương trình tính giá trị biểu thức trung tố theo các yêu cầu sau: 1. Nhập biểu thức trung tố: toán hạng, toán tử và dấu ngoặc VD: (20+5)/5+(7-3)*100 2. Chuyển biểu thức trung tố thành hậu tố (xuất ra màn hình) VD: 20 5 + 5 / 7 3 – 100 * + 3. Tính giá trị của biểu thức hậu tố VD: (20+5)/5+(7-3)*100 = 405 Yêu cầu: Sinh viên cài đặt stack dùng danh sách liên kết: 1. Khai báo cấu trúc của phần tử trong DSLK dùng làm stack 2. Cài đặt các thao tác: IsEmpty, NewNode, FreeNode, Pop, Push trên Stack | Cấu trúc dữ liệu giải thuật CNTT Bài thực hành số 3 Stack -Queue Bài tập 3.1 Viết chương trình tính giá trị biểu thức trung tố theo các yêu cầu sau 1. Nhập biểu thức trung tố toán hạng toán tử và dấu ngoặc VD 20 5 5 7-3 100 2. Chuyển biểu thức trung tố thành hậu tố xuất ra màn hình VD 20 5 5 7 3 - 100 3. Tính giá trị của biểu thức hậu tố VD 20 5 5 7-3 100 405 Yêu cầu Sinh viên cài đặt stack dùng danh sách liên kết 1. Khai báo cấu trúc của phần tử trong DSLK dùng làm stack 2. Cài đặt các thao tác IsEmpty NewNode FreeNode Pop Push. trên Stack. Hướng dẫn 1. Chuyển biểu thức trung tố thành hâu tố Duyệt biểu thức trung tố từ trái sang phải Nếu gặp toán hạng thì ghi vào chuỗi kết quả Nếu gặp dấu mở ngoặc thì push stack Nếu gặp toán tử gọi là Oi thực hiện các bước sau Chừng nào còn một toán tử O2 ở đỉnh stack và độ ưu tiên của Oi độ ưu tiên O2 thì lấy O2 ra khỏi stack và ghi vào chuỗi kết quả. Push Oi stack 1 Cấu trúc dữ liệu giải thuật CNTT Nếu gặp dâu đóng ngoặc thì lấy toán tử trong stack ra cho đến khi lấy được dấu mở ngoặc lưu ý pop dâu mở ngoặc ra nhưng ko xuất ra chuỗi kết quả ị Khi đã duyệt kết biểu thức trung tố lây tất cả toán tử trong stack và ghi vào chuỗi kết quả. 2. Tính giá trị biểu thức hâu tố ị Đọc biểu thức từ trái sang phải Nếu là toán hạng Push stack Nếu gặp toán tử Lấy 2 toán hạng trong stack ra Tính giá trị của 2 toán hạng đó theo toán tử Push kết quả stack ị Khi quá trình kết thúc thì con số cuối cùng còn lại trong stack chính là giá trị của biểu thức đó. Bài tập 3.2 Bài toán Tháp Hanoi được mô tả như sau cho 3 cột được đánh số lần lượt là 1 2 và 3. Có n đĩa được sắp theo thứ tự đĩa nhỏ ở bên trên đĩa lớn. Hãy liệt kê các bước thực hiện để chuyển tất cả các đĩa từ cột 1 sang cột 2. Quy luật di chuyển như sau 1. Mỗi bước chỉ di chuyển 1 đĩa từ cột này sang cột khác. 2. Đĩa có bán kính nhỏ luôn sắp trên đĩa có bán kính lớn. 12 3 12 3 I I I à Yêu cầu Viết chương trình nhập vào số đĩa n thực hiện các bước di chuyển các đĩa mỗi bước di chuyển cho biết .
