Viết chương trình kiểm tra tính hợp lệ của dấu ngoặc trong chuỗi biểu thức số học
Viết chương trình kiểm tra tính hợp lệ của dấu ngoặc trong chuỗi biểu thức số học. Dữ liệu vào: chuỗi biểu thức số học.
Giải Chuyên đề Tin 12 Bài 1.4: Ứng dụng của ngăn xếp - Chân trời sáng tạo
Luyện tập trang 22 Chuyên đề Tin học 12: Viết chương trình kiểm tra tính hợp lệ của dấu ngoặc trong chuỗi biểu thức số học. Dữ liệu vào: chuỗi biểu thức số học.
Dữ liệu ra: nếu các dấu ngoặc cân bằng thì thông báo lên màn hình "Chuỗi có dấu ngoặc hợp lệ", ngược lại thông báo "Chuỗi có dấu ngoặc không hợp lệ".
Lời giải:
#Mã giả kiểm tra dấu ngoặc hợp lệ trong chuỗi biểu thức
checkParentheses (s)
openParentheses = ["[","{","("] closeParentheses = ["]","}",")"] khởi tạo ngăn xếp stack rỗng for c in s:
if c là là dấu mở ngoặc:
Thêm c vào stack
elif c là dấu đóng ngoặc:
if stack rỗng:
return False
#Danh sách các ngoặc mở
#Danh sách các ngoặc đóng
else:
pos = vị trí của c trong closeParentheses
c1 là dấu mở ngoặc ở vị trí pos (tương ứng với c) c2 là dấu mở ngoặc lấy ra từ stack
if c1 khác c2:
return False
if stack rỗng:
return True
else:
return False
* Hàm kiểm tra dấu ngoặc hợp lệ trong chuỗi:
#Hàm kiểm tra dấu ngoặc hợp lệ trong chuỗi biểu thức
def checkParentheses(s):
openParentheses = ["[","",""] closeParentheses = ["]","}",")"] stack initStack() for c in s:
if c in openParentheses: push(stack, c)
elif c in closeParentheses:
if isEmptyStack(stack):
return False
else:
#Danh sách các kí tự ngoặc mở #Danh sách các kí tự ngoặc đồng #Khởi tạo ngăn xếp rỗng #Duyệt mọi kí tự trong s
#Kiểm tra nếu c là dấu mở ngoặc
#Thêm c vào stack
#Ngược lại, nếu c là dấu đóng ngoặc
pos = closeParentheses.index(c) #Lấy vị trí của kí tự ngoặc đóng
c1 = openParentheses[pos]
c2 = pop(stack)
if c1 = c2:
return False
if isEmptyStack(stack):
return True
else:
return False
#Nếu stack rỗng, dấu ngoặc hợp lệ
#Ngược lại, chuỗi có dấu ngoặc không hợp lệ
Lời giải bài tập Chuyên đề Tin 12 Bài 1.3: Ứng dụng của hàng đợi hay, chi tiết khác: