Chương trình đánh giá biểu thức Boolean từ chuỗi trong Python

Cho chuỗi s chứa biểu thức Boolean với toán tử and, or và dấu ngoặc. Đánh giá và trả về kết quả (True/False). Dấu ngoặc có độ ưu tiên cao nhất.

Ví dụ

Đầu vào: "T and (F or T)"

Đánh giá: F or T = True → T and True = True → kết quả: True.

Thuật toán (Stack-based parsing)

1. Tách chuỗi theo khoảng trắng thành tokens.
2. Duyệt tokens, dùng stack lưu giá trị boolean và toán tử.
3. Xử lý dấu ngoặc:
   • Token bắt đầu bằng (: push giá trị boolean bên trong.
   • Token chứa ): pop 3 phần tử (right, operator, left), tính toán, push kết quả. Lặp cho mỗi dấu ).
4. Token T/F: push boolean tương ứng.
5. Token toán tử: push function lambda.
6. Cuối cùng: nếu stack > 1 phần tử, đánh giá lần lượt từ trái sang phải.

Triển khai Python

class Solution:
    def solve(self, s):
        stack = []
        ops = {
            "or": lambda x, y: x or y,
            "and": lambda x, y: x and y,
        }
        for token in s.split():
            if token[0] == "(":
                # Token dạng "(T" hoặc "(F"
                stack.append(token[token.count("("):] == "T")
            elif token.count(")") > 0:
                ct = token.count(")")
                # Token dạng "T))" hoặc "F))"
                stack.append(token[:-ct] == "T")
                for _ in range(ct):
                    right = stack.pop()
                    op = stack.pop()
                    left = stack.pop()
                    stack.append(op(left, right))
            elif token in ["T", "F"]:
                stack.append(token == "T")
            else:
                stack.append(ops[token])
        
        # Đánh giá các phép toán còn lại (left-associative)
        if len(stack) > 1:
            for i in range(0, len(stack) - 1, 2):
                stack[i + 2] = stack[i + 1](stack[i], stack[i + 2])
            return stack[-1]
        return stack[0]

# Test
ob = Solution()
print(ob.solve("T and (F or T)"))        # True
print(ob.solve("F or (T and F)"))        # False
print(ob.solve("(T or F) and (F or T)")) # True

Độ phức tạp

• Thời gian: O(n) với n số token.
• Không gian: O(n) cho stack.

Lưu ý: Triển khai này giả định input đúng định dạng, không có toán tử NOT.