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ự

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:

• Khởi động trang 9 Chuyên đề Tin học 12: Theo em những kiểu dữ liệu sau có thể được dùng để thiết lập dữ liệu ngăn xếp không ....

• Hoạt động 1 trang 9 Chuyên đề Tin học 12: Dùng kiểu dữ liệu mảng để biểu diễn ngăn xếp. Quan sát, trao đổi, thảo luận ....

• Câu hỏi 1 trang 10 Chuyên đề Tin học 12: Dãy các số 1, 2, 3, 4, 5, 6 lần lượt được đưa vào ngăn xếp S bằng lệnh ....

• Câu hỏi 2 trang 10 Chuyên đề Tin học 12: Giả sử chúng ta lần lượt thực hiện dãy các lệnh sau (ngăn xếp S ban đầu là rỗng) ....

• Hoạt động 2 trang 10 Chuyên đề Tin học 12: Tìm hiểu các hàm cơ bản của ngăn xếp. Đọc, trao đổi để biết các hàm cơ bản ....

• Câu hỏi 1 trang 12 Chuyên đề Tin học 12: Sửa lại hàm pop(S) và top(S) trong hoạt động trên như sau: Nếu ngăn xếp rỗng thì thông báo ....

• Câu hỏi 2 trang 12 Chuyên đề Tin học 12: Vì sao các hàm cơ bản trên ngăn xếp S được cài đặt bằng danh sách (kiểu list của Python) ....

• Luyện tập 1 trang 12 Chuyên đề Tin học 12: Viết hàm length(S) trả về số phần tử của ngăn xếp S ....

• Luyện tập 2 trang 12 Chuyên đề Tin học 12: Giả sử dãy số ban đầu là 2, 7, 6, 1 và S là ngăn xếp rỗng. Chúng ta lần lượt thực hiện các thao tác ....

• Vận dụng 2 trang 12 Chuyên đề Tin học 12: Ngăn xếp S được cài đặt bằng mảng T có N phân tử, phần tử đầu tiên có chỉ số 0 ....

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:

• Chuyên đề Tin học 12 Bài 3: Thực hành với dữ liệu ngăn xếp

• Chuyên đề Tin học 12 Bài 4: Kiểu dữ liệu hàng đợi

• Chuyên đề Tin học 12 Bài 5: Thực hành kiểu dữ liệu ngăn xếp và hàng đợi

• Chuyên đề Tin học 12 Bài 6: Cây nhị phân

• Chuyên đề Tin học 12 Bài 7: Cây tìm kiếm nhị phân

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

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều
• Giải lớp 12 Kết nối tri thức (các môn học)
• Giải lớp 12 Chân trời sáng tạo (các môn học)
• Giải lớp 12 Cánh diều (các môn học)

---