後置記法（逆ポーランド記法）の式から式木を構築するC++プログラム

式木（Expression Tree）とは、数式を木構造として表現するために用いられる二分木の一種です。式木では、演算子（+、-、*、/ など）が内部ノードに対応し、オペランド（被演算子）が葉ノードに対応します。本記事では、後置記法（ポストフィックス記法、いわゆる逆ポーランド記法）で与えられた式から式木を構築し、その結果を行きがけ順（前順）、通りがけ順（中間順）、帰りがけ順（後順）の3つの方法で巡回して出力するC++プログラムを紹介します。

たとえば、後置記法の式「762*+6+」は、中間記法では「7+6*2+6」に相当します。式を木構造に変換することで、式の構造を視覚的に把握できるようになり、コンパイラや電卓アプリなどでの式の評価処理にも広く応用されています。

アルゴリズム

開始
　　関数 r()：1文字を引数として受け取り、その種類を判定する。
　　　　文字が + 、- 、* 、/ のいずれかならば
　　　　　　-1 を返す（演算子であることを示す）
　　　　文字が A〜Z の範囲ならば
　　　　　　1 を返す（オペランドであることを示す）
　　　　文字が a〜z の範囲ならば
　　　　　　1 を返す（オペランドであることを示す）
　　　　それ以外の場合
　　　　　　-100 を返す
　　関数 construct_expression_tree()：後置記法の式から式木を構築する
　　関数 push()：ノードをスタックに積む
　　関数 pop()：ノードをスタックから取り出す
　　関数 preOrder()：前順巡回（行きがけ順）を実行する
　　関数 inOrder()：中間順巡回（通りがけ順）を実行する
　　関数 postOrder()：後順巡回（帰りがけ順）を実行する
終了。

式木の構築手順

後置記法の式を左から右へ走査しながら、以下の手順で式木を組み立てます。

• オペランドの場合：新しいノードを作成し、スタックにプッシュします。
• 演算子の場合：スタックから2つのノードをポップし、演算子を保持する新しいノードの子として接続します（先にポップしたノードを右の子、次にポップしたノードを左の子とする）。その後、新しいノードをスタックにプッシュします。

走査が完了した時点で、スタックに残っているノードが式木の根（ルート）となります。

サンプルコード

#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 {
            p1 = pop();
            p2 = pop();
            newl = new n;
            newl->d = s;
            newl->l = p2;
            newl->r = p1;
            push(newl);
        }
        s = suffix[i];
    }
}
void preOrder(n *tree) {
    if (tree != NULL) {
        cout << tree->d;
        preOrder(tree->l);
        preOrder(tree->r);
    }
}
void inOrder(n *tree) {
    if (tree != NULL) {
        inOrder(tree->l);
        cout << tree->d;
        inOrder(tree->r);
    }
}
void postOrder(n *tree) {
    if (tree != NULL) {
        postOrder(tree->l);
        postOrder(tree->r);
        cout << tree->d;
    }
}
int main(int argc, char **argv) {
    cout << "Enter Postfix Expression : ";
    cin >> pf;
    construct_expression_tree(pf);
    cout << "\nIn-Order Traversal : ";
    inOrder(a[0]);
    cout << "\nPre-Order Traversal : ";
    preOrder(a[0]);
    cout << "\nPost-Order Traversal : ";
    postOrder(a[0]);
    return 0;
}

実行結果

Enter Postfix Expression : 762*+6+
In-Order Traversal : 7+6*2+6
Pre-Order Traversal : ++7*626
Post-Order Traversal : 762*+6+

出力の読み方

• 中間順巡回（In-Order）： 「7+6*2+6」と出力され、中間記法（通常の数式の書き方）の形式になります。
• 前順巡回（Pre-Order）： 「++7*626」と出力され、前置記法（ポーランド記法）の形式になります。
• 後順巡回（Post-Order）： 「762*+6+」と出力され、入力した元の後置記法の式と完全に一致します。