Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Định giá biểu thức Boolean có độ ưu tiên bằng đệ quy

    Xét văn phạm phi ngữ cảnh cho biểu thức logic Boolean với ba toán tử NOT, AND, OR (độ ưu tiên giảm dần: NOT cao nhất, rồi đến AND, thấp nhất là OR; AND và OR kết hợp trái):

    Expr→Term ( OR Term )∗\text{Expr} \to \text{Term}\ (\ \text{OR}\ \text{Term}\ )^*Expr→Term ( OR Term )∗ Term→Factor ( AND Factor )∗\text{Term} \to \text{Factor}\ (\ \text{AND}\ \text{Factor}\ )^*Term→Factor ( AND Factor )∗ Factor→NOT Factor ∣ ( Expr ) ∣ TRUE ∣ FALSE\text{Factor} \to \text{NOT}\ \text{Factor} \ \mid\ (\ \text{Expr}\ ) \ \mid\ \text{TRUE} \ \mid\ \text{FALSE}Factor→NOT Factor ∣ ( Expr ) ∣ TRUE ∣ FALSE

    Chuỗi đầu vào gồm các token (TRUE, FALSE, AND, OR, NOT, (, )) cách nhau bởi đúng một khoảng trắng. Hãy cài đặt bộ phân tích cú pháp đệ quy xuống, trong đó mỗi hàm (Expr\text{Expr}Expr, Term\text{Term}Term, Factor\text{Factor}Factor) vừa phân tích vừa tính giá trị Boolean trực tiếp (không cần dựng cây cú pháp trung gian).

    Yêu cầu: in ra kết quả cuối cùng của toàn bộ biểu thức.

    Ví dụ: TRUE OR FALSE AND NOT TRUE — do AND ưu tiên hơn OR và NOT ưu tiên cao nhất, biểu thức được hiểu là TRUE OR (FALSE AND (NOT TRUE)) === TRUE OR (FALSE AND FALSE) === TRUE OR FALSE === TRUE.

    • Định dạng đầu vào:

      Một dòng chứa các token cách nhau bởi một khoảng trắng, gồm TRUE, FALSE, AND, OR, NOT, (, ), đảm bảo hợp lệ cú pháp theo văn phạm trên. Độ dài dòng không quá 2000 ký tự.

    • Định dạng đầu ra:

      In ra TRUE hoặc FALSE — giá trị của biểu thức Boolean.

    Ví dụ:

    Đầu vào:

    TRUE

    Đầu ra:

    TRUE

    Đầu vào:

    TRUE OR FALSE AND NOT TRUE

    Đầu ra:

    TRUE

    Đang tải editor...