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.
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:
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
Hot: 500+ Đề thi thử tốt nghiệp THPT các môn, ĐGNL các trường ĐH... file word có đáp án (2025). Tải ngay
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.
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.
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.
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.