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

逆ポーランド記法とは

一般に人が読むことを前提にした数式は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)あるいは前置記法と言います。

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

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

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

このデモでできる変換処理と制限事項についてはCでの実装の項をご覧ください。 また、ソースコードはGitHubリポジトリにてご覧いただけます。

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

          
記入例
  • 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に対応したブラウザでご覧ください。
二分木化した数式と記法の変換過程
逆ポーランド記法・後置記法
placeholder
SVG-SMIL animationに対応したブラウザでご覧ください。
二分木化した数式と記法の変換過程
中置記法
placeholder
SVG-SMIL animationに対応したブラウザでご覧ください。
二分木化した数式と数式の計算過程
placeholder
SVG-SMIL animationに対応したブラウザでご覧ください。

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

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

二分木とは

二分木(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型であるとしていますが、扱うデータに応じて型を選択します。

数式を二分木に変換する

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

変換手順の定義

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

ルール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での実装で掲載しているプログラムでは、こういった定義に従い括弧を含む式を扱うようにしています。

変換手順の適用

ここまでで定めてきたルールに従って、式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全体が二分木へと変換されました。

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

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

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

まず、二分木からデータを読み出す方法には次の三種類があります。 ノードを巡回(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の順でデータが読み出されることになります。

式の二分木への適用

では、これを式から変換した二分木にあてはめた場合を考えてみます。 ここでは式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 + 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 -

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

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以外の言語での実装も用意しています。

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

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

データ構造

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

Node型
#define MAX_NODES 80 // このプログラムで確保するノードの最大個数
#define MAX_EXP_LEN 0x100 // 各ノードで保持する式の文字列の最大文字数

// ノードを構成するデータ構造
typedef struct Node Node;

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 *const create_node()
{
    if (nb_node_used == MAX_NODES)
        return NULL;
    else
        return &nodes[nb_node_used++];
}

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

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

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

main関数

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

前処理のための関数の宣言
// 標準入力から1行分読み込む関数
// 最大(len_max-1)文字までを標準入力から読み込み、末尾の改行文字を取り除いた上でexpに格納する
bool read_line(char *const exp, size_t len_max);

// 文字列から空白を取り除く関数
// 空白を取り除いた後の文字列の長さを戻り値として返す
size_t remove_space(char *const exp);

// 式exp内の括弧の対応を検証する関数
// 開き括弧と閉じ括弧が同数でない場合はエラーとする
bool validate_bracket_balance(const char *const exp);
main関数と前処理のための関数
bool read_line(char *const exp, size_t len_max)
{
    // 標準入力から最大(len_max - 1)文字を読み込む
    if (!fgets(exp, len_max, stdin))
        return false;

    // 読み込んだ内容が改行文字で終わる場合は、削除する
    char *lf = strchr(exp, '\n');

    if (lf)
        *lf = '\0';

    return true;
}

size_t remove_space(char *const exp)
{
    char *dst = exp;
    char *src = exp;
    size_t len = 0;

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

        *(dst++) = *(src++);
        len++;
    }

    *dst = '\0';

    return len;
}

bool validate_bracket_balance(const char *const exp)
{
    int nest_depth = 0; // 丸括弧の深度(くくられる括弧の数を計上するために用いる)

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

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

    // 深度が0でない場合
    if (0 != nest_depth) {
        // 式中に開かれていない/閉じられていない括弧があるので、不正な式と判断する
        // 例:"((1+2)"などの場合
        fprintf(stderr, "unbalanced bracket: %s\n", exp);
        return false;
    }
    else {
        return true;
    }
}

// main関数。 結果によって次の値を返す。
//   0: 正常終了 (二分木への分割、および式全体の値の計算に成功した場合)
//   1: 入力のエラーによる終了 (二分木への分割に失敗した場合)
//   2: 計算のエラーによる終了 (式全体の値の計算に失敗した場合)
int main()
{
    // 二分木の根(root)ノードを作成する
    Node *root = create_node();

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

    if (!read_line(root->exp, MAX_EXP_LEN))
        // 入力が得られなかった場合は、処理を終了する
        return 1;

    // 入力された式から空白を除去する
    if (0 == remove_space(root->exp))
        // 空白を除去した結果、空の文字列となった場合は、処理を終了する
        return 1;

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

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

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

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

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

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

    // 分割した二分木から式全体の値を計算する
    double result_value;

    if (calculate_expression_tree(root, &result_value)) {
        // 計算できた場合はその値を表示する
        printf("calculated result: %.17g\n", result_value);
        return 0;
    }
    else {
        // (式の一部あるいは全部が)計算できなかった場合は、計算結果の式を中置記法で表示する
        printf("calculated expression: ");
        print_inorder(root);
        return 2;
    }
}

main関数の流れは、

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

となります。

二分木への分割

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

二分木への分割を行う関数群の宣言
/*
 * ### 二分木への分割を行う関数の宣言 ###
 */

// 与えられたノードnodeの式expを二分木へと分割する関数
// (成功した場合はtrue、エラーの場合はfalseを返す)
bool parse_expression(Node *const node);

// 式expから最も外側にある丸括弧を取り除く関数
// (成功した場合はtrue、エラーの場合はfalseを返す)
bool remove_outermost_bracket(char *const exp);

// 式expから最も右側にあり、かつ優先順位が低い演算子を探して位置を返す関数
// (演算子がない場合は-1を返す)
int get_pos_operator(const char *const exp);
parse_expressionの実装
bool parse_expression(Node *const node)
{
    if (!node)
        return false;

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

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

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

    size_t len = strlen(node->exp);

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

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

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

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

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

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

    // 演算子の右側を右の部分式としてノードを構成する
    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))
        return false;

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

    return true;
}
remove_outermost_bracketの実装
bool remove_outermost_bracket(char *const exp)
{
    bool has_outermost_bracket = false; // 最も外側に括弧を持つかどうか
    int nest_depth = 0; // 丸括弧の深度(式中で開かれた括弧が閉じられたかどうか調べるために用いる)

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

    // 1文字目以降を1文字ずつ検証
    unsigned int i;
    size_t len;

    for (i = 1, len = 1; exp[i]; i++, len++) {
        if ('(' == exp[i]) {
            // 開き丸括弧なので深度を1増やす
            nest_depth++;
        }
        else if (')' == exp[i]) {
            // 閉じ丸括弧なので深度を1減らす
            nest_depth--;

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

    // 最も外側に丸括弧がない場合は、何もしない
    if (!has_outermost_bracket)
        return true;

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

    // 最初と最後の文字を取り除く(最も外側の丸括弧を取り除く)
    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_outermost_bracket(exp);
    else
        // そうでない場合は処理を終える
        return true;
}
get_pos_operatorの実装
int get_pos_operator(const char *const exp)
{
    int pos_operator = -1; // 現在見つかっている演算子の位置(初期値として-1=演算子なしを設定)
    int priority_current = INT_MAX; // 現在見つかっている演算子の優先順位(初期値としてINT_MAXを設定)
    int nest_depth = 0; // 丸括弧の深度(括弧でくくられていない部分の演算子を「最も優先順位が低い」と判断するために用いる)

    // 与えられた文字列を先頭から1文字ずつ検証する
    for (unsigned int i = 0; exp[i]; i++) {
        int priority;

        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_depth++; continue;
            case ')': nest_depth--; continue;
            // それ以外の文字の場合は何もしない
            default: continue;
        }

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

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

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

  1. まず、remove_outermost_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は、分割された部分式に演算子が含まれる限り、再帰的に呼び出され、式の分割を繰り返します。

二分木の巡回と各記法での表示

続いて、二分木の巡回を行う関数について見ていきます。 二分木の巡回のために、以下のような関数traverseを用意します。

二分木の巡回を行う関数とコールバック関数型の宣言
/*
 * ### 二分木の巡回を行う関数の宣言 ###
 */

// 巡回する際の動作を定義したコールバック関数への関数ポインタ型
typedef void (*traversal_callback_func_t)(Node *const node);

// 二分木を巡回し、ノードの行きがけ・通りがけ・帰りがけに指定された関数をコールバックする関数
void traverse(
    Node *const node,
    const traversal_callback_func_t on_visit,   // ノードの行きがけにコールバックする関数
    const traversal_callback_func_t on_transit, // ノードの通りがけにコールバックする関数
    const traversal_callback_func_t on_leave    // ノードの帰りがけにコールバックする関数
);
traverseの実装
void traverse(
    Node *const node,
    const traversal_callback_func_t on_visit,
    const traversal_callback_func_t on_transit,
    const traversal_callback_func_t on_leave
)
{
    // このノードの行きがけに行う動作をコールバックする
    if (on_visit)
        on_visit(node);

    // 左に子ノードをもつ場合は、再帰的に巡回する
    if (node->left)
        traverse(node->left, on_visit, on_transit, on_leave);

    // このノードの通りがけに行う動作をコールバックする
    if (on_transit)
        on_transit(node);

    // 右に子ノードをもつ場合は、再帰的に巡回する
    if (node->right)
        traverse(node->right, on_visit, on_transit, on_leave);

    // このノードの帰りがけに行う動作をコールバックする
    if (on_leave)
        on_leave(node);
}

この関数は、§.二分木からデータを読み出す順序で解説した疑似コードを実装したもので、与えられたノードを起点に巡回を行います。

巡回に際して、指定された関数をコールバック呼び出しすることにより、ノードの行きがけ・通りがけ・帰りがけの各時点での処理を行います。 左もしくは右に子ノードを持つ場合は、その子ノードに対して再帰的にtraverseを呼び出します。

これにより、二分木全体を再帰的に巡回し、各ノードへの行きがけ・通りがけ・帰りがけに指定された処理を行います。


続いて、この関数を用いて各記法での表示を行うための次の3つの関数を見ていきます。

print_postorder
二分木を帰りがけ順で巡回して表示する=逆ポーランド記法(後置記法)で表示する関数
print_inorder
二分木を通りがけ順で巡回して表示する=中置記法で表示する関数
print_preorder
二分木を行きがけ順で巡回して表示する=ポーランド記法(前置記法)で表示する関数

各関数とも、引数として与えられる二分木の根となるノードnodeに対して先の関数traverseを呼び出します。 また、呼び出しに際してノードの持つ値(node->exp)の表示を行うコールバック関数を指定します。

ここで、値を表示する関数のコールバックを、それぞれ帰りがけ・通りがけ・行きがけに行うよう指定します。 これにより、§.式の二分木への適用で解説したとおり、各記法に変換した数式が表示されることになります。

なお、値を表示する各コールバック関数では、結果の読みやすさのために各ノードの値の間に空白を補って表示します。 またprint_inorderでは丸括弧も補って表示します。

二分木を帰りがけ順で巡回して表示する関数の宣言
// 後行順序訪問(帰りがけ順)で二分木を巡回して
// すべてのノードの演算子または項を表示する関数
void print_postorder(Node *const node);

// 帰りがけ順で巡回する際に、帰りがけにコールバックさせる関数
void print_postorder_on_leave(Node *const node);
print_postorderと表示を行うコールバック関数の実装
void print_postorder(Node *const node)
{
    // 巡回を開始する
    traverse(
        node,
        NULL, // ノードへの行きがけ時には何もしない
        NULL, // ノードへの通りがけ時には何もしない
        print_postorder_on_leave // ノードへの帰りがけに、ノードの演算子または項を表示する
    );

    // 巡回が終了したら改行を表示する
    printf("\n");
}

void print_postorder_on_leave(Node *const node)
{
    // 巡回を終えた後でノードの演算子または項を表示する
    // (読みやすさのために項の後に空白を補って表示する)
    printf("%s ", node->exp);
}
二分木を通りがけ順で巡回して表示する関数の宣言
// 中間順序訪問(通りがけ順)で二分木を巡回して
// すべてのノードの演算子または項を表示する関数
void print_inorder(Node *const node);

// 通りがけ順で巡回する際に、行きがけにコールバックさせる関数
void print_inorder_on_visit(Node *const node);

// 通りがけ順で巡回する際に、通りがけにコールバックさせる関数
void print_inorder_on_transit(Node *const node);

// 通りがけ順で巡回する際に、帰りがけにコールバックさせる関数
void print_inorder_on_leave(Node *const node);
print_inorderと表示を行うコールバック関数の実装
void print_inorder(Node *const node)
{
    // 巡回を開始する
    traverse(
        node,
        print_inorder_on_visit,     // ノードへの行きがけに、必要なら開き括弧を補う
        print_inorder_on_transit,   // ノードへの通りがけに、ノードの演算子または項を表示する
        print_inorder_on_leave      // ノードへの帰りがけに、必要なら閉じ括弧を補う
    );

    // 巡回が終了したら改行を表示する
    printf("\n");
}

void print_inorder_on_visit(Node *const node)
{
    // 左右に項を持つ場合、読みやすさのために項の前(行きがけ)に開き括弧を補う
    if (node->left && node->right)
        printf("(");
}

void print_inorder_on_transit(Node *const node)
{
    if (node->left)
        // 左に子ノードを持つ場合は、読みやすさのために空白を補う
        printf(" ");

    // 左の子ノードから右の子ノードへ巡回する際に、ノードの演算子または項を表示する
    printf("%s", node->exp);

    if (node->right)
        // 右に子ノードを持つ場合は、読みやすさのために空白を補う
        printf(" ");
}

void print_inorder_on_leave(Node *const node)
{
    // 左右に項を持つ場合、読みやすさのために項の後(帰りがけ)に閉じ括弧を補う
    if (node->left && node->right)
        printf(")");
}
二分木を行きがけ順で巡回して表示する関数の宣言
// 先行順序訪問(行きがけ順)で二分木を巡回して
// すべてのノードの演算子または項を表示する関数
void print_preorder(Node *const node);

// 行きがけ順で巡回する際に、行きがけにコールバックさせる関数
void print_preorder_on_visit(Node *const node);
print_preorderと表示を行うコールバック関数の実装
void print_preorder(Node *const node)
{
    // 巡回を開始する
    traverse(
        node,
        print_preorder_on_visit, // ノードへの行きがけに、ノードの演算子または項を表示する
        NULL, // ノードへの行きがけ時には何もしない
        NULL  // ノードへの帰りがけ時には何もしない
    );

    // 巡回が終了したら改行を表示する
    printf("\n");
}

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

二分木からの値の演算

続いて、二分木から値の演算について見ていきます。 §.二分木化した数式を使って計算を行うで解説したとおり、個々のノードの値を再帰的に演算していくことにより、二分木全体の演算を行います。

具体的には、次の関数でこの処理を行います。 まず、calculate_expression_treeでは先の二分木の巡回と同様にtraverseを用いて各ノードを巡回します。 ここで、帰りがけに個々のノードの値を演算する関数calculate_nodeをコールバックさせることにより、二分木全体の演算を行います。 最後に、parse_numberを用いて演算された数式を文字列からdoubleに変換し、計算結果として代入します。

二分木から値の演算を行う関数群の宣言
/*
 * ### 二分木から値の演算を行う関数の宣言 ###
 */

// 後行順序訪問(帰りがけ順)で二分木を巡回して、二分木全体の値を計算する関数
// すべてのノードの値が計算できた場合はtrue、そうでない場合(記号を含む場合など)はfalseを返す
// 計算結果はresult_valueに代入する
bool calculate_expression_tree(Node *const node, double *const result_value);

// 与えられたノードの演算子と左右の子ノードの値から、ノードの値を計算する関数
// 計算できた場合、計算結果の値はnode->expに文字列として代入し、左右のノードは削除する
void calculate_node(Node *const node);

// 与えられた文字列を数値化する関数
// 正常に変換できた場合はnumberに変換した数値を代入し、trueを返す
// 変換できなかった場合はfalseを返す
bool parse_number(const char *const expression, double *const number);
calculate_expression_treeの実装
bool calculate_expression_tree(Node *const node, double *const result_value)
{
    // 巡回を開始する
    // ノードへの帰りがけに、ノードが表す部分式から、その値を計算する
    // 帰りがけに計算することによって、末端の部分木から順次計算し、再帰的に木全体の値を計算する
    traverse(
        node,
        NULL, // ノードへの行きがけには何もしない
        NULL, // ノードへの通りがけには何もしない
        calculate_node // ノードへの帰りがけに、ノードの値を計算する
    );

    // ノードの値を数値に変換し、計算結果として代入する
    return parse_number(node->exp, result_value);
}

個々のノードの値を演算する関数calculate_nodeについて詳しく見ていきます。

calculate_nodeの実装
void calculate_node(Node *const node)
{
    // 左右に子ノードを持たない場合、ノードは部分式ではなく項であり、
    // それ以上計算できないので処理を終える
    if (!node->left || !node->right)
        return;

    // 計算した左右の子ノードの値を数値型(double)に変換して演算子の左項・右項の値とする
    // 変換できない場合(左右の子ノードが記号を含む式などの場合)は、
    // ノードの値が計算できないものとして、処理を終える
    double left_operand, right_operand;

    // 左ノードの値を数値に変換して演算子の左項left_operandの値とする
    if (!parse_number(node->left->exp, &left_operand))
        // doubleで扱える範囲外の値か、途中に変換できない文字があるため、計算できないものとして扱い、処理を終える
        return;

    // 右ノードの値を数値に変換して演算子の右項right_operandの値とする
    if (!parse_number(node->right->exp, &right_operand))
        // doubleで扱える範囲外の値か、途中に変換できない文字があるため、計算できないものとして扱い、処理を終える
        return;

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

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

calculate_node関数では、引数で与えられたノードに対して以下のような処理を行います。

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

traverse関数によってcalculate_node関数が再帰的に呼び出されることにより、末端の部分木から順次値が定まっていきます。 すべての部分木の値が定まることで、最終的に二分木全体の値、つまり式の演算結果が求まります。

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

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


最後に、文字列からdoubleに変換する関数parse_numberは次のようになります。 基本的には標準ライブラリ関数strtodを使用して変換し、エラー処理を行っているだけなので、詳細については省略します。

parse_numberの宣言
// 与えられた文字列を数値化する関数
// 正常に変換できた場合はnumberに変換した数値を代入し、trueを返す
// 変換できなかった場合はfalseを返す
bool parse_number(const char *const expression, double *const number);
parse_numberの実装
bool parse_number(const char *const expression, double *const number)
{
    // 入力および出力先がNULLの場合は変換できないものとして扱う
    if (!expression)
        return false;
    if (!number)
        return false;

    char *endptr_value; // strtodで変換できない文字の位置を検出するためのポインタ

    // 与えられた文字列を数値に変換する
    errno = 0;
    *number = strtod(expression, &endptr_value);

    if (ERANGE == errno)
        return false; // doubleで扱える範囲外のため、正常に変換できなかった

    if (endptr_value != (expression + strlen(expression)))
        return false; // 途中に変換できない文字があるため、正常に変換できなかった

    return true;
}

プログラム全文

最後に、プログラム全文とコンパイル・実行例です。 プログラム全文およびコンパイル方法・実行例はGitHubリポジトリでも参照できます。

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

polish.c
// SPDX-FileCopyrightText: 2022 smdn <smdn@smdn.jp>
// SPDX-License-Identifier: MIT
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <errno.h>
#include <string.h>
#include <limits.h>

#define MAX_NODES 80 // このプログラムで確保するノードの最大個数
#define MAX_EXP_LEN 0x100 // 各ノードで保持する式の文字列の最大文字数

// ノードを構成するデータ構造
typedef struct Node Node;

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 *const create_node()
{
    if (nb_node_used == MAX_NODES)
        return NULL;
    else
        return &nodes[nb_node_used++];
}

/*
 * ### 二分木への分割を行う関数の宣言 ###
 */

// 与えられたノードnodeの式expを二分木へと分割する関数
// (成功した場合はtrue、エラーの場合はfalseを返す)
bool parse_expression(Node *const node);

// 式expから最も外側にある丸括弧を取り除く関数
// (成功した場合はtrue、エラーの場合はfalseを返す)
bool remove_outermost_bracket(char *const exp);

// 式expから最も右側にあり、かつ優先順位が低い演算子を探して位置を返す関数
// (演算子がない場合は-1を返す)
int get_pos_operator(const char *const exp);

/*
 * ### 二分木の巡回を行う関数の宣言 ###
 */

// 巡回する際の動作を定義したコールバック関数への関数ポインタ型
typedef void (*traversal_callback_func_t)(Node *const node);

// 二分木を巡回し、ノードの行きがけ・通りがけ・帰りがけに指定された関数をコールバックする関数
void traverse(
    Node *const node,
    const traversal_callback_func_t on_visit,   // ノードの行きがけにコールバックする関数
    const traversal_callback_func_t on_transit, // ノードの通りがけにコールバックする関数
    const traversal_callback_func_t on_leave    // ノードの帰りがけにコールバックする関数
);

// 後行順序訪問(帰りがけ順)で二分木を巡回して
// すべてのノードの演算子または項を表示する関数
void print_postorder(Node *const node);

// 帰りがけ順で巡回する際に、帰りがけにコールバックさせる関数
void print_postorder_on_leave(Node *const node);

// 中間順序訪問(通りがけ順)で二分木を巡回して
// すべてのノードの演算子または項を表示する関数
void print_inorder(Node *const node);

// 通りがけ順で巡回する際に、行きがけにコールバックさせる関数
void print_inorder_on_visit(Node *const node);

// 通りがけ順で巡回する際に、通りがけにコールバックさせる関数
void print_inorder_on_transit(Node *const node);

// 通りがけ順で巡回する際に、帰りがけにコールバックさせる関数
void print_inorder_on_leave(Node *const node);

// 先行順序訪問(行きがけ順)で二分木を巡回して
// すべてのノードの演算子または項を表示する関数
void print_preorder(Node *const node);

// 行きがけ順で巡回する際に、行きがけにコールバックさせる関数
void print_preorder_on_visit(Node *const node);

/*
 * ### 二分木から値の演算を行う関数の宣言 ###
 */

// 後行順序訪問(帰りがけ順)で二分木を巡回して、二分木全体の値を計算する関数
// すべてのノードの値が計算できた場合はtrue、そうでない場合(記号を含む場合など)はfalseを返す
// 計算結果はresult_valueに代入する
bool calculate_expression_tree(Node *const node, double *const result_value);

// 与えられたノードの演算子と左右の子ノードの値から、ノードの値を計算する関数
// 計算できた場合、計算結果の値はnode->expに文字列として代入し、左右のノードは削除する
void calculate_node(Node *const node);

// 与えられた文字列を数値化する関数
// 正常に変換できた場合はnumberに変換した数値を代入し、trueを返す
// 変換できなかった場合はfalseを返す
bool parse_number(const char *const expression, double *const number);

/*
 * ### その他の前処理を行う関数の宣言 ###
 */

// 標準入力から1行分読み込む関数
// 最大(len_max-1)文字までを標準入力から読み込み、末尾の改行文字を取り除いた上でexpに格納する
bool read_line(char *const exp, size_t len_max);

// 文字列から空白を取り除く関数
// 空白を取り除いた後の文字列の長さを戻り値として返す
size_t remove_space(char *const exp);

// 式exp内の括弧の対応を検証する関数
// 開き括弧と閉じ括弧が同数でない場合はエラーとする
bool validate_bracket_balance(const char *const exp);

/*
 * ### 各関数の実装 ###
 */

bool parse_expression(Node *const node)
{
    if (!node)
        return false;

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

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

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

    size_t len = strlen(node->exp);

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

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

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

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

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

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

    // 演算子の右側を右の部分式としてノードを構成する
    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))
        return false;

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

    return true;
}

bool remove_outermost_bracket(char *const exp)
{
    bool has_outermost_bracket = false; // 最も外側に括弧を持つかどうか
    int nest_depth = 0; // 丸括弧の深度(式中で開かれた括弧が閉じられたかどうか調べるために用いる)

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

    // 1文字目以降を1文字ずつ検証
    unsigned int i;
    size_t len;

    for (i = 1, len = 1; exp[i]; i++, len++) {
        if ('(' == exp[i]) {
            // 開き丸括弧なので深度を1増やす
            nest_depth++;
        }
        else if (')' == exp[i]) {
            // 閉じ丸括弧なので深度を1減らす
            nest_depth--;

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

    // 最も外側に丸括弧がない場合は、何もしない
    if (!has_outermost_bracket)
        return true;

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

    // 最初と最後の文字を取り除く(最も外側の丸括弧を取り除く)
    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_outermost_bracket(exp);
    else
        // そうでない場合は処理を終える
        return true;
}

int get_pos_operator(const char *const exp)
{
    int pos_operator = -1; // 現在見つかっている演算子の位置(初期値として-1=演算子なしを設定)
    int priority_current = INT_MAX; // 現在見つかっている演算子の優先順位(初期値としてINT_MAXを設定)
    int nest_depth = 0; // 丸括弧の深度(括弧でくくられていない部分の演算子を「最も優先順位が低い」と判断するために用いる)

    // 与えられた文字列を先頭から1文字ずつ検証する
    for (unsigned int i = 0; exp[i]; i++) {
        int priority;

        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_depth++; continue;
            case ')': nest_depth--; continue;
            // それ以外の文字の場合は何もしない
            default: continue;
        }

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

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

void traverse(
    Node *const node,
    const traversal_callback_func_t on_visit,
    const traversal_callback_func_t on_transit,
    const traversal_callback_func_t on_leave
)
{
    // このノードの行きがけに行う動作をコールバックする
    if (on_visit)
        on_visit(node);

    // 左に子ノードをもつ場合は、再帰的に巡回する
    if (node->left)
        traverse(node->left, on_visit, on_transit, on_leave);

    // このノードの通りがけに行う動作をコールバックする
    if (on_transit)
        on_transit(node);

    // 右に子ノードをもつ場合は、再帰的に巡回する
    if (node->right)
        traverse(node->right, on_visit, on_transit, on_leave);

    // このノードの帰りがけに行う動作をコールバックする
    if (on_leave)
        on_leave(node);
}

void print_postorder(Node *const node)
{
    // 巡回を開始する
    traverse(
        node,
        NULL, // ノードへの行きがけ時には何もしない
        NULL, // ノードへの通りがけ時には何もしない
        print_postorder_on_leave // ノードへの帰りがけに、ノードの演算子または項を表示する
    );

    // 巡回が終了したら改行を表示する
    printf("\n");
}

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

void print_inorder(Node *const node)
{
    // 巡回を開始する
    traverse(
        node,
        print_inorder_on_visit,     // ノードへの行きがけに、必要なら開き括弧を補う
        print_inorder_on_transit,   // ノードへの通りがけに、ノードの演算子または項を表示する
        print_inorder_on_leave      // ノードへの帰りがけに、必要なら閉じ括弧を補う
    );

    // 巡回が終了したら改行を表示する
    printf("\n");
}

void print_inorder_on_visit(Node *const node)
{
    // 左右に項を持つ場合、読みやすさのために項の前(行きがけ)に開き括弧を補う
    if (node->left && node->right)
        printf("(");
}

void print_inorder_on_transit(Node *const node)
{
    if (node->left)
        // 左に子ノードを持つ場合は、読みやすさのために空白を補う
        printf(" ");

    // 左の子ノードから右の子ノードへ巡回する際に、ノードの演算子または項を表示する
    printf("%s", node->exp);

    if (node->right)
        // 右に子ノードを持つ場合は、読みやすさのために空白を補う
        printf(" ");
}

void print_inorder_on_leave(Node *const node)
{
    // 左右に項を持つ場合、読みやすさのために項の後(帰りがけ)に閉じ括弧を補う
    if (node->left && node->right)
        printf(")");
}

void print_preorder(Node *const node)
{
    // 巡回を開始する
    traverse(
        node,
        print_preorder_on_visit, // ノードへの行きがけに、ノードの演算子または項を表示する
        NULL, // ノードへの行きがけ時には何もしない
        NULL  // ノードへの帰りがけ時には何もしない
    );

    // 巡回が終了したら改行を表示する
    printf("\n");
}

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

bool calculate_expression_tree(Node *const node, double *const result_value)
{
    // 巡回を開始する
    // ノードへの帰りがけに、ノードが表す部分式から、その値を計算する
    // 帰りがけに計算することによって、末端の部分木から順次計算し、再帰的に木全体の値を計算する
    traverse(
        node,
        NULL, // ノードへの行きがけには何もしない
        NULL, // ノードへの通りがけには何もしない
        calculate_node // ノードへの帰りがけに、ノードの値を計算する
    );

    // ノードの値を数値に変換し、計算結果として代入する
    return parse_number(node->exp, result_value);
}

void calculate_node(Node *const node)
{
    // 左右に子ノードを持たない場合、ノードは部分式ではなく項であり、
    // それ以上計算できないので処理を終える
    if (!node->left || !node->right)
        return;

    // 計算した左右の子ノードの値を数値型(double)に変換して演算子の左項・右項の値とする
    // 変換できない場合(左右の子ノードが記号を含む式などの場合)は、
    // ノードの値が計算できないものとして、処理を終える
    double left_operand, right_operand;

    // 左ノードの値を数値に変換して演算子の左項left_operandの値とする
    if (!parse_number(node->left->exp, &left_operand))
        // doubleで扱える範囲外の値か、途中に変換できない文字があるため、計算できないものとして扱い、処理を終える
        return;

    // 右ノードの値を数値に変換して演算子の右項right_operandの値とする
    if (!parse_number(node->right->exp, &right_operand))
        // doubleで扱える範囲外の値か、途中に変換できない文字があるため、計算できないものとして扱い、処理を終える
        return;

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

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

bool parse_number(const char *const expression, double *const number)
{
    // 入力および出力先がNULLの場合は変換できないものとして扱う
    if (!expression)
        return false;
    if (!number)
        return false;

    char *endptr_value; // strtodで変換できない文字の位置を検出するためのポインタ

    // 与えられた文字列を数値に変換する
    errno = 0;
    *number = strtod(expression, &endptr_value);

    if (ERANGE == errno)
        return false; // doubleで扱える範囲外のため、正常に変換できなかった

    if (endptr_value != (expression + strlen(expression)))
        return false; // 途中に変換できない文字があるため、正常に変換できなかった

    return true;
}

bool read_line(char *const exp, size_t len_max)
{
    // 標準入力から最大(len_max - 1)文字を読み込む
    if (!fgets(exp, len_max, stdin))
        return false;

    // 読み込んだ内容が改行文字で終わる場合は、削除する
    char *lf = strchr(exp, '\n');

    if (lf)
        *lf = '\0';

    return true;
}

size_t remove_space(char *const exp)
{
    char *dst = exp;
    char *src = exp;
    size_t len = 0;

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

        *(dst++) = *(src++);
        len++;
    }

    *dst = '\0';

    return len;
}

bool validate_bracket_balance(const char *const exp)
{
    int nest_depth = 0; // 丸括弧の深度(くくられる括弧の数を計上するために用いる)

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

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

    // 深度が0でない場合
    if (0 != nest_depth) {
        // 式中に開かれていない/閉じられていない括弧があるので、不正な式と判断する
        // 例:"((1+2)"などの場合
        fprintf(stderr, "unbalanced bracket: %s\n", exp);
        return false;
    }
    else {
        return true;
    }
}

// main関数。 結果によって次の値を返す。
//   0: 正常終了 (二分木への分割、および式全体の値の計算に成功した場合)
//   1: 入力のエラーによる終了 (二分木への分割に失敗した場合)
//   2: 計算のエラーによる終了 (式全体の値の計算に失敗した場合)
int main()
{
    // 二分木の根(root)ノードを作成する
    Node *root = create_node();

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

    if (!read_line(root->exp, MAX_EXP_LEN))
        // 入力が得られなかった場合は、処理を終了する
        return 1;

    // 入力された式から空白を除去する
    if (0 == remove_space(root->exp))
        // 空白を除去した結果、空の文字列となった場合は、処理を終了する
        return 1;

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

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

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

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

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

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

    // 分割した二分木から式全体の値を計算する
    double result_value;

    if (calculate_expression_tree(root, &result_value)) {
        // 計算できた場合はその値を表示する
        printf("calculated result: %.17g\n", result_value);
        return 0;
    }
    else {
        // (式の一部あるいは全部が)計算できなかった場合は、計算結果の式を中置記法で表示する
        printf("calculated expression: ");
        print_inorder(root);
        return 2;
    }
}
プログラムのコンパイルと実行(GCCを用いた場合の例)
$gcc polish.c -o polish
$./polish

GCC以外でのコンパイル・実行方法はhttps://github.com/smdn/polish-notation-impls/tree/main/src/impls/cを参照してください。

実行例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.666666666666667
実行例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))

他の言語での実装

GitHubリポジトリにて、他の言語で実装したものを掲載しています。 比較して読めるように、いずれもCでの実装に近い記述にしてあります。

なお、最初に挙げたデモはJavaScriptで実装しています。 ソースコードについては、上記リポジトリのほか、このページのソースからも閲覧できます。

不具合・質問等

各言語での実装、あるいは冒頭のデモに不具合がある場合は、Issuesまでご報告をお願いします。 質問等についてもIssuesにて受け付けています。

コードの修正案・改善案についてはPull requestsを受け付けていますが、その際はまずCONTRIBUTING.mdをお読みください。

文書情報

2022-09-09
C++での実装を追加
各言語での実装について
二分木の走査処理とノード走査時の処理をコールバックによって分離し、各記法での表示と演算処理を共通化
入力された式が空白のみの場合、入力エラーとして処理を中断するように変更
終了コードを以下のように定義
0:正常終了 (二分木への分割、および式全体の値の計算に成功した場合)
1:入力のエラーによる終了 (二分木への分割に失敗した場合)
2:計算のエラーによる終了 (式全体の値の計算に失敗した場合)
浮動小数点型からの文字列化に際して、%.17g(およびその相当書式)を使用するように変更
各言語のより新しい標準にあわせてコードを改善
コメントの齟齬・誤りを修正
ほか軽微な修正と改善
Cでの実装について
sscanfの代わりにstrtodを使用した実装に改善
JavaScriptでのデモについて
ES modulesおよびES2022を用いた実装に改善
「変換」ボタンを押すとページ遷移が発生する不具合を修正
本文について
上記修正に合わせてコードの解説文を修正
2022-08-07
Cを含む各種言語での実装をGitHubリポジトリに移動
2018-01-21
本文について
演算子の優先順位について「最も右側の」の記載が抜けていた点を修正し、補足説明を追記
図表について、§.Cでの実装と差異があった箇所を修正
例示用の数式を同一のものに統一
各記法での表記において項の間に空白を入れるように変更
その他図表についてよりわかりやすいものとなるよう追加・変更
§.ポーランド記法化・逆ポーランド記法化と数式計算のデモにて各記法への変換過程・数式の計算過程を確認できるようにした
各言語での実装について
各記法での表記において項の間に空白を入れて出力するように変更
その他掲示板での指摘に基づいて改善・修正(プログラミング #entry48, プログラミング #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
初版公開