式ツリー(構文木)とは？データ構造における構築アルゴリズムをわかりやすく解説

式ツリー(Expression Tree)とは

式ツリー(構文木とも呼ばれます)は、二分木の一種であり、葉ノードに演算対象となる値(オペランド)を持ち、内部ノードにはその値に対して実行される演算子を格納する木構造です。木を下から順に評価することで、式全体の計算結果を求めることができます。

式ツリーの例

たとえば、4 + ((7 + 9) * 2) という数式を表現すると、次のような式ツリーになります。

この式の場合、「7 + 9 = 16」「16 * 2 = 32」「32 + 4 = 36」という順序で計算が進み、最終的な結果は 36 となります。

式ツリーの評価アルゴリズム

式ツリー T の値を再帰的に計算する基本的なアルゴリズムは、以下の通りです。

T が NULL でない場合:
    もし T->data がオペランドならば:
        return T.data
    A = solve(T.left)    // 左部分木を評価
    B = solve(T.right)   // 右部分木を評価
    // A と B に対して 'T.data'(演算子)を適用する
    return calculate(A, B, T.data)

このように、まず左部分木と右部分木をそれぞれ再帰的に評価し、その結果に対して現在のノードが持つ演算子を適用することで、式全体の値が求まります。

式ツリーの構築方法

与えられた式から式ツリーを構築する際には、一般的にスタック(Stack)というデータ構造を利用します。特に、後置記法(逆ポーランド記法)で表現された式を扱うのが基本です。

後置式を先頭から順に走査しながら、以下の手順を実行していきます。

• オペランド(値)を読み取った場合: 新しいノードを作成し、スタックにプッシュします。このノードは、後ほど部分木の一部となります。
• 演算子を読み取った場合: スタックから2つのノードをポップし、それぞれを演算子ノードの子(左の子・右の子)として接続します。その後、作成した演算子ノードをスタックにプッシュします。
• 手順の繰り返し: 上記の手順1と手順2を、式全体の走査が完了するまで繰り返します。
• 最終確認: 走査終了後、スタックに残っているノードが1つだけであることを確認します。それが式ツリーの根(ルート)となり、すべての内部ノードには演算子、すべての葉ノードにはオペランドのみが格納されている状態になっているはずです。

この手法を用いることで、任意の後置式から正しく一意な式ツリーを構築できます。式ツリーは、コンパイラの構文解析や電卓アプリケーションの実装など、幅広い場面で活用されている重要なデータ構造です。