Xâu kí tự được gọi là biểu thức nếu nó là rỗng hoặc chỉ chứa các kí tự

Vận dụng 1 trang 12 Chuyên đề Tin học 12: Xâu kí tự được gọi là biểu thức nếu nó là rỗng hoặc chỉ chứa các kí tự “(“ và “)”

Ví dụ: "((()())())". Xâu biểu thức được gọi là đúng nếu vị trí các dáu ngoặc được sắp xếp hợp lí theo tự nhiên. Ví dụ các xâu sau là biểu thức đúng:

()

(()())

Ví dụ các xâu biểu thức sau là sai:

((())

))()()

Có thể định nghĩa khái niệm biểu thức đúng bằng đệ quy như sau:

- Xâu rỗng là đúng.

- Nếu xâu A, B đúng thì xâu AB đúng.

- Nếu xâu A là đúng thì xâu (A) đúng.

Cho trước xâu biểu thức A, viết chương trình kiểm tra xem A có là biểu thức đúng hay không. Yêu cầu sử dụng kiểu dữ liệu ngăn xếp.

Lời giải:

def is_valid_expression(expression):

# Khởi tạo ngăn xếp rỗng

stack = []

# Tạo một từ điển để ghép các dấu ngoặc đóng với dấu ngoặc mở tương ứng

matching_parentheses = {')': '(', '}': '{', ']': '['}

# Duyệt qua từng ký tự trong biểu thức

for char in expression:

if char in matching_parentheses.values():

stack.append(char)

elif char in matching_parentheses.keys():

if not stack or stack.pop() != matching_parentheses[char]:

return False

return not stack

Lời giải bài tập Chuyên đề Tin 12 Bài 2: Kiểu dữ liệu ngăn xếp hay, ngắn gọn khác:

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

Xem thêm các tài liệu học tốt lớp 12 hay khác:

Giải bài tập lớp 12 sách mới các môn học