Pythonで式木（式ツリー）を構築して評価するプログラムの実装方法

はじめに

本記事では、式木（Expression Tree）の後順巡回（後置記法・逆ポーランド記法）の結果が与えられたとき、そこから式木を復元（構築）し、さらにその式を評価して計算結果を求めるプログラムをPythonで実装します。最終的には、構築した式木の根（ルート）と、木全体を評価した値を返します。

問題例

次のような後置記法のトークン列が入力として与えられたとします。

['1', '2', '-', '3', '4', '+', '*']

この列から式木を構築して評価すると、中間記法では (1 - 2) * (3 + 4) に相当し、計算結果は -7 になります。

アルゴリズムの流れ

まず、子の接続位置を表す定数を定義しておきます。

LEFT = 0
RIGHT = 1

1. evaluate() 関数 ― 式木の評価

• 根の値が数値であれば、それを整数に変換して返します（葉＝オペランドの場合）。
• そうでなければ、左の子と右の子をそれぞれ再帰的に評価します。
• 根の演算子に応じて次のように計算します。
  • '+' → 左辺 ＋ 右辺
  • '-' → 左辺 − 右辺
  • '*' → 左辺 × 右辺
  • '/' → 左辺 ÷ 右辺（小数点以下切り捨ての除算）

2. buildTree() 関数 ― 式木の構築

• root を None で初期化し、空のスタックを用意します。
• 後置記法のリストが空になるまで、末尾から要素を1つずつ取り出します。末尾から処理すると、最初に取り出される要素が必ず木の根になるため、効率的に構築できます。
• 取り出した値で新しいノードを作成します。
• root が未設定であれば、このノードを根として登録します。
• スタックが空でなければ、親ノードと「どちら側に接続すべきか」の情報を取り出し、指定された側（左または右）に現在のノードを接続します。
• 現在の値が数値ではなく演算子である場合、このノードにはまだ左・右の子が必要なため、(ノード, LEFT) と (ノード, RIGHT) の2つのタプルをスタックに積みます。
• すべての処理が完了したら root を返します。

Pythonでの実装例

LEFT = 0
RIGHT = 1

class Node():
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def evaluate(root):
    if root.val.isnumeric():
        return int(root.val)
    left_val = evaluate(root.left)
    right_val = evaluate(root.right)
    if root.val == '+':
        return left_val + right_val
    elif root.val == '-':
        return left_val - right_val
    elif root.val == '*':
        return left_val * right_val
    elif root.val == '/':
        return left_val // right_val

def buildTree(postfix):
    root = None
    stack = []
    while postfix:
        curr = postfix.pop()
        curr_node = Node(curr)
        if not root:
            root = curr_node
        if stack:
            parent, side = stack.pop()
            if side == LEFT:
                parent.left = curr_node
            else:
                parent.right = curr_node
        if not curr.isnumeric():
            stack.append((curr_node, LEFT))
            stack.append((curr_node, RIGHT))
    return root

root = buildTree(['1', '2', '-', '3', '4', '+', '*'])
print(evaluate(root))

入力

['1', '2', '-', '3', '4', '+', '*']

出力

-7

まとめ

後置記法の式は、演算子が必ず2つのオペランドの後に現れるという性質を持っています。この性質を利用すれば、リストの末尾から順に処理しながらスタックで未接続の親ノードを管理するだけで、式木を簡単に復元できます。構築した式木は、再帰的な evaluate() 関数によって自然に評価でき、複雑な数式のパースや計算にも応用できる強力な手法です。