トップ > 論理検索演算子を逆ポーランド記法で評価する

論理検索演算子を逆ポーランド記法で評価する

tl:dr

論理検索を実現するために論理演算子を含むクエリを評価するのに逆ポーランド記法を使ったので、 忘備録を兼ねて、逆ポーランド記法の説明と操作上アルゴリズム、pythonでのコードを残しておく

逆ポーランド記法とは

普段なれているのは1 + 2のような記法ですが、これを中置記法と言われています。

逆ポーランド記法は、演算子を被演算子の後ろにする記法の一種で、後置記法とも言い1 + 2を逆ポーランド記法で記すと、1 2 +となります。

真ん中と後ろ来たら前もあるのか？と思いますが、前もあります。 演算子を前に置いた+ 1 2のような記法を前置記法といい、これをポーランド記法と呼びます。

逆ポーランド記法は、ポーランド記法(前置記法)の演算子と被演算子の順序が逆であることが名前の由来です。

逆ポーランド記法利点は、前から順に式を評価できることにあります。

逆ポーランド記法の評価は先頭からひとつずつ順番に記号を読み込み、 1. 記号が演算子であればスタックに値をつみ 2. 演算子であればスタックから値を２つ取り出して計算する この２つを繰り返すだけというシンプルな操作をするだけですみます。

これが中置記法などの場合は、 演算子に相当するもの記憶するか、読み出す順番を戻すなどの処理が必要になり複雑な操作が必要となります。

いくら評価シンプルになるとはいえ、検索エンジンでユーザーに逆ポーランド記法での入力を強制するのはハードルがとても高いので、一般的な中置記法を逆ポーランド記法に変換する必要があります。

逆ポーランド記法の評価については後述するとして、まずは中置記法を逆ポーランド記法に変換するアルゴリズムから見ていきます。

操車場アルゴリズム

中置記法の構文に従った順番で記号(以下トークン)が並んでいるトークン列(数式や文字列)を構文解析する際に使われるアルゴリズムの一つに操車場アルゴリズムというものがあります。

このアルゴリズムの出力を出力順に並べるとそのまま逆ポーランド記法になります。

このアルゴリズムは、データフローに 1. 入力と出力のトークン列(配列) 2.演算子を保持するスタック(LIFO) があります。

アルゴリズムの説明

※ここで説明するアルゴリズムにはfunc(a, b)のような関数は含んでいません。

読み込むべきトークンが入力列にある限り、以下の操作を繰り返します。

  • 入力列からトークンを一つ取り出す。
  • トークンが被演算子の場合
    • スタックのトップに演算子トークンo2があり、o1が左性結合で優先順位がo2と等しいか低い場合、もしくはo1の優先順位がo2より低い場合は以下を繰り返す
      • o2をスタックからポップして出力キューに追加する
    • 上記以外はスタックにプッシュする トークンを出力列に追加する。
  • トークンが左括弧の場合、トークンをスタックにプッシュする
  • トークンが右括弧の場合
    • スタックからトップにあるトークンが左括弧になるまで、スタックからポップした演算子を出力列に追加する
    • スタックからポップしたトークンが左括弧の場合、出力列には追加せずに捨てる
    • 左括弧がスタックにない場合は、左右の括弧の不一致(エラー)
  • 読むこむべきトークンが入力列にない場合
    • スタックに演算子トークンがある間以下を繰り返す
      • スタックのトップにある演算子がトークンが括弧なら括弧不一致(エラー )
      • 演算子をスタックからポップして出力キューに追加する

処理例

A AND (B OR C) NOT Cの場合

演算子には結合性と優先順位を設定します。

演算子 優先順位 結合性
AND 3 左性結合
OR 2 左性結合
NOT 1 右性結合
入力列 操作 出力列 スタック
['A', 'AND', '(', 'B', 'OR', 'C', ')', 'NOT', 'D]
['AND', '(', 'B', 'OR', 'C', ')', 'NOT', 'D] トークンが被演算子なので出力列に追加 ['A']
['(', 'B', 'OR', 'C', ')', 'NOT', 'D'] トークンが演算子でスタックに演算子がないのでスタックに追加 ['A'] ['AND']
['B', 'OR', 'C', ')', 'NOT', 'D'] トークンが左括弧なのでスタックに追加 ['A'] ['AND', '(']
['OR', 'C', ')', 'NOT', 'D'] トークンが被演算子なので出力列に追加 ['A', B] ['AND', '(']
[ 'C', ')', 'NOT', 'D'] トークンが演算子でスタックに演算子があるが優先順位はORがANDより高いのでスタックに追加 ['A', B] ['AND', '(', "OR"]
[ ')', 'NOT', 'D'] トークンが被演算子なので出力列に追加 ['A', B, C] ['AND', '(', "OR"]
[ 'NOT', 'D'] トークンが右括弧でなのでスタックからポップ。左括弧ではないので出力列に追加する ['A', B, C, OR] ['AND', '(']
[ 'NOT', 'D'] トークンが右括弧でなのでスタックからポップ。左括弧ではないので捨てる ['A', B, C, OR] ['AND']
[ 'D'] トークンが演算子でスタックに演算子があり、が優先順位はNOTがANDより高いのでNOTをスタックに追加 ['A', B, C, OR] ['AND', NOT]
トークンが被演算子なので出力列に追加 ['A', B, C, OR,D] [NOT]
入力列が空だがスタックに左括弧ではない演算子があるのでポップして出力列に追加 ['A', B, C, OR, D、NOT] [AND]
入力列が空だがスタックに左括弧ではない演算子があるのでポップして出力列に追加 ['A', B, C, OR, D、NOT, AND]
入力列もスタックも空なので終了 ['A', B, C, OR, D、NOT, AND] []

python code

LEFT = True
RIGHT = False

OPERATER = {"AND": (1, LEFT), "OR": (2, LEFT), "NOT": (3, RIGHT)}


def is_pop_stack(token, top_opr):
    print(token, top_opr)
    o1 = OPERATER[token]
    o2 = OPERATER[top_opr]
    print(o1, o2)
    if o1[1] is LEFT and o1[0] <= o2[0]:
        return True
    if o1[0] < o2[0]:
        return True
    return False

def parse_rpn(tokens: list):
    # アルゴリズムの実装
    stack = []
    queue = []
    print(tokens)
    for token in tokens:
        print(token)
        # tokenがoperaterならstackにpush
        if token in OPERATER:
            while len(stack) != 0:
                top = stack[-1]
                if top not in OPERATER:
                    break
                if is_pop_stack(token, top):
                    opr = stack.pop()
                    queue.append(opr)
                else:
                    break
            stack.append(token)

        # tokenが左括弧ならstackに追加
        elif token == "(":
            stack.append(token)
        # tokenが右括弧なら
        elif token == ")":
            # 左括弧がでるまでstackからpopしてqueueに追加
            # 左括弧がでればqueueに追加せずに終了
            # 左括弧がでない=stackに左括弧がない場合は括弧不整合でエラー
            while True:
                try:
                    opr = stack.pop()
                except IndexError:
                    raise
                if opr == "(":
                    break
                queue.append(opr)
        else:
            queue.append(token)

    # stackのトップが括弧なら不整合エラー
    if stack and stack[-1] == "(":
        raise

    while True:
        try:
            opr = stack.pop()
        except IndexError:
            break
        queue.append(opr)

    return queue