Câu hỏi:

13/07/2024 375

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 ki 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.

Quảng cáo

Trả lời:

verified
Giải bởi Vietjack

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

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Lời giải

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). push(S,1); push(S,2); pop(S); push(S,3); pop(S); pop(S).

Dãy các phần tử lần lượt được đưa ra khỏi ngăn xếp là các số: 2,3,1.

Lời giải

Vì đỉnh (top) của ngăn xếp S luôn là phần tử cuối cùng của danh sách S. Do vậy không cần biến top.

Vì đáy (bottom) của ngăn xếp S luôn là phần tử đầu tiên của danh sách S. Do vậy không cần biến bottom.

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP