Đánh giá biểu thức logic dạng chuỗi trong C++

Trong bài toán này, chúng ta được cho một chuỗi exp đại diện cho một biểu thức logic (boolean). Nhiệm vụ là đánh giá biểu thức logic này và trả về kết quả (0 hoặc 1).

Các ký tự hợp lệ trong biểu thức:

• 0 hoặc 1 đại diện cho giá trị boolean (False/True).
• & đại diện cho phép AND.
• | đại diện cho phép OR.
• ^ đại diện cho phép XOR.

Ví dụ minh họa

Đầu vào: str = "1&1|0^1^0&1"

Đầu ra: 0

Giải thích:

1&1|0^1^0&1
1 AND 1 OR 0 XOR 1 XOR 0 AND 1
1 OR 0 XOR 1 XOR 0 AND 1
1 XOR 1 XOR 0 AND 1
0 XOR 0 AND 1
0 AND 1
0

Phương pháp giải

Một giải pháp đơn giản là duyệt qua chuỗi, mỗi lần lấy 3 ký tự (toán hạng, toán tử, toán hạng), tính toán và thay thế kết quả vào vị trí toán hạng thứ hai, sau đó dịch chuỗi. Do các phép toán logic có cùng độ ưu tiên và tính từ trái sang phải, ta có thể xử lý tuần tự.

Chương trình minh họa

#include <iostream>
using namespace std;

int andOp(int a, int b) { return a & b; }
int orOp(int a, int b) { return a | b; }
int xorOp(int a, int b) { return a ^ b; }

char solveExpression(string s) {
    int n = s.length();
    // Duyệt qua các toán tử (ở vị trí lẻ: 1, 3, 5...)
    for (int i = 0; i < n; i += 2) {
        // Kiểm tra giới hạn để tránh out-of-bounds
        if (i + 2 >= n) break;

        if (s[i + 1] == '&') {
            s[i + 2] = andOp(s[i] - '0', s[i + 2] - '0') + '0';
        } else if (s[i + 1] == '|') { // Lưu ý: code gốc dùng '+' cho OR, sửa thành '|'
            s[i + 2] = orOp(s[i] - '0', s[i + 2] - '0') + '0';
        } else { // '^'
            s[i + 2] = xorOp(s[i] - '0', s[i + 2] - '0') + '0';
        }
    }
    return s[n - 1];
}

int main() {
    string expr = "0^1|0|1&1"; // Sửa ví dụ cho khớp logic OR là '|'
    cout << "Kết quả của biểu thức " << expr << " là " << solveExpression(expr);
    return 0;
}

Đầu ra

Kết quả của biểu thức 0^1|0|1&1 là 1

Lưu ý: Code gốc trong ví dụ sử dụng ký tự '+' cho phép OR, tuy nhiên đề bài quy định '|'. Code trên đã được chỉnh sửa để sử dụng '|' cho OR.