Pythonでブール式を解析して評価する方法

はじめに

ブール式（真偽値を扱う論理式）が与えられたとき、その式を実際に評価した結果を求める問題を考えてみましょう。

この問題では、式は次のいずれかの形式で表現されます。

• 「t」 … True に評価される
• 「f」 … False に評価される
• 「!(expression)」 … 内側の式の論理否定（NOT）
• 「&(expr1,expr2,...)」 … 2つ以上の内側の式の論理積（AND）
• 「|(expr1,expr2,...)」 … 2つ以上の内側の式の論理和（OR）

具体例

たとえば、入力が |(!(t),&(t,f,t)) の場合、出力は False になります。

その理由を見てみましょう。!(t) は t を否定するので False、&(t,f,t) には f が含まれるため False です。したがって、両方が False の OR 演算の結果も False となります。

解き方のアプローチ

この問題は、再帰処理とスタックを組み合わせることで効率よく解けます。手順は以下のとおりです。

1. solve(e, i) 関数を定義します（e は式、i は現在の位置）。
2. e[i] が「f」なら、(False, i + 1) を返します。
3. e[i] が「t」なら、(True, i + 1) を返します。
4. それ以外の場合は演算子として op := e[i] を取得し、i を 2 増やします（開き括弧をスキップ）。
5. 結果を保持するためのスタックを用意します。
6. e[i] が閉じ括弧「)」でない限り、以下を繰り返します。
   • e[i] が「,」なら、i を 1 増やしてスキップ。
   • それ以外は solve(e, i) を再帰的に呼び出し、得られた結果 res をスタックにプッシュします。
7. op が「&」の場合：スタック内のすべての要素が True なら True、そうでなければ False を返します（i + 1 と一緒に）。
8. op が「|」の場合：スタック内の少なくとも 1 つの要素が True なら True、そうでなければ False を返します。
9. 上記以外（つまり「!」の場合）：stack[0] の反転（NOT）を返します。
10. メイン処理からは、solve(expression, 0) を呼び出し、その最初の戻り値 s を返します。

実装例（Python）

class Solution(object):
    def parseBoolExpr(self, expression):
        s, y = self.solve(expression, 0)
        return s

    def solve(self, e, i):
        if e[i] == "f":
            return False, i + 1
        elif e[i] == "t":
            return True, i + 1
        op = e[i]
        i = i + 2
        stack = []
        while e[i] != ")":
            if e[i] == ",":
                i += 1
                continue
            res, i = self.solve(e, i)
            stack.append(res)
        if op == "&":
            return all(stack), i + 1
        elif op == "|":
            return any(stack), i + 1
        return not stack[0], i + 1

ob = Solution()
print(ob.parseBoolExpr("|(!(t),&(t,f,t))"))

入力

"|(!(t),&(t,f,t))"

出力

False

ポイントのまとめ

• Python の組み込み関数 all() を使うことで、AND 演算（すべて True かどうか）を簡潔に判定できます。
• 同様に any() を使えば、OR 演算（少なくとも 1 つが True かどうか）を一行で表現できます。
• ネストされた括弧構造は再帰呼び出しによって自然に処理でき、各部分式の評価結果をスタックに積んでいくのがこの手法の核心です。
• 計算量は式の長さに対してほぼ線形時間 O(n) となり、効率的な実装と言えます。