Bài 3. Thực hành kiểu dữ liệu ngăn xếp
THỰC HÀNH KIỂU DỮ LIỆU NGĂN XẾP
Sau bài học này em sẽ:
Trong bài trước, các em đã học cách thiết lập kiểu dữ liệu ngăn xếp. Kiểu dữ liệu ngăn xếp được sử dụng khá phổ biến trong các ứng dụng thực tế. Theo em, có thể sử dụng kiểu dữ liệu này để mô phỏng chức năng quay lại trang web đã duyệt trong các trình duyệt thông dụng như Google Chrome hay Bing được không?
Nhiệm vụ 1: Viết chương trình mô phỏng quá trình duyệt web
Hầu hết các trình duyệt web đều hỗ trợ chức năng quay lại trang web trước (backward). Để thực hiện chức năng này, các trình duyệt web lưu lại lịch sử các trang web đã duyệt trước đó.
Viết chương trình mô phỏng quá trình duyệt web của người dùng bằng cách sử dụng ngăn xếp. Chương trình cho phép người dùng nhấn phím số 1 để nhập vào địa chỉ trang web mới, nhấn phím số 2 để quay trở về trang web vừa duyệt trước đó, nhấn phím số 3 để kết thúc. Với mỗi lựa chọn, chương trình sẽ in ra thông báo về việc đi tới trang web tương ứng.
Hướng dẫn
Phân tích: Trong bài toán này, chúng ta cần sử dụng kiểu dữ liệu phù hợp để lưu trữ lịch sử các trang web đã duyệt. Mỗi lần người dùng duyệt web, cần lưu lại địa chỉ trang web. Khi người dùng chọn quay trở lại trang web trước (backward) thì cần truy xuất lại trang web ngay trước đó, nghĩa là trang web nào được lưu trữ sau cùng sẽ được truy xuất đầu tiên. Như vậy, dữ liệu ngăn xếp là kiểu dữ liệu phù hợp trong bài toán này.
web.py
from Stack import *
backward = Stack()
option = 0
while option != 3:
option = int(input("Hãy nhập vào lựa chọn của bạn:\n"))
if option == 1:
website = input("Hãy nhập vào địa chỉ website muốn đi đến:\n")
push(backward, website)
print("Đang đi đến trang web: " + website)
if option == 2:
if isEmptyStack(backward):
print("Không tồn tại lịch sử duyệt web")
else:
website = pop(backward)
print("Đang đi đến trang web: " + website)Nhiệm vụ 2: Viết chương trình kiểm tra các dấu ngoặc trong biểu thức
Hầu hết công cụ hỗ trợ các ngôn ngữ lập trình bậc cao hiện nay đều có chức năng phát hiện và cảnh báo một số lỗi lập trình của người lập trình, ví dụ kiểm tra thứ tự xuất hiện các dấu đóng/mở ngoặc trong các biểu thức có hợp lệ hay không.
Em hãy viết chương trình cho phép người dùng nhập vào một biểu thức toán học và kiểm tra các dấu đóng mở ngoặc trong biểu thức có hợp lệ hay không. Biểu thức có thể chứa hai loại dấu đóng mở ngoặc là dấu "( )" và dấu "[ ]". Một biểu thức hợp lệ là biểu thức mà trong đó mỗi dấu mở ngoặc cần có các dấu đóng ngoặc tương ứng theo trình tự xuất hiện. Ví dụ biểu thức [(5 + 4)/(9 - 3)] được coi là hợp lệ; biểu thức [(5 + 4)/(9 - 3]) là không hợp lệ.
Hướng dẫn
Phân tích: Các dấu đóng mở ngoặc có thể được chia ra làm hai nhóm: nhóm các dấu ngoặc mở bao gồm "(", "[" và nhóm các dấu ngoặc đóng ")", "]". Một biểu thức là hợp lệ nếu số lượng các dấu ngoặc đóng, ngoặc mở phải bằng nhau, thêm vào đó, với mỗi dấu ngoặc đóng, dấu ngoặc mở ngay trước đó phải là dấu cùng loại. Ví dụ với dấu ")" thì dấu ngoặc mở ngay trước đó phải là dấu "(". Nếu dấu ngoặc mở ngay trước dấu ")" là "[" thì biểu thức là không hợp lệ.
Để giải bài toán này, chúng ta sử dụng ngăn xếp. Các bước thực hiện như sau:
Ví dụ: Xét biểu thức "([()])".
Duyệt kí tự "(" đẩy vào ngăn xếp. Duyệt kí tự "[" đẩy vào ngăn xếp. Duyệt kí tự "(" đẩy vào ngăn xếp. Duyệt kí tự ")" lấy "(" khỏi ngăn xếp. Duyệt kí tự "]" lấy "[" khỏi ngăn xếp. Duyệt kí tự ")" lấy "(" khỏi ngăn xếp.
Hết biểu thức, kiểm tra ngăn xếp có rỗng hay không. Lúc này ngăn xếp rỗng nên biểu thức là hợp lệ.
kiemtrabieuthuc.py
from Stack import *
def kiemtrabt(bieuthuc):
hople = True
ngoacmo = Stack()
for i in range(0, len(bieuthuc)):
if bieuthuc[i] in {"(", "["}:
push(ngoacmo, bieuthuc[i])
elif bieuthuc[i] in {")", "]"}:
if isEmptyStack(ngoacmo):
hople = False
break
else:
tmp = pop(ngoacmo)
if (bieuthuc[i] == ")" and tmp != "(") or (bieuthuc[i] == "]" and tmp != "["):
hople = False
break
if not isEmptyStack(ngoacmo):
hople = False
return hople
bieuthuc = input("Hãy nhập vào một biểu thức:\n")
hople = kiemtrabt(bieuthuc)
if hople:
print("Biểu thức hợp lệ")
else:
print("Biểu thức không hợp lệ")LUYỆN TẬP
VẬN DỤNG
Nếu muốn lấy quyển sách Maths ra khỏi ngăn xếp sách thì chúng ta cần lấy các quyển Biology, History, Chemistry ra trước.