Pythonで文字列として与えられたブール式を評価する方法

「and」や「or」といった論理演算子を含むブール式が、文字列 s として与えられたとします。この式を評価し、その結果を返すのが本記事の目的です。式には括弧が含まれる場合があり、括弧で囲まれた部分は最優先で評価する必要があります。

たとえば、入力が s = "T and (F or T)" であれば、出力は True になります。

解決の手順

この問題は、スタック（リスト）を活用することで効率的に解けます。全体の流れは以下の通りです。

1. スタックの初期化：空のリスト stack を用意します。
2. トークン化：文字列 s を空白区切りで分割し、トークンのリストを作成します。
3. 各トークンの処理：各トークン v に対して、次のように判定と処理を行います。
   • v が「(」で始まる場合 → 括弧を取り除いた残りの部分が「T」であるかを判定し、その真偽値をスタックへプッシュします。
   • v に「)」が含まれる場合 → 閉じ括弧の個数を ct とし、括弧を除いた部分が「T」かどうかを判定してスタックへプッシュします。続いて ct 回ポップを行い、右辺・演算子・左辺を取り出して演算を実行し、その結果をスタックに戻します。
   • v が「T」または「F」の場合 → v が「T」と等しいかどうかの真偽値をスタックへプッシュします。
   • 上記以外（演算子）の場合 → 演算子に対応する関数 op[v] をスタックへプッシュします。
4. 最終的な集計：すべてのトークンを処理した後、スタックに複数の要素が残っている場合は、左側から順に演算子を適用して畳み込みを行い、スタックの先頭要素を結果として返します。要素が 1 つだけの場合は、その値をそのまま返します。

それでは、実際の実装例を見ていきましょう。

実装例（Pythonコード）

class Solution:
    def solve(self, s):
        stack = []
        op = {
            "or": lambda x, y: x or y,
            "and": lambda x, y: x and y,
        }
        for v in s.split():
            if v[0] == "(":
                stack.append(v[v.count("(") :] == "T")
            elif v.count(")") > 0:
                ct = v.count(")")
                stack.append(v[:-ct] == "T")
                for _ in range(ct):
                    right = stack.pop()
                    o = stack.pop()
                    left = stack.pop()
                    stack.append(o(left, right))
            elif v in ["T", "F"]:
                stack.append(v == "T")
            else:
                stack.append(op[v])

        if len(stack) > 1:
            for i in range(0, len(stack) - 1, 2):
                stack[i + 2] = stack[i + 1](stack[i], stack[i + 2])
            return stack[-1]

        return stack[0]

ob = Solution()
s = "T and (F or T)"
print(ob.solve(s))

入力

"T and (F or T)"

出力

True

コードのポイント

• 演算子「and」「or」は、それぞれ2つの引数を受け取るラムダ式として辞書 op に登録しておき、必要なときに呼び出せるようにしています。
• 「(F」や「T)」のように、値と括弧が同じトークンに含まれるケースにも対応できるよう、括弧の個数を数えてスライスで除去しています。
• 閉じ括弧「)」が現れた時点で直前の演算を確定させることで、括弧内の式を優先的に評価する仕組みを実現しています。
• 最後にスタックへ複数の要素が残る場合は「値・演算子・値…」という並びになるため、2つずつ間隔をあけてループし、左から順に演算を適用していきます。

このようにスタックを使った処理を組み合わせることで、文字列形式のブール式でも括弧の優先順位を正しく守りながら評価できます。条件式を動的に扱いたい場面などで応用できるテクニックなので、ぜひ参考にしてください。