การประเมินนิพจน์บูลีนแบบสตริงใน C++

ปัญหา

ได้รับสตริง exp ที่แทนนิพจน์บูลีน ต้องประเมินค่าและส่งคืนผลลัพธ์ ตัวอักษรที่ถูกต้องคือ:

• 0 หรือ 1 แทนค่าบูลีน
• & แทน AND
• | แทน OR
• ^ แทน XOR

ตัวอย่าง

อินพุต: str = "1&1|0^1^0&1"

เอาต์พุต: 0

คำอธิบาย:

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

แนวทางแก้ปัญหา

วิธีง่ายคือตรวจสอบค่าปัจจุบันและดำเนินการทีละขั้นตอน โดยพิจารณา 3 ตัวอักษรของสตริงในแต่ละครั้ง

โปรแกรมตัวอย่าง

#include <iostream>
using namespace std;

int andOperation(int a, int b) { return a & b; }
int orOperation(int a, int b) { return a | b; }
int xorOperation(int a, int b) { return a ^ b; }

char solveExpression(string s) {
    int n = s.length();
    for (int i = 0; i < n; i += 2) {
        if (s[i + 1] == '&') {
            s[i + 2] = andOperation(s[i], s[i + 2]);
        } else if (s[i + 1] == '|') {
            s[i + 2] = orOperation(s[i], s[i + 2]);
        } else {
            s[i + 2] = xorOperation(s[i], s[i + 2]);
        }
    }
    return s[n - 1];
}

int main() {
    string expr = "0^1+0+1&1";
    cout << "The result of expression " << expr << " is " << solveExpression(expr);
    return 0;
}

ผลลัพธ์

The result of expression 0^1+0+1&1 is 1