C++で前置記法（プレフィックス記法）の式から式木を構築するプログラム

式木（Expression Tree）は、数式を表現するために用いられる二分木の一種です。式木では、内部ノードが演算子に対応し、葉ノードがオペランド（被演算子）に対応します。この記事では、前置記法（プレフィックス記法）で与えられた式から式木を構築し、中間順（インオーダー）、前置順（プレオーダー）、後置順（ポストオーダー）の3種類の走査で出力するC++プログラムを紹介します。

式木とは？

例えば、前置記法の式「++7*626」は、次のような二分木として表現できます。

          +
        /   \
       +     6
      / \
     7   *
        / \
       6   2

根および内部ノードには演算子（+, -, *, / など）が配置され、その子としてオペランド（数字）が接続されます。同じ木でも、走査する順序を変えることで、前置記法・中間記法・後置記法それぞれの式を取り出せるのが大きな特徴です。

アルゴリズム

開始
    以下のメンバ関数を持つクラス ExpressionTree を定義する：

    関数 push()：ノードをスタックに積む
    もしスタックが空なら
        ノードを最初の要素としてプッシュする
    そうでなければ
        ノードをプッシュし、それを先頭（top）にする

    関数 pop()：ノードをスタックから取り出す
    もしスタックが空なら
        「アンダーフロー」を出力する
    そうでなければ
        ノードを取り出して返し、top を更新する

    関数 insert()：文字を挿入する
    もし数字なら
        新しいノードを作成してプッシュする
    そうでなく演算子なら
        2つのノードをポップし、演算子ノードの子として連結してプッシュする
    それ以外なら
        「無効な式です」と出力する

    関数 postOrder()：後置順走査
    木が空でなければ
        postOrder(ptr->l)
        postOrder(ptr->r)
        ptr->d を出力する

    関数 inOrder()：中間順走査
    木が空でなければ
        inOrder(ptr->l)
        ptr->d を出力する
        inOrder(ptr->r)

    関数 preOrder()：前置順走査
    木が空でなければ
        ptr->d を出力する
        preOrder(ptr->l)
        preOrder(ptr->r)
終了

C++サンプルコード

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;

class TreeN { // ノードの宣言
public:
    char d;
    TreeN *l, *r;
    TreeN(char d) {
        this->d = d;
        this->l = NULL;
        this->r = NULL;
    }
};

class StackNod { // スタックの宣言
public:
    TreeN *treeN;
    StackNod *n;
    StackNod(TreeN *treeN) { // コンストラクタ
        this->treeN = treeN;
        n = NULL;
    }
};

class ExpressionTree {
private:
    StackNod *top;
public:
    ExpressionTree() {
        top = NULL;
    }
    void clear() {
        top = NULL;
    }

    void push(TreeN *ptr) {
        if (top == NULL)
            top = new StackNod(ptr);
        else {
            StackNod *nptr = new StackNod(ptr);
            nptr->n = top;
            top = nptr;
        }
    }

    TreeN *pop() {
        if (top == NULL) {
            cout << "アンダーフロー" << endl;
        } else {
            TreeN *ptr = top->treeN;
            top = top->n;
            return ptr;
        }
    }

    TreeN *peek() {
        return top->treeN;
    }

    void insert(char val) {
        if (isDigit(val)) {
            TreeN *nptr = new TreeN(val);
            push(nptr);
        } else if (isOperator(val)) {
            TreeN *nptr = new TreeN(val);
            nptr->l = pop();
            nptr->r = pop();
            push(nptr);
        } else {
            cout << "無効な式です" << endl;
            return;
        }
    }

    bool isDigit(char ch) {
        return ch >= '0' && ch <= '9';
    }

    bool isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    }

    int toDigit(char ch) {
        return ch - '0';
    }

    void buildTree(string eqn) {
        // 文字列を右端から左端へ向かって1文字ずつ処理する
        for (int i = eqn.length() - 1; i >= 0; i--)
            insert(eqn[i]);
    }

    void postfix() {
        postOrder(peek());
    }

    void postOrder(TreeN *ptr) {
        if (ptr != NULL) {
            postOrder(ptr->l);
            postOrder(ptr->r);
            cout << ptr->d;
        }
    }

    void infix() {
        inOrder(peek());
    }

    void inOrder(TreeN *ptr) {
        if (ptr != NULL) {
            inOrder(ptr->l);
            cout << ptr->d;
            inOrder(ptr->r);
        }
    }

    void prefix() {
        preOrder(peek());
    }

    void preOrder(TreeN *ptr) {
        if (ptr != NULL) {
            cout << ptr->d;
            preOrder(ptr->l);
            preOrder(ptr->r);
        }
    }
};

int main() {
    string s;
    ExpressionTree et;
    cout << "\n前置記法で式を入力してください: ";
    cin >> s;
    et.buildTree(s);
    cout << "\nPrefix（前置順）: ";
    et.prefix();
    cout << "\n\nInfix（中間順）: ";
    et.infix();
    cout << "\n\nPostfix（後置順）: ";
    et.postfix();
}

実行結果

前置記法で式を入力してください: ++7*626
Prefix（前置順）: ++7*626
Infix（中間順）: 7+6*2+6
Postfix（後置順）: 762*+6+

プログラムのポイント

• 右から左へ処理する： 前置記法の式は演算子が先頭に来るため、buildTree() では文字列を末尾（右端）から先頭（左端）へ向かって1文字ずつ読み込みます。
• スタックで部分木を管理： 数字はそのままノードとしてスタックにプッシュされ、演算子を読み込んだ時点で2つのノードをポップして子として連結し、完成した部分木を再びスタックに戻します。
• 1つの木から3つの記法を取得： 走査の順序（根を先に訪問するか・後に訪問するか）を変えるだけで、前置・中間・後置の各式が得られます。

このように、スタックと再帰的な木の走査を組み合わせることで、前置記法の式を効率的に解析し、さまざまな形式の式へ変換することができます。コンパイラや電卓アプリなど、数式を扱うプログラムの基礎となる重要なテクニックなので、ぜひマスターしておきましょう。