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ự

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à “)”

Giải Chuyên đề Tin 12 Bài 2: Kiểu dữ liệu ngăn xếp - Kết nối tri thức

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: