C++で式ツリー（Expression Tree）を評価する方法｜再帰を使った実装例

本記事では、+、-、*、/ といった二項演算子から構成される式ツリー（Expression Tree）を評価し、その計算結果を返す問題について解説します。

式ツリーとは

式ツリーは二分木の一種であり、各ノードには演算子またはオペランド（被演算数）が格納されます。ノードの役割は次のように分けられます。

• 葉ノード：演算の対象となる値（オペランド）を保持します。
• 非葉ノード（内部ノード）：実行すべき演算を表す二項演算子を保持します。

式ツリーを中順走査（in-order traversal）すると、元の中置記法の数式が復元できるのが特徴です。

例題で理解しよう

入力：次のような式ツリーが与えられます。

出力：1

解説：式ツリーを数式として読み解くと、

Exp = ((5 + 9) / (2 * 7))
    = (14 / 14)
    = 1

解法アプローチ

最もシンプルな解法は、ルートから順に各ノードの演算を処理していく方法です。扱う演算はすべて二項演算なので、木の各ノードは「子を2つ持つ」か「子を1つも持たない（葉）」のどちらかになります。

そこで再帰を利用して、各ノードの二項演算を解いていきます。処理の流れは以下のとおりです。

1. ノードが NULL の場合は 0 を返します。
2. ノードが葉（左右どちらの子も持たない）であれば、その値を整数に変換して返します。
3. 左部分木と右部分木をそれぞれ再帰的に評価します。
4. 現在のノードの演算子に従って、左右の評価結果を演算し、その結果を返します。

C++での実装例

以下は、この解法の動作を示すC++プログラムです。

#include <bits/stdc++.h>
using namespace std;

class node {
public:
    string value;
    node *left = NULL, *right = NULL;
    node(string x)
    {
        value = x;
    }
};

// 式ツリーを再帰的に評価する関数
int solveExpressionTree(node* root) {

    if (!root)
        return 0;

    // 葉ノードなら値をそのまま返す
    if (!root->left && !root->right)
        return stoi(root->value);

    // 左右の部分木を再帰的に評価
    int leftSubTreeSol = solveExpressionTree(root->left);
    int rightSubTreeSol = solveExpressionTree(root->right);

    // 演算子に応じて計算
    if (root->value == "+")
        return leftSubTreeSol + rightSubTreeSol;

    if (root->value == "-")
        return leftSubTreeSol - rightSubTreeSol;

    if (root->value == "*")
        return leftSubTreeSol * rightSubTreeSol;

    if (root->value == "/")
        return leftSubTreeSol / rightSubTreeSol;

    return -1;
}

int main()
{
    node *root = new node("/");
    root->left = new node("+");
    root->left->left = new node("9");
    root->left->right = new node("5");
    root->right = new node("*");
    root->right->left = new node("2");
    root->right->right = new node("7");
    cout << "式ツリーの評価結果: " << solveExpressionTree(root);
    return 0;
}

実行結果

式ツリーの評価結果: 1

計算量の分析

• 時間計算量：O(n) — 木の各ノードを一度ずつ訪問します（nはノード数）。
• 空間計算量：O(h) — 再帰呼び出しのためのスタック領域が必要です（hは木の高さ）。最悪ケースでは O(n) となります。