§1 逆ポーランド記法とは

一般に人が読むことを前提にした数式は「x = 3 * 2 + 1」の様な形式で表記されますが、演算の順序などを考えるとコンピュータにとってはこの表記は扱いにくいものです。 コンピュータとしてはこの式は「x32*1+=」と表記されていたほうが扱いやすくなります。 このような形式での表記が逆ポーランド記法です。

逆ポーランド記法で記述された数式「x32*1+=」は、「xは3と2を掛けたものに1を足して代入したもの」と読むことができます。 より機械的な表現では「xは3と2を*したものに1を+して=したもの」と読むこともできます。 つまり、この表記においては、演算対象と演算処理が処理順に記述されることになります。 プログラミングなどでは「x = 3 * 2 + 1;」といった式を書きますが、実は実行時にはスタックというものを使って逆ポーランド記法的に計算しています。

このように、項の後ろに演算子記号を記述する方式を逆ポーランド記法(後置記法)と言います。 対して、最初に挙げた馴染み深い記法、つまり項の間に演算子を記述する方式を中置記法、項の前に演算子が来る記法をポーランド記法(前置記法)と言います。

§1.1 ポーランド記法化・逆ポーランド記法化と数式計算のデモ

記法を変換するアルゴリズムの解説に入る前に、実際にどのようになるのか見たほうが分かりやすいと思います。 これはこの文書で紹介するアルゴリズムを実装したポーランド記法化・逆ポーランド記法化のデモです。 変換したい数式を入力して、[変換]のボタンを押してください。 (Javascriptを有効にしないと動作しません)

数式のポーランド記法化・逆ポーランド記法化と数式計算のデモ
変換する数式
記入例
  • x = a * (b + c)
  • 2+5*3-4
  • 1+4*2+(7-3)/2
ポーランド記法
(前置記法化した数式)
逆ポーランド記法
(後置記法化した数式)
元の数式から再構成した数式
(中置記法の数式)
数式の計算結果

変換アルゴリズムについてはこの後解説します。 なお、このデモで出来る変換処理についてはCでの実装の項をご覧ください。

§2 二分木を使った逆ポーランド記法化のアルゴリズム

逆ポーランド記法化を行うアルゴリズムには様々なものがあり、一例としてスタックを使うものがありますが、ここではスタックではなく二分木を使って数式を逆ポーランド記法に変換する方法について解説します。 また、二分木に変換した数式を使って数式の計算を行う方法についても解説します。

§2.1 二分木とは

二分木とは節から二本に枝分かれした木のようなデータ構造です。 この木構造は二分探索などのアルゴリズムでよく用いられるデータ構造です。 二分木の構造として、まず根(root)があり、そこから二本に枝分かれします。 枝分かれする元を節(node)、枝分かれした先を葉(leaf)といいます。 根や葉を区別せずに全てまとめてノードと呼ぶこともあります。 また、ある節から見た根本の節を親(parent)といい、節から見た枝(branch)の先を子(child)、同じ親をもつ子同士を兄弟(sibling)といい、親ノード・子ノードなどと呼びます。 さらに、ある節を根とみなし、それ以下の構造を部分木(subtree)とも言います。 二分岐の一例と構造上の名称を図にすると次のようになります。

二分木

実際にプログラミングによって二分木を再現する場合は、次のような構造体を用いることが多いです。 この例では各々のノードが持ちうる値はint型であるとしています。

struct Node
{
    int   data;
    Node* left;
    Node* right;
};

つまり、右と左の子ノードへのポインタと、そのノード自体が持つデータを構造体のメンバとして持つわけです。 子を持たないノード、つまり葉のノードを表すには右と左の子ノードとしてヌル参照を設定します。

§2.2 数式を二分木に変換する

数式を逆ポーランド記法化する前の下準備としてに、式を二分木に変換します。 なぜ二分木にする必要があるのかという点については後述するとして、まずは変換する式として「X=A*B+C」を例にとって二分木に変換する方法を考えてみたいと思います。 まずはじめに、式を二分木に変換する方法を次のように定義します。

ルール1
演算子は2つの部分式(項)を必要とする。 これを二分木で表す場合、演算子の左側の部分式を左の子ノード、演算子の右側の部分式を右の子ノード、演算子自体をノード自身に持つこととする。

つまり、式「A+B」は次のような二分木になるものとします。

A+Bの二分木

さらに、式「X=A+B」について考えてみると、演算子=の左の部分式をX、右の部分式をA+Bと考えることができるので、このような二分木になるものとします。

X=A+Bの二分木

しかし、式「X=A+B」は演算子+を中心として部分式「X=A」と部分式「B」に分けてしまうこともできます。 このままでは式に複数の演算子が含まれている場合にどの演算子で分けるかあいまいなので、次のルールを加えます。

ルール2
式を二分木で表す場合、最も低い優先順位の演算子を選び出して、その演算子を中心に部分式に分けることとする。
ルール3
分けた後の部分式に演算子が含まれる場合は、さらにその節について分割を続ける。

例えば「X=A+B」の場合、A+Bを先に計算し、その結果をXに代入せよと言う意味なので、=は+より優先順位が低いことになります。

ここまでで定めてきたルールに従って、式「X=A*B+C」を二分木に変換する場合について1ステップずつ見ていきます。 まず、この式の中で最も優先順位が低いのは「=」なので、これを中心に、「X」と「A*B+C」に分割します。

XとA*B+C

つぎに、部分式「A*B+C」を二分木に変換します。 この式の中で最も優先順位が低いのは「+」なので、この式は「A*B」と「C」の部分式に分かれます。

XとA*BとC

最後に、「A*B」は「*」を中心に「A」と「B」に分割されるので、

A*BとC

となり、これで式「X=A*B+C」は二分木へと変換されました。

§2.3 二分木から逆ポーランド記法化した数式を得る

ここまでの手順で式を二分木にすることができました。 しかし、なぜ二分木にするのかという点については理由を明らかにしていませんでした。 式を二分木にした理由は、二分木からデータを読み出す順序を定義すると簡単に逆ポーランド記法化した式が得られるためです。

まず、二分木からデータを読み出す方法には三種類あります。 ここではその三種類の方法を示します。 木を探索することをトラバースすると言います。 トラバースする方法によって木から得られるデータの順番が変わってきます。

  1. 先行順序訪問 / 行きがけ順 (preorder traversal)
    1. あるノードNにたどり着いたら、そのノードNのデータを読む
    2. ノードNの左の子ノードLのデータを読む。 ノードLが部分木を持つのであれば1を繰り返す
    3. ノードNの右の子ノードRのデータを読む。 ノードRが部分木を持つのであれば1を繰り返す
    4. ノードNの親ノードへ戻る
  2. 中間順序訪問 / 通りがけ順 (inorder traversal)
    1. あるノードNにたどり着いたら、ノードNの左の子ノードLのデータを読む。 ノードLが部分木を持つのであれば1を繰り返す
    2. ノードNのデータを読む
    3. ノードNの右の子ノードRのデータを読む。 ノードRが部分木を持つのであれば1を繰り返す
    4. ノードNの親ノードへ戻る
  3. 後行順序訪問 / 帰りがけ順 (postorder traversal)
    1. あるノードNにたどり着いたら、ノードNの左の子ノードLのデータを読む。 ノードLが部分木を持つのであれば1を繰り返す
    2. ノードNの右の子ノードRのデータを読む。 ノードRが部分木を持つのであれば1を繰り返す
    3. ノードNのデータを読む
    4. ノードNの親ノードへ戻る

ちょっと分かりにくいかと思いますが、上記の手順を端的に表すと次のようになります。 一筆書きの要領で木を左からなぞって巡回していき、行きがけ順ではノードに到達したとき、通りがけ順では左の子ノードの巡回が終わって右の子ノードに移動するとき、帰りがけ順では右の子ノードの巡回が終わったときノードのデータを読むようにします。 この方法通りにトラバースした場合、次のようになります。

先行順序訪問/行きがけ順でのノードの参照順序 中間順序訪問/通りがけ順でのノードの参照順序 後行順序訪問/帰りがけ順でのノードの参照順序

つまり、行きがけ順では「N→L→R」、通りがけ順では「L→N→R」、帰りがけ順では「L→R→N」の順でデータが読み出されることになります。 ここで、先ほどの式「X=A*B+C」から作った木を各方法でトラバースしてみると、

X=A*B+C

行きがけ順では「=X+*ABC」、通りがけ順では「X=A*B+C」、帰りがけ順では「XAB*C+=」のように読み出されます。 帰りがけ順では、ここでの目的である逆ポーランド化された式が読み出されています。 また、通りがけ順では、我々が一般的に使っている中置記法での式が読み出されています。

このように、式を二分木に変換し、その二分木から帰りがけ順で読み出すことにより、逆ポーランド記法化した式を得ることができます。

§2.4 二分木化した数式を使って計算を行う

ここまででは式から作成した二分木を探索(トラバース)することで式を様々な記法に変換する方法について解説してきましたが、ここからは作成した二分木を使って式の計算を行う方法をみていきます。 ここでは、等号や変数(記号)を含む場合については考えず、簡単化のため定数(数字)と四則演算子のみを含む式の計算を行う方法を考えます。 以下、計算する式として「2+5*3-4」を例にとり、最終的な計算結果として 13 を得るための方法をみていきます。

まず、式「2+5*3-4」を計算する場合、どのような手順をとれば正しい答えが得られるかを考えます。 式「2+5*3-4」は、値「2」と部分式「5*3-4」の演算結果を足したもの(+)と見ることができます。 式全体を計算するには、先に部分式「5*3-4」がどのような値となるかを計算する必要があります。 同様に、式「5*3-4」は部分式「5*3」の演算結果から値「4」を引いたもの(-)と見ることができます。 この部分式「5*3」の結果を求めれば式「5*3-4」の値も求まり、式「2+5*3-4」を計算できることになります。

つまり、まず式を左項・右項と演算子のみの部分式になるまで分割したのち、それぞれの部分式の演算結果を求めていくことにより最終的に式全体の計算結果を得ることができます。 部分式に分割する手順は、先に式を二分木に変換する際に使った手順をそのまま適用することができます。 そこで、この計算手順を二分木にあてはめて考えてみます。

まず、先に使った手順に従って式「2+5*3-4」を二分木に変換すると次の図のようになります。 演算子ノードの子ノードに演算の対象となる部分式または値(オペランド)が位置している点、また演算子の優先順位に従って式の分割を行ったため優先度の高い式が二分木の先端部分に位置している点に着目してください。

二分木化した式「2+5*3-4」

二分木化した式では、すでに左項・右項と演算子のみに分割された状態になっています。 従って、この二分木に対して、

  1. 二分木を根(root)から順に見ていき
  2. ノードに設定されている演算子に従って左項(左の子ノード)と右項(右の子ノード)の値を演算する
  3. このとき、項が部分式の場合(左または右の子ノードがさらに子ノードを持っている場合)は、先に2の操作を繰り返して部分式の演算結果を求める

という操作を行うことにより、最終的に式全体の値、すなわち式の計算結果を得ることができます。 この操作を、式「2+5*3-4」の二分木に対して行なっていくと次のようになります。

二分木化した式の計算 step1

まず、二分木の根を見ると、式は演算子が「+」で左項は値「2」、右項は子ノードを持っているため部分式となります。 部分式「5*3-4」にあたる部分木も左項に部分式「5*3」の子ノードを含んでいるため、まず部分式「5*3」にあたるノードの値を求めます。 このノードは左項が値「5」、右項が値「3」、演算子が「*」であるため、このノードは演算結果として値「15」を持つことになります。

二分木化した式の計算 step2

部分式のノードの値が求まったことにより、上位の部分式の値を求めることができるようになったので、演算を続けます。 このノードは左項が先の演算によって得られた値「15」、右項が値「4」、演算子は「-」であるため、このノードは演算結果として値「11」を持つことになります。

二分木化した式の計算 step3

最終的に、根のノードの左項と右項の値が求まったため、このノードの値を演算した結果、即ち「13」が式「2+5*3-4」の結果となります。 このように、式を演算子と項に分割した二分木に変換し、個々のノードの値を再帰的に演算していくことにより、式の計算を行うことができます。

さて、ここまででアルゴリズムの説明は終わりました。 次は実際にプログラムをみてみましょう。

§3 Cでの実装

ここで紹介するのはCでの実装です。 このプログラムは、

  • 中置記法を二分木に分解し、ポーランド記法(前置記法)、逆ポーランド記法(後置記法)、中置記法で出力
  • 2項演算子のうち、四則演算子(+,-,*,/)、代入演算子(=)が使用可能
  • 演算優先順位の指定に丸括弧()が使用可能
  • 式の途中に空白を含むことも可能
  • 式が四則演算子と数値のみの場合は、式の計算を行うことが可能

となっています。

まずは部分毎に説明していきます。 プログラム全文は最後に掲載しますので、必要に応じて参照してください。 C以外の言語での実装も用意しています。

§3.1 mainとNode構造体

まずは二分木を表現するためのNode型とmain関数でのプログラム全体の流れを見ていきます。

typedef struct Node Node;

#define MAX_NODES   80
#define MAX_EXP_LEN 0x100

struct Node {
    char exp[MAX_EXP_LEN];
    Node* left;
    Node* right;
};

static Node nodes[MAX_NODES];
static int nb_node_used = 0;

Node* create_node()
{
    if (nb_node_used == MAX_NODES)
        return NULL;
    else
        return &nodes[nb_node_used++];
}

void remove_space(char *exp)
{
    char *dst = exp;
    char *src = exp;

    while (*src) {
        if (*src == ' ')
            src++;
        else
            *(dst++) = *(src++);
    }

    *dst = '\0';
}

/*
 * 以下の関数については後述
 */
int parse_expression(Node* node);
void traverse_tree_postorder(Node* node);
void traverse_tree_inorder(Node* node);
void traverse_tree_preorder(Node* node);
double calculate(Node* node);

int main()
{
    Node* root = create_node();

    printf("input expression: ");
    scanf("%[^\n]", root->exp);

    remove_space(root->exp);

    printf("expression: %s\n", root->exp);

    if (parse_expression(root) < 0) {
        fprintf(stderr, "parser error\n");
        return -1;
    }

    printf("reverse polish notation: ");
    traverse_tree_postorder(root);
    printf("\n");

    printf("infix notation: ");
    traverse_tree_inorder(root);
    printf("\n");

    printf("polish notation: ");
    traverse_tree_preorder(root);
    printf("\n");

    printf("calculated result: %f\n", calculate(root));

    return 0;
}

Node型は、

left
左の子ノード(部分木)へのポインタ
right
右の子ノード(部分木)へのポインタ
exp
そのノードの持つ部分式(項または演算子)

を保持します。 最大MAX_NODES個(この例では80としました)のNodeをあらかじめ用意しておき、必要になったらcreate_node()関数で取得することにします。 また一つのNodeに格納できる部分式は終端文字を含めて最大MAX_EXP_LEN文字までとします。

main関数の流れは、

  1. 分解前の式全体を格納しておくため二分木の根、rootを作成
  2. 入力された式をrootにコピー
  3. 変換の前準備として、邪魔になる空白を削除(remove_space)
  4. 式を二分木に分割(parse_expression)
  5. 分割した二分木を
    1. 帰りがけ順でトラバースして表示(traverse_tree_postorder)
    2. 通りがけ順でトラバースして表示(traverse_tree_inorder)
    3. 行きがけ順でトラバースして表示(traverse_tree_preorder)
    4. 計算してその値を取得・表示(calculate)

となります。

§3.2 二分木への分割

次に、入力された式を二分木への分割を行う部分の関数を見てみます。

int remove_bracket(char *exp)
{
    size_t i;
    size_t len = strlen(exp);
    int nest = 1;

    if (!(exp[0] == '(' && exp[len - 1] == ')'))
        return 0;

    for (i = 1; i < len - 1; i++) {
        if (exp[i] == '(')
            nest++;
        else if (exp[i] == ')')
            nest--;

        if (nest == 0)
            return 0;
    }

    if (nest != 1) {
        fprintf(stderr, "unbalanced bracket: %s\n", exp);
        return -1;
    }

    for (i = 0; i < len - 2; i++) {
        exp[i] = exp[i + 1];
    }
    exp[i] = '\0';

    if (exp[0] == '(')
        remove_bracket(exp);

    return 0;
}

size_t get_pos_operator(char *exp)
{
    size_t i;
    size_t pos_op = -1;
    int nest = 0;
    int priority;
    int priority_lowest = 4;

    if (!exp)
        return -1;

    for (i = 0; exp[i]; i++) {
        switch (exp[i]) {
            case '=': priority = 1; break;
            case '+': priority = 2; break;
            case '-': priority = 2; break;
            case '*': priority = 3; break;
            case '/': priority = 3; break;
            case '(': nest++; continue;
            case ')': nest--; continue;
            default: continue;
        }

        if (nest == 0 && priority <= priority_lowest) {
            priority_lowest = priority;
            pos_op = i;
        }
    }

    return pos_op;
}

int parse_expression(Node* node)
{
    size_t pos_op;
    size_t len_exp;

    if (!node)
        return -1;

    pos_op = get_pos_operator(node->exp);

    if (pos_op == (size_t)-1) {
        node->left  = NULL;
        node->right = NULL;

        return 0;
    }

    len_exp = strlen(node->exp);

    // left-hand side
    node->left  = create_node();

    if (!node->left) {
        fprintf(stderr, "expression too long\n");
        return -1;
    }

    strncpy(node->left->exp, node->exp, pos_op);

    if (remove_bracket(node->left->exp) < 0)
        return -1;

    if (parse_expression(node->left) < 0)
        return -1;

    // right-hand side
    node->right = create_node();

    if (!node->right) {
        fprintf(stderr, "expression too long\n");
        return -1;
    }

    strncpy(node->right->exp, node->exp + pos_op + 1, len_exp - pos_op);

    if (remove_bracket(node->right->exp) < 0)
        return -1;

    if (parse_expression(node->right) < 0)
        return -1;

    // operator
    node->exp[0] = node->exp[pos_op];
    node->exp[1] = '\0';

    return 0;
}

parse_expressionの流れを簡単に説明すると、

  1. まずget_pos_operatorで最も優先順位の低い演算子の位置を取得する
    1. 演算子がなかった場合は、二分木への分割が完了したとして処理を終える
  2. 演算子があった場合は、その演算子を中心に左右の部分式へ分割する
    1. ここで、remove_bracketで分割した部分式に含まれる、最も外側の括弧を削除する
    2. 分割した部分式について、parse_expressionでさらに分割する

となっています。 parse_expressionは分割した部分式に演算子が含まれる限り、再帰的に呼び出され分割を繰り返します。 get_pos_operatorは、部分式のうち、括弧で括られていない部分で、かつ最も優先順位の低い演算子の位置を返します。

§3.3 二分木のトラバース

続いて、二分木のトラバースを行う関数を見てみます。

void traverse_tree_postorder(Node* node)
{
    if (node->left)
        traverse_tree_postorder(node->left);
    if (node->right)
        traverse_tree_postorder(node->right);

    printf(node->exp);
}

void traverse_tree_inorder(Node* node)
{
    if (node->left && node->right)
        printf("(");

    if (node->left)
        traverse_tree_inorder(node->left);

    printf(node->exp);

    if (node->right)
        traverse_tree_inorder(node->right);

    if (node->left && node->right)
        printf(")");
}

void traverse_tree_preorder(Node* node)
{
    printf(node->exp);

    if (node->left)
        traverse_tree_preorder(node->left);

    if (node->right)
        traverse_tree_preorder(node->right);
}

順に、帰りがけ順、通りがけ順、行きがけ順でトラバースする関数です。 与えられたノードに対してノードの持つ値の表示を行い、子ノードがある場合は再帰的にトラバースします。 なお、通りがけ順では見やすさのために括弧を付けて表示します。

§3.4 二分木からの値の演算

続いて、二分木から値の演算を行う関数を見てみます。

double calculate(Node* node)
{
    double left_operand, right_operand;

    if (node->left && node->right) {
        left_operand  = calculate(node->left);
        right_operand = calculate(node->right);

        if (0 == strcmp(node->exp, "+"))
            return left_operand + right_operand;
        else if (0 == strcmp(node->exp, "-"))
            return left_operand - right_operand;
        else if (0 == strcmp(node->exp, "*"))
            return left_operand * right_operand;
        else if (0 == strcmp(node->exp, "/"))
            return left_operand / right_operand;
        else
            return 0.0;
    }
    else {
        return atof(node->exp);
    }
}

calculate関数では、与えられたノードについて、

  1. 左と右の両方に子ノードを持つ場合
    1. 再帰的にcalculate関数を呼び出すことで左と右の部分木の計算結果を求め
    2. 求めた左項・右項の値を使い、ノード自体の持つ演算子に従って演算結果を返す
  2. 子ノードを持たない場合
    1. atof関数により文字列からdoubleに変換することでノード自身の持つ値を返す

という処理を行います。 再帰呼び出しを行うことにより、末端の部分木から順次値が定まって行きます。 この関数では0除算や、値を数値に変換できない場合などは考慮していません。

§3.5 プログラム全文

最後に、プログラム全文と実行例です。

// gcc polish.c -o polish
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node Node;

#define MAX_NODES   80
#define MAX_EXP_LEN 0x100

struct Node {
    char exp[MAX_EXP_LEN];
    Node* left;
    Node* right;
};

static Node nodes[MAX_NODES];
static int nb_node_used = 0;

Node* create_node()
{
    if (nb_node_used == MAX_NODES)
        return NULL;
    else
        return &nodes[nb_node_used++];
}

void remove_space(char *exp)
{
    char *dst = exp;
    char *src = exp;

    while (*src) {
        if (*src == ' ')
            src++;
        else
            *(dst++) = *(src++);
    }

    *dst = '\0';
}

int remove_bracket(char *exp)
{
    size_t i;
    size_t len = strlen(exp);
    int nest = 1;

    if (!(exp[0] == '(' && exp[len - 1] == ')'))
        return 0;

    for (i = 1; i < len - 1; i++) {
        if (exp[i] == '(')
            nest++;
        else if (exp[i] == ')')
            nest--;

        if (nest == 0)
            return 0;
    }

    if (nest != 1) {
        fprintf(stderr, "unbalanced bracket: %s\n", exp);
        return -1;
    }

    for (i = 0; i < len - 2; i++) {
        exp[i] = exp[i + 1];
    }
    exp[i] = '\0';

    if (exp[0] == '(')
        remove_bracket(exp);

    return 0;
}

size_t get_pos_operator(char *exp)
{
    size_t i;
    size_t pos_op = -1;
    int nest = 0;
    int priority;
    int priority_lowest = 4;

    if (!exp)
        return -1;

    for (i = 0; exp[i]; i++) {
        switch (exp[i]) {
            case '=': priority = 1; break;
            case '+': priority = 2; break;
            case '-': priority = 2; break;
            case '*': priority = 3; break;
            case '/': priority = 3; break;
            case '(': nest++; continue;
            case ')': nest--; continue;
            default: continue;
        }

        if (nest == 0 && priority <= priority_lowest) {
            priority_lowest = priority;
            pos_op = i;
        }
    }

    return pos_op;
}

int parse_expression(Node* node)
{
    size_t pos_op;
    size_t len_exp;

    if (!node)
        return -1;

    pos_op = get_pos_operator(node->exp);

    if (pos_op == (size_t)-1) {
        node->left  = NULL;
        node->right = NULL;

        return 0;
    }

    len_exp = strlen(node->exp);

    // left-hand side
    node->left  = create_node();

    if (!node->left) {
        fprintf(stderr, "expression too long\n");
        return -1;
    }

    strncpy(node->left->exp, node->exp, pos_op);

    if (remove_bracket(node->left->exp) < 0)
        return -1;

    if (parse_expression(node->left) < 0)
        return -1;

    // right-hand side
    node->right = create_node();

    if (!node->right) {
        fprintf(stderr, "expression too long\n");
        return -1;
    }

    strncpy(node->right->exp, node->exp + pos_op + 1, len_exp - pos_op);

    if (remove_bracket(node->right->exp) < 0)
        return -1;

    if (parse_expression(node->right) < 0)
        return -1;

    // operator
    node->exp[0] = node->exp[pos_op];
    node->exp[1] = '\0';

    return 0;
}

void traverse_tree_postorder(Node* node)
{
    if (node->left)
        traverse_tree_postorder(node->left);
    if (node->right)
        traverse_tree_postorder(node->right);

    printf(node->exp);
}

void traverse_tree_inorder(Node* node)
{
    if (node->left && node->right)
        printf("(");

    if (node->left)
        traverse_tree_inorder(node->left);

    printf(node->exp);

    if (node->right)
        traverse_tree_inorder(node->right);

    if (node->left && node->right)
        printf(")");
}

void traverse_tree_preorder(Node* node)
{
    printf(node->exp);

    if (node->left)
        traverse_tree_preorder(node->left);

    if (node->right)
        traverse_tree_preorder(node->right);
}

double calculate(Node* node)
{
    double left_operand, right_operand;

    if (node->left && node->right) {
        left_operand  = calculate(node->left);
        right_operand = calculate(node->right);

        if (0 == strcmp(node->exp, "+"))
            return left_operand + right_operand;
        else if (0 == strcmp(node->exp, "-"))
            return left_operand - right_operand;
        else if (0 == strcmp(node->exp, "*"))
            return left_operand * right_operand;
        else if (0 == strcmp(node->exp, "/"))
            return left_operand / right_operand;
        else
            return 0.0;
    }
    else {
        return atof(node->exp);
    }
}

int main()
{
    Node* root = create_node();

    printf("input expression: ");
    scanf("%[^\n]", root->exp);

    remove_space(root->exp);

    printf("expression: %s\n", root->exp);

    if (parse_expression(root) < 0) {
        fprintf(stderr, "parser error\n");
        return -1;
    }

    printf("reverse polish notation: ");
    traverse_tree_postorder(root);
    printf("\n");

    printf("infix notation: ");
    traverse_tree_inorder(root);
    printf("\n");

    printf("polish notation: ");
    traverse_tree_preorder(root);
    printf("\n");

    printf("calculated result: %f\n", calculate(root));

    return 0;
}
実行例1
input expression: x = y * 4 + (2-z) /3
expression: x=y*4+(2-z)/3
reverse polish notation: xy4*2z-3/+=
infix notation: (x=((y*4)+((2-z)/3)))
polish notation: =x+*y4/-2z3
calculated result: 0.000000
実行例2
input expression: 1+4*2+(7-3)/2
expression: 1+4*2+(7-3)/2
reverse polish notation: 142*+73-2/+
infix notation: ((1+(4*2))+((7-3)/2))
polish notation: ++1*42/-732
calculated result: 11.000000

§4 他の言語での実装

ここまでで紹介したアルゴリズムをC以外の言語で実装したものを以下のページに掲載しておきます。 比較して読めるように、いずれもCでの実装に近い記述にしてあります。

なお、最初に挙げたデモはJavascriptで実装しています。 ソースコードについてはこのページのソースに含まれています。

§5 文書情報

2013-07-02
二分木に変換した数式の計算を行うアルゴリズムについてを加筆
用語の不統一を修正
VB8での実装のバグを修正
2012-07-09
変換のデモを追加
Javascriptでの実装を追記
Javaでの実装を追記
C以外の実装を別ページに分離して掲載
2009-06-03
アルゴリズムの説明に加筆・修正
Cでの実装の説明を修正
new/deleteを用いた実装を削除
C# 1.0での実装を削除
C# 3.0, VB8, Rubyでの実装を追記
2009-03-21
new/deleteを用いない実装を追記
2003-02-08
初版公開