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

解法のアプローチ

もっともシンプルな解法は、文字列を左から右へ操作を1つずつ適用していく方法です。常に「オペランド・演算子・オペランド」の3文字に着目して演算を行い、その結果を次のステップへ引き継ぎます。

なお、この手法では通常の演算子の優先順位（AND → XOR → OR）は考慮せず、純粋に左から右へ評価する点に注意してください。優先順位を厳密に扱いたい場合は、スタックを用いた構文解析などの発展的な手法が必要になります。

C++での実装例

上記の考え方を実装したプログラムがこちらです。

#include <iostream>
#include <string>
using namespace std;

// 2つのブール値に対して指定された演算を適用する
int applyOperation(int a, char op, int b) {
    switch (op) {
        case '&': return a & b;  // AND
        case '|': return a | b;  // OR
        case '^': return a ^ b;  // XOR
    }
    return 0;
}

// 文字列で表されたブール式を左から右へ評価する
int solveExpression(const string& s) {
    int n = s.length();
    int result = s[0] - '0';      // 先頭のオペランド
    for (int i = 1; i < n; i += 2) {
        char op = s[i];               // 演算子
        int operand = s[i + 1] - '0'; // 次のオペランド
        result = applyOperation(result, op, operand);
    }
    return result;
}

int main() {
    string expr = "1&1|0^1^0&1";
    cout << "式 " << expr << " の評価結果: " << solveExpression(expr) << endl;
    return 0;
}

出力

式 1&1|0^1^0&1 の評価結果: 0

コードのポイント

・s[i] - '0' によって、文字 '0'／'1' を整数値 0／1 に変換しています。
・ループは2文字ずつ進み（i += 2）、演算子とオペランドを交互に読み取ります。
・演算結果をその場で result に反映するため、余分なメモリは不要です。

計算量

時間計算量：O(n) ― 文字列を一度だけ走査します。

空間計算量：O(1) ― 定数個の変数しか使用しません。