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ệ".

#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ệ