C++で式ツリー（Expression Tree）アルゴリズムを実装するプログラム

式ツリー（Expression Tree）とは、数式を表現するために用いられる二分木のことです。式ツリーでは、内部ノード（親ノード）が演算子に対応し、各葉ノードがオペランド（被演算子）に対応します。

本記事では、後置記法（ポーランド逆記法）の式を入力として受け取り、対応する式ツリーを構築し、それを中順走査（インオーダー走査）で出力するC++プログラムを紹介します。後置記法は括弧が不要なため、コンピュータによる式の解析に非常に適した記法です。

アルゴリズム

Begin
    function construct_expression_tree():
        オペランドの場合 Flag = 1
        演算子の場合 Flag = -1
        S = suffix[0] （式から最初の文字を読み込む）
    For i = 0 、s != 0 の間繰り返す
        シンボルがオペランドか演算子かを判定する
        中順走査のため関数 void inorder() を呼び出す
        結果を出力する
        i をインクリメントする
End.

サンプルコード

#include <iostream>
using namespace std;

struct n { // ノードの宣言
    char d;
    n *l;
    n *r;
};
char pf[50];
int top = -1;
n *a[50];
int r(char inputch) { // シンボルが演算子かオペランドかを判定する
    if (inputch == '+' || inputch == '-' || inputch == '*' || inputch == '/')
        return (-1);
    else if (inputch >= 'A' || inputch <= 'Z')
        return (1);
    else if (inputch >= 'a' || inputch <= 'z')
        return (1);
    else
        return (-100);
}
void push(n *tree) { // スタックに要素を追加する
    top++;
    a[top] = tree;
}
n *pop() {
    top--;
    return (a[top + 1]);
}
void construct_expression_tree(char *suffix) {
    char s;
    n *newl, *p1, *p2;
    int flag;
    s = suffix[0];
    for (int i = 1; s != 0; i++) {
        flag = r(s);
        if (flag == 1) {
            // オペランドの場合：新しいノードを作成してスタックに積む
            newl = new n;
            newl->d = s;
            newl->l = NULL;
            newl->r = NULL;
            push(newl);
        } else {
            // 演算子の場合：スタックから2つのノードを取り出し、
            // 新しいノードの子として接続する
            p1 = pop();
            p2 = pop();
            newl = new n;
            newl->d = s;
            newl->l = p2;
            newl->r = p1;
            push(newl);
        }
        s = suffix[i];
    }
}

void inOrder(n *tree) { // 中順走査を行う
    if (tree != NULL) {
        inOrder(tree->l);
        cout << tree->d;
        inOrder(tree->r);
    }
}

int main(int argc, char **argv) {
    cout << "Enter Postfix Expression : ";
    cin >> pf;
    construct_expression_tree(pf);
    cout << "\nInfix Expression : ";
    inOrder(a[0]);
    return 0;
}

処理の流れ

このプログラムの中核となる construct_expression_tree() 関数は、以下の手順で動作します。

1. 入力された後置記法の文字列を先頭から1文字ずつ読み込みます。
2. 関数 r() により、その文字が演算子かオペランドかを判定します。
3. オペランドであれば、新しいノードを作成してスタックにプッシュします。
4. 演算子であれば、スタックからノードを2つポップし、その演算子ノードの左右の子として設定したうえで、再びスタックにプッシュします。
5. すべての文字を処理すると、スタックの先頭に完成した式ツリーの根（ルート）が残ります。

最後に inOrder() 関数による中順走査を行うことで、式ツリーから中置記法（通常の数式の書き方）の式が復元されて出力されます。

実行結果

Enter Postfix Expression : 762*+6+
Infix Expression : 7+6*2+6

このように、後置記法の式「762*+6+」を入力すると、対応する中置記法の式「7+6*2+6」が出力されます。なお、この実装では演算子の優先順位を示す括弧は出力されないため、実際の応用では必要に応じて括弧の付与処理を追加することをおすすめします。