逆ポーランド記法とは何か、数式を逆ポーランド記法化するとどのようになるか、また二分木を使って数式を逆ポーランド記法化するアルゴリズムC言語による実装を紹介します。

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

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

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

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

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

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

このデモを実行するにはEdge・Chrome・Firefox・Safariいずれかのブラウザをご利用ください。 なお、Edgeでは変換過程・計算過程のアニメーションは表示されません。

このデモでできる変換処理と制限事項についてはCでの実装の項をご覧ください。

数式のポーランド記法化・逆ポーランド記法化と数式計算のデモ
変換する数式

          
記入例
  • x = 1 - 2 + 3
  • x = a * (b + c)
  • 2 + 5 * 3 - 4
  • 1.0+2/.3/(0-1)
  • 1 + 2 + X = Y + 3 + 4
ポーランド記法
(前置記法化した数式)
逆ポーランド記法
(後置記法化した数式)
元の数式から再構成した数式
(中置記法の数式)
数式の計算結果
二分木化した数式と記法の変換過程
ポーランド記法・前置記法
placeholder
SVG-SMIL animationに対応したブラウザでご覧ください。

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

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

§2.1 二分木とは

二分木(binary tree)とは節から二本に枝分かれした木(tree)のようなデータ構造です。 この木構造は二分探索などのアルゴリズムでよく用いられるデータ構造です。

二分木の構造として、まず根(root)があり、そこから二本に枝分かれします。 枝分かれする元を節(node)、枝分かれした先を葉(leaf)といいます。 ただ一般に、根・節・葉は特に強調する必要がある場合を除くと全てまとめてノードと呼ばれることがほとんどで、根を表す場合にルートノードと呼ばれることがある程度です。

また、あるノードから見た根本側のノードを親(parent)または親ノードといい、あるノードから枝分かれした先のノードを子(child)または子ノードといいます。 二分木では常に二本に枝分かれするため、子ノードを持つ場合は左の子ノード右の子ノードの2つを持つことになります。 ルートノードから枝分かれする二分木全体をと呼ぶのに対して、あるノードをルートノードとみなし、その下位に枝分かれする部分を部分木(subtree)と呼びます。

二分木の一例と構造上の名称を図にすると次のようになります。

二分木の構造と名称
ルートノード・親ノード・子ノード
subtree of '((leaf node leaf) root (child parent child))' subtree of '(leaf node leaf)' subtree of 'leaf' leaf subtree of 'leaf' leaf node subtree of '(child parent child)' subtree of 'child' child subtree of 'child' child parent root
二分木の構造と名称
木と部分木
subtree of '(node root (node node node))' tree subtree of 'node' node subtree of '(node node node)' subtree subtree of 'node' node subtree of 'node' node node root

また、プログラミングによって二分木のデータ構造を表現する場合は、次のような構造体を用いることが多いです。

二分木を表現するデータ構造の例
struct Node
{
    int   data;
    Node* left;
    Node* right;
};

つまり、ノード自体が持つデータと、右と左の子ノードへのポインタを構造体のメンバとして持つわけです。 子を持たないノードを表すにはleftおよびrightにヌル参照を設定するなどします。 また、この例では各々のノードが持ちうる値はint型であるとしていますが、扱うデータに応じて型を選択します。

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

数式を逆ポーランド記法化する前の下準備として、まずは式を二分木に変換します。 なぜ二分木にする必要があるのか、どのような利点があるのかという点については後述するとして、まずは式を二分木に変換する手順について考え、例として式x = 1 - 2 + 3手順を適用する場合を見ていきます。

§2.2.1 変換手順の定義

まずはじめに、式を二分木に変換する手順を次のように定義します。

ルール0(前提条件)
演算子は左右に1つずつ、計2つの部分式または項を持つものとする。
ルール1
式を二分木に変換する場合、演算子をノード自身に、演算子の左側の部分式を左の子ノードに、演算子の右側の部分式を右の子ノードに、それぞれ分けて持つこととする。

A + Bの場合を考えると、演算子+・左側の部分式A・右側の部分式Bからなるため、ルール1に従うと次のような二分木になります。

式「A + B」の二分木
subtree of '(A + B)' subtree of 'A' A subtree of 'B' B +

つぎに、式X = A + Bについて考えてみると、演算子=・左側の部分式X・右側の部分式A + Bからなるため、ルール1に従うと次のような二分木になります。

式「X=A+B」の二分木(1)
subtree of '(X = A + B)' subtree of 'X' X subtree of 'A + B' A + B =

ここで、もうひとつ手順を定義します。

ルール2
左右の子ノードに分けた部分式に演算子が含まれる場合は、さらにルール1を適用して部分式が項のみとなるまで繰り返す。

この右側の子ノードの部分式A + Bは演算子を含んでいるため、ルール2に従うことになります。 ルール2に従いこの部分式A + Bにルール1を適用すると、先ほどの式A + Bと同じ二分木となります。 したがって、式X = A + B全体では次のような二分木になります。

式「X=A+B」の二分木(2)
subtree of '(X = (A + B))' subtree of 'X' X subtree of '(A + B)' subtree of 'A' A subtree of 'B' B + =

しかし、ここまでで定義したルールでは単に「演算子の左側・右側で部分式に分ける」としています。 そのため、式X = A + Bは演算子+を中心として部分式X = Aと部分式Bに分けることもできてしまいます。

つまり、先に定義したルール1とルール2だけでは、式に複数の演算子が含まれている場合どの演算子で分けるかがあいまいになります。 そこで、次のルールを加えることにします。

ルール3
ルール1で式を演算子と部分式に分ける際、式中で最も右側にあり、かつ最も優先順位が低い演算子を選び出して、その演算子を中心に部分式に分けることとする。
演算子の優先順位は、高いものから順に 1:*/ 2:+- 3:=とする。

このルールを、いくつかの式にあてはめて確認すると次のようになります。

1 + 2 * 3の場合
*よりも優先順位が低い+を中心にして部分式に分ける。 (「部分式1 + 2演算子*部分式3」ではなく「部分式1演算子+部分式2 * 3」として分ける)
1 - 2 + 3の場合
-よりも右側にある+を中心にして部分式に分ける。 (「部分式1演算子-部分式2 + 3」ではなく「部分式1 - 2演算子+部分式3」として分ける)

以上3つのルールで式を二分木に変換する手順が定まりました。

演算子の優先順位の高い順に左側から計算するという計算時のルールとは逆になっているように見える点については、計算の優先順位を括弧で表した際、式1 + 2 * 3(1 + 2) * 3ではなく1 + (2 * 3)であり、式1 - 2 + 31 - (2 + 3)ではなく(1 - 2) + 3であることを考えると、本質的には同義であることがわかると思います。 異なるのは、先に計算すべき部分式を選ぶか、後で計算すべき演算子を選ぶか、という違いです。

式中に括弧()を含む場合については、ここでは簡単化のために省略しています。 括弧を含む場合を考慮するなら、「括弧の中にある演算子は、他の演算子よりも優先度が高いものとする」といったルールを加えることになります。 なお、§.Cでの実装で掲載しているプログラムでは、こういった定義に従い括弧を含む式を扱うようにしています。

§2.2.2 変換手順の適用

ここまでで定めてきたルールに従って、式x = 1 - 2 + 3を二分木に変換する場合について1ステップずつ見ていきます。

式「x = 1 - 2 + 3」の二分木(1)
式を分割する前の状態
subtree of 'x = 1 - 2 + 3' x = 1 - 2 + 3

まず、この式において最も右側にあり優先順位が低い演算子は=です。 これを中心に、左の部分式xと右の部分式1 - 2 + 3に分け、左右の子ノードにします。 元になったノードは演算子=のみのノードにします。

式「x = 1 - 2 + 3」の二分木(2)
式全体を部分式「x」と部分式「1 - 2 + 3」に分割
subtree of '(x = 1 - 2 + 3)' subtree of 'x' x subtree of '1 - 2 + 3' 1 - 2 + 3 =

つぎに、右の子ノードに分けられた部分式1 - 2 + 3は演算子を含むため、これをさらに二分木に変換します。 この部分式において最も右側にあり優先順位が低い演算子は+です。 これを中心に、左の部分式1 - 2と右の部分式3に分け、左右の子ノードにします。 元になったノードは演算子+のみのノードにします。

式「x = 1 - 2 + 3」の二分木(3)
部分式「1 - 2 + 3」を「1 - 2」と「3」に分割
subtree of '(x = (1 - 2 + 3))' subtree of 'x' x subtree of '(1 - 2 + 3)' subtree of '1 - 2' 1 - 2 subtree of '3' 3 + =

最後に、左の子ノードに分けられた部分式1 - 2も同じように二分木に変換します。 元になったノードは演算子-のノードにし、左の部分式1と右の部分式2に分け、左右の子ノードにします。

式「x = 1 - 2 + 3」の二分木(4)
部分式「1 - 2」を「1」と「2」に分割
subtree of '(x = ((1 - 2) + 3))' subtree of 'x' x subtree of '((1 - 2) + 3)' subtree of '(1 - 2)' subtree of '1' 1 subtree of '2' 2 - subtree of '3' 3 + =

これですべての部分式は演算子を含まないとなったため、二分木への変換手順は完了となり、式x = 1 - 2 + 3全体が二分木へと変換されました。

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

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

§2.3.1 二分木からデータを読み出す順序

まず、二分木からデータを読み出す方法には次の三種類があります。 ノードを巡回(traverse)してデータを読み出す順序によって、木から得られるデータの順番も変わってきます。 三種類の巡回順序はそれぞれ次のとおりです。

  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の親ノードへ戻る

言葉での表現では分かりにくいかと思いますが、上記の手順を擬似コードと図で表すと次のようになります。

先行順序訪問の擬似コード
traverse(N)
{
  read(N);

  if (N.L)
    traverse(N.L);

  if (N.R)
    traverse(N.R);

  return;
}
先行順序訪問
行きがけ順でのノードの参照順序
subtree of '(L N R)' subtree of 'L' L subtree of 'R' R N traversal order of (L N R) traversed expressions #1: 'N' 1 N #2: 'L' 2 L #3: 'R' 3 R path of #0 path of #1 path of #1 path of #2 path of #2 path of #2 path of #3 #1: 'N' 1 N #2: 'L' 2 L #3: 'R' 3 R
中間順序訪問の擬似コード
traverse(N)
{
  if (N.L)
    traverse(N.L);

  read(N);

  if (N.R)
    traverse(N.R);

  return;
}
中間順序訪問
通りがけ順でのノードの参照順序
subtree of '(L N R)' subtree of 'L' L subtree of 'R' R N traversal order of (L N R) traversed expressions #1: 'L' 1 L #2: 'N' 2 N #3: 'R' 3 R path of #0 path of #0 path of #1 path of #1 path of #2 path of #2 path of #3 #1: 'L' 1 L #2: 'N' 2 N #3: 'R' 3 R
後行順序訪問の擬似コード
traverse(N)
{
  if (N.L)
    traverse(N.L);

  if (N.R)
    traverse(N.R);

  read(N);

  return;
}
後行順序訪問
帰りがけ順でのノードの参照順序
subtree of '(L N R)' subtree of 'L' L subtree of 'R' R N traversal order of (L N R) traversed expressions #1: 'L' 1 L #2: 'R' 2 R #3: 'N' 3 N path of #0 path of #0 path of #1 path of #1 path of #1 path of #2 path of #2 #1: 'L' 1 L #2: 'R' 2 R #3: 'N' 3 N

どの巡回順序でも、一筆書きの要領で木を左からなぞるようにすべてのノードを巡回するところは共通していますが、巡回したノードのデータを読むタイミングが異なります。 ノードからデータを読むタイミングのみに着目して比較すると、それぞれ次のようになります。

行きがけ順
左右の子ノードの巡回を始める前
通りがけ順
左右の子ノードの巡回の途中(左の子ノードの巡回が終わった後、かつ、右の子ノードの巡回を始める前)
帰りがけ順
左右の子ノードの巡回が終わった後

このような順序でそれぞれデータを読むと、上図のように異なった順序でデータが読み出されます。 つまり、行きがけ順ではNLR、通りがけ順ではLNR、帰りがけ順ではLRNの順でデータが読み出されることになります。

§2.3.2 式の二分木への適用

では、これを式から変換した二分木にあてはめた場合を考えてみます。 ここでは式A + Bを例にとってみていきます。 この式の二分木に対して先の3つの順序でノードのデータを読み出していくと次のようになります。

行きがけ順での式の二分木の読み出し
subtree of '(A + B)' subtree of 'A' A subtree of 'B' B + traversal order of (A + B) traversed expressions #1: '+' 1 + #2: 'A' 2 A #3: 'B' 3 B path of #0 path of #1 path of #1 path of #2 path of #2 path of #2 path of #3 #1: '+' 1 + #2: 'A' 2 A #3: 'B' 3 B
通りがけ順での式の二分木の読み出し
subtree of '(A + B)' subtree of 'A' A subtree of 'B' B + traversal order of (A + B) traversed expressions #1: 'A' 1 A #2: '+' 2 + #3: 'B' 3 B path of #0 path of #0 path of #1 path of #1 path of #2 path of #2 path of #3 #1: 'A' 1 A #2: '+' 2 + #3: 'B' 3 B
帰りがけ順での式の二分木の読み出し
subtree of '(A + B)' subtree of 'A' A subtree of 'B' B + traversal order of (A + B) traversed expressions #1: 'A' 1 A #2: 'B' 2 B #3: '+' 3 + path of #0 path of #0 path of #1 path of #1 path of #1 path of #2 path of #2 #1: 'A' 1 A #2: 'B' 2 B #3: '+' 3 +

行きがけ順では+ABの順、つまり+ A Bとなりポーランド記法(前置記法)に、通りがけ順ではA+Bの順、つまりA + Bとなり中置記法に、帰りがけ順ではAB+の順、つまりA B +となり逆ポーランド記法(後置記法)に、それぞれ読み出されることになります。

このように、二分木化した式から行きがけ/順通りがけ順/帰りがけ順の各順序でノードを読み出していくと、それぞれポーランド記法/中置記法/逆ポーランド記法となった式が得られることになります。 逆ポーランド記法化した数式を得るために式を二分木に変換した目的は、これがその理由となります。


さて、これで逆ポーランド記法化した数式を得る手順が整いました。 先ほどの式x = 1 - 2 + 3から変換した二分木に対して、3つの順序を当てはめて巡回し、各記法に変換した数式を得てみます。

行きがけ順での式の二分木の読み出し
subtree of '(x = ((1 - 2) + 3))' subtree of 'x' x subtree of '((1 - 2) + 3)' subtree of '(1 - 2)' subtree of '1' 1 subtree of '2' 2 - subtree of '3' 3 + = traversal order of (x = ((1 - 2) + 3)) traversed expressions #1: '=' 1 = #2: 'x' 2 x #3: '+' 3 + #4: '-' 4 - #5: '1' 5 1 #6: '2' 6 2 #7: '3' 7 3 path of #0 path of #1 path of #1 path of #2 path of #2 path of #2 path of #3 path of #3 path of #4 path of #4 path of #5 path of #5 path of #5 path of #6 path of #6 path of #6 path of #6 path of #7 path of #7 #1: '=' 1 = #2: 'x' 2 x #3: '+' 3 + #4: '-' 4 - #5: '1' 5 1 #6: '2' 6 2 #7: '3' 7 3
SVG-SMIL animationに対応したブラウザでご覧ください。
通りがけ順での式の二分木の読み出し
subtree of '(x = ((1 - 2) + 3))' subtree of 'x' x subtree of '((1 - 2) + 3)' subtree of '(1 - 2)' subtree of '1' 1 subtree of '2' 2 - subtree of '3' 3 + = traversal order of (x = ((1 - 2) + 3)) traversed expressions #1: 'x' 1 x #2: '=' 2 = #3: '1' 3 1 #4: '-' 4 - #5: '2' 5 2 #6: '+' 6 + #7: '3' 7 3 path of #0 path of #0 path of #1 path of #1 path of #2 path of #2 path of #2 path of #2 path of #3 path of #3 path of #4 path of #4 path of #5 path of #5 path of #5 path of #6 path of #6 path of #7 path of #7 #1: 'x' 1 x #2: '=' 2 = #3: '1' 3 1 #4: '-' 4 - #5: '2' 5 2 #6: '+' 6 + #7: '3' 7 3
SVG-SMIL animationに対応したブラウザでご覧ください。
帰りがけ順での式の二分木の読み出し
subtree of '(x = ((1 - 2) + 3))' subtree of 'x' x subtree of '((1 - 2) + 3)' subtree of '(1 - 2)' subtree of '1' 1 subtree of '2' 2 - subtree of '3' 3 + = traversal order of (x = ((1 - 2) + 3)) traversed expressions #1: 'x' 1 x #2: '1' 2 1 #3: '2' 3 2 #4: '-' 4 - #5: '3' 5 3 #6: '+' 6 + #7: '=' 7 = path of #0 path of #0 path of #1 path of #1 path of #1 path of #1 path of #1 path of #2 path of #2 path of #2 path of #3 path of #3 path of #4 path of #4 path of #4 path of #5 path of #5 path of #6 path of #6 #1: 'x' 1 x #2: '1' 2 1 #3: '2' 3 2 #4: '-' 4 - #5: '3' 5 3 #6: '+' 6 + #7: '=' 7 =
SVG-SMIL animationに対応したブラウザでご覧ください。

行きがけ順では= x + - 1 2 3、通りがけ順ではx = 1 - 2 + 3、帰りがけ順ではx 1 2 - 3 + =のように読み出されます。

このように、式を二分木に変換し、その二分木から帰りがけ順で読み出すことにより、逆ポーランド記法化した式を得ることができます。 また、ノードの巡回順序を変えるだけで異なる記法での式を得られることから、数式をポーランド記法⇆中置記法⇆逆ポーランド記法へと相互に記法変換するように応用することもできます。 さらにこの後で述べるように、与えられた数式を計算することにも応用することができます。

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

ここまででは、式から作成した二分木を巡回することで式を様々な記法に変換する方法について解説してきました。 ここからは作成した二分木を使って式の計算を行う方法を考えていきます。

ここでは、等号=や変数(記号)を含む場合については考えず、簡単化のため定数(数字)と四則演算子のみを含む式の計算を行う方法を考えます。 以下、計算する式として2 + 5 * 3 - 4を例にとり、最終的な計算結果として13を得るための方法を考えていきます。

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

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

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

二分木化した式「2 + 5 * 3 - 4」
subtree of '((2 + (5 * 3)) - 4)' ((2 + (5 * 3)) - 4) subtree of '(2 + (5 * 3))' (2 + (5 * 3)) subtree of '2' 2 subtree of '(5 * 3)' (5 * 3) subtree of '5' 5 subtree of '3' 3 * + subtree of '4' 4 -

二分木化した式では、すでに左項・右項と演算子のみに分割された状態になっています。 この二分木の末端部分から順に値を求めていけば、最終的に木全体の値、すなわち式の計算結果を得ることができます。 つまり手順としては、

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

という操作を行うことにより、計算結果を得ることができます。

まず、二分木の根を見ると、演算子は-、左項は部分木を持っているため部分式、右項は値4となっています。 左の部分木(部分式2 + 5 * 3にあたる部分)も、さらに右側に部分木(部分式5 * 3にあたる部分)を持っているため、まずはこのノードの値を求めます。

二分木化した式「2 + 5 * 3 - 4」の計算
計算開始前の状態
subtree of '((2 + (5 * 3)) - 4)' ((2 + (5 * 3)) - 4) subtree of '(2 + (5 * 3))' (2 + (5 * 3)) subtree of '2' 2 subtree of '(5 * 3)' (5 * 3) subtree of '5' 5 subtree of '3' 3 * + subtree of '4' 4 -

このノードは左項が値5、右項が値3、演算子が*であるため、このノードは演算結果として値15を持つことになります。

二分木化した式「2 + 5 * 3 - 4」の計算
過程1
expression tree after calculation step #1 = '5 * 3' subtree of '((2 + 15) - 4)' subtree of '(2 + 15)' subtree of '2' 2 subtree of '15' 15 + subtree of '4' 4 - initial expression tree subtree of '((2 + (5 * 3)) - 4)' subtree of '(2 + (5 * 3))' subtree of '2' 2 subtree of '(5 * 3)' subtree of '5' 5 subtree of '3' 3 * + subtree of '4' 4 -

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

二分木化した式「2 + 5 * 3 - 4」の計算
過程2
expression tree after calculation step #2 = '2 + 15' subtree of '(17 - 4)' subtree of '17' 17 subtree of '4' 4 - expression tree after calculation step #1 subtree of '((2 + 15) - 4)' subtree of '(2 + 15)' subtree of '2' 2 subtree of '15' 15 + subtree of '4' 4 -

最終的に、根のノードの左項と右項の値が求まったため、このノードの値を演算した結果、すなわち値13が式2 + 5 * 3 - 4の計算結果となります。

二分木化した式「2 + 5 * 3 - 4」の計算
過程3
expression tree after calculation step #3 = '17 - 4' subtree of '13' 13 expression tree after calculation step #2 subtree of '(17 - 4)' subtree of '17' 17 subtree of '4' 4 -

このように、式を演算子と項に分割した二分木へと変換し、個々のノードの値を再帰的に演算していくことにより、式の計算を行うことができます。

二分木化した式「2 + 5 * 3 - 4」の計算過程
expression tree after calculation step #3 = '17 - 4' subtree of '13' 13 expression tree after calculation step #2 = '2 + 15' subtree of '(17 - 4)' subtree of '17' 17 subtree of '4' 4 - expression tree after calculation step #1 = '5 * 3' subtree of '((2 + 15) - 4)' subtree of '(2 + 15)' subtree of '2' 2 subtree of '15' 15 + subtree of '4' 4 - initial expression tree subtree of '((2 + (5 * 3)) - 4)' subtree of '(2 + (5 * 3))' subtree of '2' 2 subtree of '(5 * 3)' subtree of '5' 5 subtree of '3' 3 * + subtree of '4' 4 -

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

§3 Cでの実装

以下で紹介するのはC言語での実装です。 このプログラムは、ここまでで解説してきたアルゴリズムを用いて数式の二分木化と各記法での表示、計算を行うものです。

このプログラムは以下のことが可能で、冒頭に掲載しているデモと同様に動作します。

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

一方、電卓のような用途を目的としたプログラムとしては不完全ではあるものの、アルゴリズムの説明の範囲を超えるため、以下の点は制限事項としています。

  • +1-1などの符号付きの値は、左項がない不正な式として扱う ((0+1), (0-1)として記述することで代用可能)
  • 数値の間に空白を含んでいる場合は無視する (1 2 + 312+3として扱われる)
  • 暗黙の乗算を含む部分式に関する動作は未定義 (この実装では式2(1+2)は項2(1+2)として扱われ、部分式の分割および計算はされない)
  • 式の計算に関して
    • 計算できる部分式のみが計算されるため、x + 1 = 2 + 1の計算結果は((x+1)=3)となる
    • 数学的には等価な式でも、二分木への分割のされ方により計算される場合とされない場合がある (例:X + 1 + 21 + 2 + X)
    • ゼロ除算やオーバーフローは考慮しておらず、また浮動小数点型を用いているため式によっては計算誤差なども生じる

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

§3.1 データ構造とプログラムの概略

まずは二分木を表現するためのNode型と、main関数でのプログラム全体の流れを見ていきます。 (プログラム全文は§.プログラム全文を参照してください。)

§3.1.1 データ構造

二分木を表現するためのデータ構造は、Node型として次のように実装します。

Node型
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]; // あらかじめ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++];
}
Copyright© 2017 . Released under the MIT License.

Node型は次の3つの値を保持します。

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

また、Node型はあらかじめ最大MAX_NODES個(この例では80としました)を配列として用意しておき、必要になったらcreate_node()関数を呼び出すことで取得するようにします。 なお、各Nodeexpに格納できる部分式は終端文字を含めて最大MAX_EXP_LEN文字(この例では256)までとします。

§3.1.2 main関数

main関数でのプログラム全体の流れ、およびその他の関数の定義は次のとおりです。

mainから呼び出すその他の関数の定義
/*
 * 以下の関数については後述
 */
int parse_expression(Node* node);
void traverse_postorder(Node* node);
void traverse_inorder(Node* node);
void traverse_preorder(Node* node);
int calculate(Node* node);
main関数と前処理のための関数
// 文字列から空白を取り除く関数
void remove_space(char *exp)
{
    char *dst = exp;
    char *src = exp;

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

    *dst = '\0';
}

// 式exp内の括弧の対応を検証する関数
// 開き括弧と閉じ括弧が同数でない場合はエラーとして0以外、同数の場合は0を返す
int validate_bracket_balance(char *exp)
{
    int i;
    int nest = 0; // 丸括弧の深度(くくられる括弧の数を計上するために用いる)

    // 1文字ずつ検証する
    for (i = 0; exp[i]; i++) {
        if ('(' == exp[i]) {
            // 開き丸括弧なので深度を1増やす
            nest++;
        }
        else if (')' == exp[i]) {
            // 閉じ丸括弧なので深度を1減らす
            nest--;

            // 深度が負になった場合
            if (nest < 0)
                // 式中で開かれた括弧よりも閉じ括弧が多いため、その時点でエラーとする
                // 例:"(1+2))"などの場合
                break;
        }
    }

    // 深度が0でない場合
    if (0 != nest)
        // 式中に開かれていない/閉じられていない括弧があるので、エラーとする
        // 例:"((1+2)"などの場合
        fprintf(stderr, "unbalanced bracket: %s\n", exp);

    return nest;
}

int main()
{
    // 二分木の根(root)ノードを作成する
    Node* root = create_node();

    // 標準入力から二分木に分割したい式を入力して、式全体をroot->expに格納する
    printf("input expression: ");
    scanf("%[^\n]", root->exp);

    // 入力された式から空白を除去する
    remove_space(root->exp);

    // 入力された式における括弧の対応数をチェックする
    if (0 != validate_bracket_balance(root->exp))
        return -1;

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

    // 根ノードに格納した式を二分木へと分割する
    if (parse_expression(root) < 0)
        return -1;

    // 分割した二分木を帰りがけ順で巡回して表示する(前置記法/逆ポーランド記法で表示される)
    printf("reverse polish notation: ");
    traverse_postorder(root);
    printf("\n");

    // 分割した二分木を通りがけ順で巡回して表示する(中置記法で表示される)
    printf("infix notation: ");
    traverse_inorder(root);
    printf("\n");

    // 分割した二分木を行きがけ順で巡回して表示する(後置記法/ポーランド記法で表示される)
    printf("polish notation: ");
    traverse_preorder(root);
    printf("\n");

    // 分割した二分木から式全体の値を計算する
    if (calculate(root) < 0) {
        // (式の一部あるいは全部が)計算できなかった場合は、計算結果の式を中置記法で表示する
        printf("calculated expression: ");
        traverse_inorder(root);
        printf("\n");
    }
    else {
        // 計算できた場合はその値を表示する
        printf("calculated result: %s\n", root->exp);
    }

    return 0;
}
Copyright© 2017 . Released under the MIT License.

main関数の流れは、

  1. 分割前の式全体を格納しておくため二分木の根、rootを作成
  2. 入力された式をroot->expに格納
  3. 二分木への変換の前準備として、
    1. 式中から邪魔になる空白を削除(remove_space)
    2. 式中の括弧が正しく対応しているかを検証(validate_bracket_balance)
  4. 式を二分木に分割(parse_expression)
  5. 分割した二分木を
    1. 帰りがけ順で巡回して表示する(traverse_postorder)
    2. 通りがけ順で巡回して表示する(traverse_inorder)
    3. 行きがけ順で巡回して表示する(traverse_preorder)
    4. 計算する(calculate)
      1. 計算できた場合はその値、できなかった場合は中置記法(通りがけ順で巡回)した結果を表示する

となります。

§3.2 二分木への分割

次に、入力された式から二分木への分割を行う部分の関数parse_expressionを見ていきます。 この関数は、二分木への分割に際して、式の最も外側にある丸括弧を削除する関数remove_outer_most_bracket、および、式中の演算子の位置を取得する関数get_pos_operatorを呼び出します。

二分木への分割を行う関数群
// 式expから最も外側にある丸括弧を取り除く関数
// (成功した場合は0、エラーの場合は-1を返す)
int remove_outer_most_bracket(char *exp)
{
    int i;
    size_t len;
    int has_outer_most_bracket = 0; // 最も外側に括弧を持つかどうか(0=持たない、1=持つ)
    int nest = 0; // 丸括弧の深度(式中で開かれた括弧が閉じられたかどうか調べるために用いる)

    if ('(' == exp[0]) {
        // 0文字目が開き丸括弧の場合、最も外側に丸括弧があると仮定する
        has_outer_most_bracket = 1;
        nest = 1;
    }

    // 1文字目以降を1文字ずつ検証
    for (i = 1, len = 1; exp[i]; i++, len++) {
        if ('(' == exp[i]) {
            // 開き丸括弧なので深度を1増やす
            nest++;
        }
        else if (')' == exp[i]) {
            // 閉じ丸括弧なので深度を1減らす
            nest--;

            // 最後の文字以外で開き丸括弧がすべて閉じられた場合、最も外側には丸括弧がないと判断する
            // 例:"(1+2)+(3+4)"などの場合
            if (0 == nest && exp[i + 1]) {
                has_outer_most_bracket = 0;
                break;
            }
        }
    }

    // 最も外側に丸括弧がない場合は、何もしない
    if (0 == has_outer_most_bracket)
        return 0;

    // 文字列の長さが2未満の場合は、つまり空の丸括弧"()"なのでエラーとする
    if (len <= 2) {
        fprintf(stderr, "empty bracket: %s\n", exp);
        return -1;
    }

    // 最初と最後の文字を取り除く(最も外側の丸括弧を取り除く)
    for (i = 0; i < len - 2; i++) {
        exp[i] = exp[i + 1];
    }
    exp[i] = '\0';

    // 取り除いた後の文字列の最も外側に括弧が残っている場合
    // 例:"((1+2))"などの場合
    if ('(' == exp[0] && ')' == exp[i - 1])
        // 再帰的に呼び出して取り除く
        return remove_outer_most_bracket(exp);
    else
        // そうでない場合は処理を終える
        return 0;
}

// 式expから最も右側にあり、かつ優先順位が低い演算子を探して位置を返す関数
// (演算子がない場合は-1を返す)
int get_pos_operator(char *exp)
{
    int i;
    int pos_operator = -1; // 現在見つかっている演算子の位置(初期値として-1=演算子なしを設定)
    int priority_current = INT_MAX; // 現在見つかっている演算子の優先順位(初期値としてINT_MAXを設定)
    int nest = 0; // 丸括弧の深度(括弧でくくられていない部分の演算子を「最も優先順位が低い」と判断するために用いる)
    int priority;

    if (!exp)
        return pos_operator;

    // 与えられた文字列を先頭から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;
        }

        // 括弧の深度が0(丸括弧でくくられていない部分)かつ、
        // 現在見つかっている演算子よりも優先順位が同じか低い場合
        // (優先順位が同じ場合は、より右側に同じ優先順位の演算子があることになる)
        if (0 == nest && priority <= priority_current) {
          // 最も優先順位が低い演算子とみなし、その位置を保存する
          priority_current = priority;
          pos_operator = i;
        }
    }

    // 見つかった演算子の位置を返す
    return pos_operator;
}

// 与えられたノードnodeの式expを二分木へと分割する関数
// (成功した場合は0、エラーの場合は-1を返す)
int parse_expression(Node* node)
{
    int pos_operator;
    size_t len;

    if (!node)
        return -1;

    // 式expから最も外側にある丸括弧を取り除く
    if (remove_outer_most_bracket(node->exp) < 0)
        return -1;

    // 式expから演算子を探して位置を取得する
    pos_operator = get_pos_operator(node->exp);

    if (-1 == pos_operator) {
        // 式expに演算子が含まれない場合、expは項であるとみなす
        // (左右に子ノードを持たないノードとする)
        node->left  = NULL;
        node->right = NULL;
        return 0;
    }

    len = strlen(node->exp);

    if (0 == pos_operator || (len - 1) == pos_operator) {
      // 演算子の位置が式の先頭または末尾の場合は不正な式とする
        fprintf(stderr, "invalid expression: %s\n", node->exp);
        return -1;
    }

    // 以下、演算子の位置をもとに左右の部分式に分割する

    // 左側・右側のノードを作成する
    node->left   = create_node();
    node->right  = create_node();

    if (!node->left || !node->right) {
        // ノードが作成できない場合は、式が長過ぎるためエラーとする
        fprintf(stderr, "expression too long\n");
        return -1;
    }

    // 演算子の左側を左の部分式としてノードを構成する
    memset(node->left->exp, 0, MAX_EXP_LEN);
    strncpy(node->left->exp, node->exp, pos_operator);

    // 左側のノード(部分式)について、再帰的に二分木へと分割する
    if (parse_expression(node->left) < 0)
        return -1;

    // 演算子の右側を右の部分式としてノードを構成する
    memset(node->right->exp, 0, MAX_EXP_LEN);
    strncpy(node->right->exp, node->exp + pos_operator + 1, len - pos_operator);

    // 右側のノード(部分式)について、再帰的に二分木へと分割する
    if (parse_expression(node->right) < 0)
        return -1;

    // 残った演算子部分をこのノードに設定する
    node->exp[0] = node->exp[pos_operator];
    node->exp[1] = '\0';

    return 0;
}
Copyright© 2017 . Released under the MIT License.

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

  1. まず、remove_outer_most_bracketで分割する部分式に含まれる、最も外側の丸括弧を削除する (例:(1+2)1+2にする)
    1. 空の括弧の場合は、不正な式と判断して処理を終える (例:node->exp()の場合)
  2. 次に、get_pos_operatorで最も右側にあり、かつ優先順位の低い演算子の位置を取得する
    1. 演算子がなかった場合は、二分木への分割が完了したとして処理を終える (例:node->exp12などの場合)
    2. 演算子が式の先頭または末尾にあった場合は、不正な式と判断して処理を終える (例:node->exp1-+1などの場合)
    3. 演算子があった場合は、その演算子を中心として左右の部分式へ分割する
      1. node->leftおよびnode->rightに新しくノードを作成(create_node)して代入する
      2. node->expから、左右それぞれの部分式にあたる部分をnode->left->expおよびnode->right->expにコピーしたのち、node->expに演算子のみを残す
      3. node->leftおよびnode->rightに対してparse_expressionを呼び出すことで、左右それぞれの部分式を再帰的に分割していく

となっています。

ここでget_pos_operatorは、部分式のうち、丸括弧( )で括られていない部分で、最も右側にあり、かつ最も優先順位の低い演算子の位置を返します。 例えば式1*(2+3)の場合は、*の位置が分割すべき位置として判断されます。 なお、演算子の優先順位は低い方から次の順で定義しています。

  1. =
  2. +および-
  3. *および/

parse_expressionは、分割された部分式に演算子が含まれる限り、再帰的に呼び出され、式の分割を繰り返します。

§3.3 二分木の巡回

続いて、二分木の巡回を行う関数traverse_postorder, traverse_inorder, traverse_preorderを見ていきます。

二分木の巡回を行う関数群
// 後行順序訪問(帰りがけ順)で二分木を巡回して
// すべてのノードの演算子または項を表示する関数
void traverse_postorder(Node* node)
{
    // 左右に子ノードをもつ場合、表示する前にノードを再帰的に巡回する
    if (node->left)
        traverse_postorder(node->left);
    if (node->right)
        traverse_postorder(node->right);

    // 巡回を終えた後でノードの演算子または項を表示する
    // (読みやすさのために項の後に空白を補って表示する)
    printf("%s ", node->exp);
}

// 中間順序訪問(通りがけ順)で二分木を巡回して
// すべてのノードの演算子または項を表示する関数
void traverse_inorder(Node* node)
{
    // 左右に項を持つ場合、読みやすさのために項の前に開き括弧を補う
    if (node->left && node->right)
        printf("(");

    // 表示する前に左の子ノードを再帰的に巡回する
    if (node->left) {
        traverse_inorder(node->left);

        // 読みやすさのために空白を補う
        printf(" ");
    }

    // 左の子ノードの巡回を終えた後でノードの演算子または項を表示する
    printf("%s", node->exp);

    // 表示した後に右の子ノードを再帰的に巡回する
    if (node->right) {
        // 読みやすさのために空白を補う
        printf(" ");

        traverse_inorder(node->right);
    }

    // 左右に項を持つ場合、読みやすさのために項の後に閉じ括弧を補う
    if (node->left && node->right)
        printf(")");
}

// 先行順序訪問(行きがけ順)で二分木を巡回して
// すべてのノードの演算子または項を表示する関数
void traverse_preorder(Node* node)
{
    // 巡回を始める前にノードの演算子または項を表示する
    // (読みやすさのために項の後に空白を補って表示する)
    printf("%s ", node->exp);

    // 左右に子ノードをもつ場合、表示した後にノードを再帰的に巡回する
    if (node->left)
        traverse_preorder(node->left);
    if (node->right)
        traverse_preorder(node->right);
}
Copyright© 2017 . Released under the MIT License.

それぞれtraverse_postorderが帰りがけ順、traverse_inorderが通りがけ順、traverse_preorderが行きがけ順で巡回する関数です。 各関数とも、与えられたノードnodeに対して、ノードの持つ値(node->exp)の表示を行い、子ノード(node->left, node->right)がある場合は再帰的に巡回します。 値の表示と再帰呼出しの順序を変えることで、ノードの巡回順序も変わることに注目してください。

なお、これらの関数では結果のわかりやすさのために、各ノードの値の間に空白を補って表示します。 またtraverse_inorderでは丸括弧も補って表示しています。

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

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

二分木から値の演算を行う関数
// 与えられたノードの演算子と左右の子ノードの値から、ノードの値を計算する関数
// ノードの値が計算できた場合は0、そうでない場合(記号を含む場合など)は-1を返す
// 計算結果はnode->expに文字列として代入する
int calculate(Node* node)
{
    double left_operand, right_operand;

    // 左右に子ノードを持たない場合、ノードは部分式ではなく項であり、
    // それ以上計算できないので0(成功)を返す
    if (!node->left && !node->right)
        return 0;

    // 左右の子ノードについて、再帰的にノードの値を計算する
    calculate(node->left);
    calculate(node->right);

    // 計算した左右の子ノードの値を数値型(double)に変換して演算子の左項・右項の値とする
    if (1 != sscanf(node->left->exp,  "%lf", &left_operand) || 
        1 != sscanf(node->right->exp, "%lf", &right_operand)) {
        // 変換できない場合(左右の子ノードが記号を含む式などの場合)は、
        // ノードの値が計算できないものとして、-1(失敗)を返す
        return -1;
    }

    // ノードの演算子に応じて左右の子ノードの値を演算し、
    // 演算した結果を文字列に変換して再度node->expに代入することで現在のノードの値とする
    switch (node->exp[0]) {
      case '+': snprintf(node->exp, MAX_EXP_LEN, "%.15lg", left_operand + right_operand); break;
      case '-': snprintf(node->exp, MAX_EXP_LEN, "%.15lg", left_operand - right_operand); break;
      case '*': snprintf(node->exp, MAX_EXP_LEN, "%.15lg", left_operand * right_operand); break;
      case '/': snprintf(node->exp, MAX_EXP_LEN, "%.15lg", left_operand / right_operand); break;
      // 上記以外の演算子の場合は計算できないものとして、-1(失敗)を返す
      default: return -1;
    }

    // 左右の子ノードの値からノードの値が求まったため、
    // このノードは左右に子ノードを持たない値のみのノードとする
    node->left  = NULL;
    node->right = NULL;

    // 計算できたため、0(成功)を返す
    return 0;
}
Copyright© 2017 . Released under the MIT License.

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

  1. 左右の両方に子ノードを持たない場合
    1. node->expには項の値が設定されているため、それ以上計算できないものとして処理を終える
  2. 左右の両方に子ノードを持つ場合
    1. 再帰的にcalculate関数を呼び出すことで左右の部分木の計算結果を求める
    2. sscanf関数を用いて、node->left->expおよびnode->right->expの値を文字列からdoubleへと変換することで、左項・右項の値を得る
      1. 変換できない場合は、左項または右項がそれ以上計算できないものとして処理を終える
    3. 得られた左項・右項の値と、node->expに設定されている演算子にしたがって演算を行う
    4. snprintf関数を用いて、演算結果の値を再度node->expに文字列として格納する
    5. node->leftおよびnode->rightNULLを設定し、nodeを値のみのノードとする

という処理を行います。 calculate関数を左右のノードに対して再帰的に呼び出すことにより、末端の部分木から順次値が定まっていきます。 すべての部分木の値が定まることで、最終的に木全体の値(つまり式の演算結果)が求まります。

なお、この関数ではゼロ除算(1/0)やオーバーフローなどについては考慮していません。 また、部分式に数値に変換できない文字が含まれている場合は、部分式の値が計算できないものと判断します。

X+1+2と式1+2+Xでは異なる結果となります。 式がどのように二分木に分割され、計算されるかを考察すると結果が異なる理由がわかります。

§3.5 プログラム全文

最後に、プログラム全文とコンパイル・実行例です。 なお、このプログラムはMIT Licenseにて公開します。 複製・改変・再配布は、ライセンスに従った形で行ってください。

polish.c
// gcc polish.c -o polish && ./polish
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.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]; // あらかじめ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++];
}

// 式expから最も外側にある丸括弧を取り除く関数
// (成功した場合は0、エラーの場合は-1を返す)
int remove_outer_most_bracket(char *exp)
{
    int i;
    size_t len;
    int has_outer_most_bracket = 0; // 最も外側に括弧を持つかどうか(0=持たない、1=持つ)
    int nest = 0; // 丸括弧の深度(式中で開かれた括弧が閉じられたかどうか調べるために用いる)

    if ('(' == exp[0]) {
        // 0文字目が開き丸括弧の場合、最も外側に丸括弧があると仮定する
        has_outer_most_bracket = 1;
        nest = 1;
    }

    // 1文字目以降を1文字ずつ検証
    for (i = 1, len = 1; exp[i]; i++, len++) {
        if ('(' == exp[i]) {
            // 開き丸括弧なので深度を1増やす
            nest++;
        }
        else if (')' == exp[i]) {
            // 閉じ丸括弧なので深度を1減らす
            nest--;

            // 最後の文字以外で開き丸括弧がすべて閉じられた場合、最も外側には丸括弧がないと判断する
            // 例:"(1+2)+(3+4)"などの場合
            if (0 == nest && exp[i + 1]) {
                has_outer_most_bracket = 0;
                break;
            }
        }
    }

    // 最も外側に丸括弧がない場合は、何もしない
    if (0 == has_outer_most_bracket)
        return 0;

    // 文字列の長さが2未満の場合は、つまり空の丸括弧"()"なのでエラーとする
    if (len <= 2) {
        fprintf(stderr, "empty bracket: %s\n", exp);
        return -1;
    }

    // 最初と最後の文字を取り除く(最も外側の丸括弧を取り除く)
    for (i = 0; i < len - 2; i++) {
        exp[i] = exp[i + 1];
    }
    exp[i] = '\0';

    // 取り除いた後の文字列の最も外側に括弧が残っている場合
    // 例:"((1+2))"などの場合
    if ('(' == exp[0] && ')' == exp[i - 1])
        // 再帰的に呼び出して取り除く
        return remove_outer_most_bracket(exp);
    else
        // そうでない場合は処理を終える
        return 0;
}

// 式expから最も右側にあり、かつ優先順位が低い演算子を探して位置を返す関数
// (演算子がない場合は-1を返す)
int get_pos_operator(char *exp)
{
    int i;
    int pos_operator = -1; // 現在見つかっている演算子の位置(初期値として-1=演算子なしを設定)
    int priority_current = INT_MAX; // 現在見つかっている演算子の優先順位(初期値としてINT_MAXを設定)
    int nest = 0; // 丸括弧の深度(括弧でくくられていない部分の演算子を「最も優先順位が低い」と判断するために用いる)
    int priority;

    if (!exp)
        return pos_operator;

    // 与えられた文字列を先頭から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;
        }

        // 括弧の深度が0(丸括弧でくくられていない部分)かつ、
        // 現在見つかっている演算子よりも優先順位が同じか低い場合
        // (優先順位が同じ場合は、より右側に同じ優先順位の演算子があることになる)
        if (0 == nest && priority <= priority_current) {
          // 最も優先順位が低い演算子とみなし、その位置を保存する
          priority_current = priority;
          pos_operator = i;
        }
    }

    // 見つかった演算子の位置を返す
    return pos_operator;
}

// 与えられたノードnodeの式expを二分木へと分割する関数
// (成功した場合は0、エラーの場合は-1を返す)
int parse_expression(Node* node)
{
    int pos_operator;
    size_t len;

    if (!node)
        return -1;

    // 式expから最も外側にある丸括弧を取り除く
    if (remove_outer_most_bracket(node->exp) < 0)
        return -1;

    // 式expから演算子を探して位置を取得する
    pos_operator = get_pos_operator(node->exp);

    if (-1 == pos_operator) {
        // 式expに演算子が含まれない場合、expは項であるとみなす
        // (左右に子ノードを持たないノードとする)
        node->left  = NULL;
        node->right = NULL;
        return 0;
    }

    len = strlen(node->exp);

    if (0 == pos_operator || (len - 1) == pos_operator) {
      // 演算子の位置が式の先頭または末尾の場合は不正な式とする
        fprintf(stderr, "invalid expression: %s\n", node->exp);
        return -1;
    }

    // 以下、演算子の位置をもとに左右の部分式に分割する

    // 左側・右側のノードを作成する
    node->left   = create_node();
    node->right  = create_node();

    if (!node->left || !node->right) {
        // ノードが作成できない場合は、式が長過ぎるためエラーとする
        fprintf(stderr, "expression too long\n");
        return -1;
    }

    // 演算子の左側を左の部分式としてノードを構成する
    memset(node->left->exp, 0, MAX_EXP_LEN);
    strncpy(node->left->exp, node->exp, pos_operator);

    // 左側のノード(部分式)について、再帰的に二分木へと分割する
    if (parse_expression(node->left) < 0)
        return -1;

    // 演算子の右側を右の部分式としてノードを構成する
    memset(node->right->exp, 0, MAX_EXP_LEN);
    strncpy(node->right->exp, node->exp + pos_operator + 1, len - pos_operator);

    // 右側のノード(部分式)について、再帰的に二分木へと分割する
    if (parse_expression(node->right) < 0)
        return -1;

    // 残った演算子部分をこのノードに設定する
    node->exp[0] = node->exp[pos_operator];
    node->exp[1] = '\0';

    return 0;
}

// 後行順序訪問(帰りがけ順)で二分木を巡回して
// すべてのノードの演算子または項を表示する関数
void traverse_postorder(Node* node)
{
    // 左右に子ノードをもつ場合、表示する前にノードを再帰的に巡回する
    if (node->left)
        traverse_postorder(node->left);
    if (node->right)
        traverse_postorder(node->right);

    // 巡回を終えた後でノードの演算子または項を表示する
    // (読みやすさのために項の後に空白を補って表示する)
    printf("%s ", node->exp);
}

// 中間順序訪問(通りがけ順)で二分木を巡回して
// すべてのノードの演算子または項を表示する関数
void traverse_inorder(Node* node)
{
    // 左右に項を持つ場合、読みやすさのために項の前に開き括弧を補う
    if (node->left && node->right)
        printf("(");

    // 表示する前に左の子ノードを再帰的に巡回する
    if (node->left) {
        traverse_inorder(node->left);

        // 読みやすさのために空白を補う
        printf(" ");
    }

    // 左の子ノードの巡回を終えた後でノードの演算子または項を表示する
    printf("%s", node->exp);

    // 表示した後に右の子ノードを再帰的に巡回する
    if (node->right) {
        // 読みやすさのために空白を補う
        printf(" ");

        traverse_inorder(node->right);
    }

    // 左右に項を持つ場合、読みやすさのために項の後に閉じ括弧を補う
    if (node->left && node->right)
        printf(")");
}

// 先行順序訪問(行きがけ順)で二分木を巡回して
// すべてのノードの演算子または項を表示する関数
void traverse_preorder(Node* node)
{
    // 巡回を始める前にノードの演算子または項を表示する
    // (読みやすさのために項の後に空白を補って表示する)
    printf("%s ", node->exp);

    // 左右に子ノードをもつ場合、表示した後にノードを再帰的に巡回する
    if (node->left)
        traverse_preorder(node->left);
    if (node->right)
        traverse_preorder(node->right);
}

// 与えられたノードの演算子と左右の子ノードの値から、ノードの値を計算する関数
// ノードの値が計算できた場合は0、そうでない場合(記号を含む場合など)は-1を返す
// 計算結果はnode->expに文字列として代入する
int calculate(Node* node)
{
    double left_operand, right_operand;

    // 左右に子ノードを持たない場合、ノードは部分式ではなく項であり、
    // それ以上計算できないので0(成功)を返す
    if (!node->left && !node->right)
        return 0;

    // 左右の子ノードについて、再帰的にノードの値を計算する
    calculate(node->left);
    calculate(node->right);

    // 計算した左右の子ノードの値を数値型(double)に変換して演算子の左項・右項の値とする
    if (1 != sscanf(node->left->exp,  "%lf", &left_operand) || 
        1 != sscanf(node->right->exp, "%lf", &right_operand)) {
        // 変換できない場合(左右の子ノードが記号を含む式などの場合)は、
        // ノードの値が計算できないものとして、-1(失敗)を返す
        return -1;
    }

    // ノードの演算子に応じて左右の子ノードの値を演算し、
    // 演算した結果を文字列に変換して再度node->expに代入することで現在のノードの値とする
    switch (node->exp[0]) {
      case '+': snprintf(node->exp, MAX_EXP_LEN, "%.15lg", left_operand + right_operand); break;
      case '-': snprintf(node->exp, MAX_EXP_LEN, "%.15lg", left_operand - right_operand); break;
      case '*': snprintf(node->exp, MAX_EXP_LEN, "%.15lg", left_operand * right_operand); break;
      case '/': snprintf(node->exp, MAX_EXP_LEN, "%.15lg", left_operand / right_operand); break;
      // 上記以外の演算子の場合は計算できないものとして、-1(失敗)を返す
      default: return -1;
    }

    // 左右の子ノードの値からノードの値が求まったため、
    // このノードは左右に子ノードを持たない値のみのノードとする
    node->left  = NULL;
    node->right = NULL;

    // 計算できたため、0(成功)を返す
    return 0;
}

// 文字列から空白を取り除く関数
void remove_space(char *exp)
{
    char *dst = exp;
    char *src = exp;

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

    *dst = '\0';
}

// 式exp内の括弧の対応を検証する関数
// 開き括弧と閉じ括弧が同数でない場合はエラーとして0以外、同数の場合は0を返す
int validate_bracket_balance(char *exp)
{
    int i;
    int nest = 0; // 丸括弧の深度(くくられる括弧の数を計上するために用いる)

    // 1文字ずつ検証する
    for (i = 0; exp[i]; i++) {
        if ('(' == exp[i]) {
            // 開き丸括弧なので深度を1増やす
            nest++;
        }
        else if (')' == exp[i]) {
            // 閉じ丸括弧なので深度を1減らす
            nest--;

            // 深度が負になった場合
            if (nest < 0)
                // 式中で開かれた括弧よりも閉じ括弧が多いため、その時点でエラーとする
                // 例:"(1+2))"などの場合
                break;
        }
    }

    // 深度が0でない場合
    if (0 != nest)
        // 式中に開かれていない/閉じられていない括弧があるので、エラーとする
        // 例:"((1+2)"などの場合
        fprintf(stderr, "unbalanced bracket: %s\n", exp);

    return nest;
}

int main()
{
    // 二分木の根(root)ノードを作成する
    Node* root = create_node();

    // 標準入力から二分木に分割したい式を入力して、式全体をroot->expに格納する
    printf("input expression: ");
    scanf("%[^\n]", root->exp);

    // 入力された式から空白を除去する
    remove_space(root->exp);

    // 入力された式における括弧の対応数をチェックする
    if (0 != validate_bracket_balance(root->exp))
        return -1;

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

    // 根ノードに格納した式を二分木へと分割する
    if (parse_expression(root) < 0)
        return -1;

    // 分割した二分木を帰りがけ順で巡回して表示する(前置記法/逆ポーランド記法で表示される)
    printf("reverse polish notation: ");
    traverse_postorder(root);
    printf("\n");

    // 分割した二分木を通りがけ順で巡回して表示する(中置記法で表示される)
    printf("infix notation: ");
    traverse_inorder(root);
    printf("\n");

    // 分割した二分木を行きがけ順で巡回して表示する(後置記法/ポーランド記法で表示される)
    printf("polish notation: ");
    traverse_preorder(root);
    printf("\n");

    // 分割した二分木から式全体の値を計算する
    if (calculate(root) < 0) {
        // (式の一部あるいは全部が)計算できなかった場合は、計算結果の式を中置記法で表示する
        printf("calculated expression: ");
        traverse_inorder(root);
        printf("\n");
    }
    else {
        // 計算できた場合はその値を表示する
        printf("calculated result: %s\n", root->exp);
    }

    return 0;
}
Copyright© 2017 . Released under the MIT License.
プログラムのコンパイルと実行(GCCを用いた場合の例)
$ gcc polish.c -o polish
$ ./polish
実行例1
input expression: x = 1 - 2 + 3
expression: x=1-2+3
reverse polish notation: x 1 2 - 3 + = 
infix notation: (x = ((1 - 2) + 3))
polish notation: = x + - 1 2 3 
calculated expression: (x = 2)
実行例2
input expression: 2 + 5 * 3 - 4
expression: 2+5*3-4
reverse polish notation: 2 5 3 * + 4 - 
infix notation: ((2 + (5 * 3)) - 4)
polish notation: - + 2 * 5 3 4 
calculated result: 13
実行例3
input expression: 1.0+2/.3/(0-1)
expression: 1.0+2/.3/(0-1)
reverse polish notation: 1.0 2 .3 / 0 1 - / + 
infix notation: (1.0 + ((2 / .3) / (0 - 1)))
polish notation: + 1.0 / / 2 .3 - 0 1 
calculated result: -5.66666666666667
実行例4
input expression: 1 + 2 + X = Y + 3 + 4
expression: 1+2+X=Y+3+4
reverse polish notation: 1 2 + X + Y 3 + 4 + = 
infix notation: (((1 + 2) + X) = ((Y + 3) + 4))
polish notation: = + + 1 2 X + + Y 3 4 
calculated expression: ((3 + X) = ((Y + 3) + 4))

§4 他の言語での実装

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

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

§5 文書情報

2018-01-21
本文について
演算子の優先順位について「最も右側の」の記載が抜けていた点を修正し、補足説明を追記
図表について、§.Cでの実装と差異があった箇所を修正
例示用の数式を同一のものに統一
各記法での表記において項の間に空白を入れるように変更
その他図表についてよりわかりやすいものとなるよう追加・変更
§.ポーランド記法化・逆ポーランド記法化と数式計算のデモにて各記法への変換過程・数式の計算過程を確認できるようにした
各言語での実装について
各記法での表記において項の間に空白を入れて出力するように変更
その他掲示板での指摘に基づいて改善・修正(http://smdn.jp/misc/forum/programming/#entry48, http://smdn.jp/misc/forum/programming/#entry50)
2017-12-22
各言語での実装について
処理内容を記述したコメントを追記
ソースコードのライセンスをMIT Licenseに設定
定数以外(XやAなどの記号)を含む部分式の場合でも、計算できる部分は計算するように変更(式X=1+21+2=3*4+Aなど)
開き丸括弧(および閉じ丸括弧)が正しく開いて/閉じていない場合にエラーとなるように修正(式(2+31+(2+3))など)
Pythonでの実装およびJavaScriptでの実装を追加
Rubyでの実装を更新停止
本文について
一部解説に加筆
用語の不統一を修正
2017-12-09
Cでの実装について、strncpyの前にmemsetすることで文字列を終端させるように修正
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
初版公開