プログラミング関連の話題・質問用のスレッド。 Atom 1.0

※ブラウザによっては新しい書き込みが表示されない場合があるようなので、返信が表示されていない場合はF5または更新ボタンでページを更新してください。

:ID:cipeco0y

プログラミング以外の話題はロビーのスレッドでお願いします。
ツールのソースについての質問などはこちらでも構いません。

:ID:+LyRQS9z

>>45
遅くなりましたが、ご指摘いただいた件を含め、コードの不備を修正しました。

全体的なアルゴリズムそのものは変更していませんが、remove_bracket関数の処理が変わったほか、
calculate関数等にも変更を施しています。
そのため、コード全体で変更箇所が多くなっている点についてはご了承ください。

変更点の詳細については下記の更新情報をご参照ください。
http://smdn.jp/programming/tips/polish/#DocumentLog

問題点のご報告ありがとうございました。

:ID:kmpqh+b/

「二分木を使った数式の逆ポーランド記法化と計算」のコードを修正していただき、どうも有り難う御座います。
今までとは趣きが大きく変わりましたので正直なところ驚きました。

本格的に書き直していただきましたので、今一度、細部に渡って確認させていただきました。
致命的な不具合は見つかりませんでしたが、気になった箇所が幾つかありましたので、それらを列挙させていただきます。
どうでも良い点ばかりかも知れませんが、多少なりとも何かのヒントにでも繋がれば幸です。

get_pos_operator関数(size_t型)の戻り値が-1になる場合がある。
処理系によってはNG?
size_tは通常unsigned型で定義されるので、ゼロ以下の値は避けた方が良い。
この関数中のpos_operator変数(size_t型)も同様。
この関数の呼びだし元も見直した方がよいかも知れません。

C言語の場合はchar型のポインタで書き換えた方がスッキリすると思います。
ポインタ型が使えない他言語とアルゴリズムを揃えておきたい場合は、size_tをint型やlong型で置き換えるとよいかも。

この関数内では演算子の最低の優先度をあらわす変数priority_currentを4で初期化していますが、
対応する演算子を増やすなどした場合、この値を変更するのを忘れると不具合の原因になりえます。
4よりも大きな、できるだけ大きな整数値で初期化した方が良いと思います。

以下のコードの中で★印で囲まれたコメントは、私が追記したモノです。
==========================================================================

size_t get_pos_operator(char *exp) // ★ size_t型の関数の戻り値に-1? ★
{

   size_t i;                      // ★ size_tは必要? INT_MAX超の長大な式を扱う?                   ★
   size_t pos_operator = -1;      // ★ size_t型に-1?                                               ★
   int priority_current = 4;      // ★ <limits.h>で定義されるINT_MAX等の充分大きな値で初期化したい  ★
                                  // ★ 対応する演算子を増やした場合に、ここを変更し忘れてもOK     ★

==========================================================================

calculate関数内で子ノードのポインタにNULLを代入している次の2行は不要?
==========================================================================
int calculate(Node* node)

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

==========================================================================

remove_outer_most_bracket関数の先頭部分が冗長で少々難解。次の2点で簡素化可能。

   ・int has_outer_most_bracket = ( '(' == exp[0] );  //  boolean
   ・for (i = 0; i < len; i++) {  //  i=1ではなく、i=0から開始

この関数は何度も呼び出されるので、できるだけ先頭部の処理を軽くしておきたい。
丸括弧の対応を厳密にチェックする関数を別途用意して、数式入力直後に1度だけチェックするようにすれば、この関数の動作を簡素化できる。
この関数の目的を「式全体が括弧で括られている場合の処理のみ」に限定した方がよい。
特にこの関数の先頭付近でのstrlenは止めた方がよい。
==========================================================================
int remove_outer_most_bracket(char *exp)
{

   size_t i;
   // ★ expが長大な場合、strlenは遅い                                                           ★
   // ★ この関数は再帰的に何度も呼び出されるので、できるだけ先頭の処理を軽くしたい              ★
   // ★ 括弧の対応をチェックする際にexpを最後までスキャンすれば、strlen無しでも文字列長は分かる ★
   size_t len = strlen(exp);
   int has_outer_most_bracket = 0; // 最も外側に括弧を持つかどうか(0=持たない、1=持つ)
   // ★ int has_outer_most_bracket = ( '(' == exp[0] );  で初期化した方がよい?                 ★
   int nest = 0;
   // ★ この後のfor文を工夫すれば、次の10行は不要? ★
   if ('(' == exp[0]) {
       // 0文字目が開き丸括弧の場合、最も外側に丸括弧があると仮定する
       nest = 1;
       has_outer_most_bracket = 1;
   }
   else if (')' == exp[0]) {
       // 0文字目が閉じ丸括弧の場合、エラーとする
       fprintf(stderr, "unbalanced bracket: %s\n", exp);
       return -1;
   }
   // 1文字目以降を1文字ずつ検証
   // ★ この前のifとelse ifの両ブロックを削除した場合は、i=1ではなく、i=0からスキャン開始 ★
   for (i = 1; i < len; i++) {
       if ('(' == exp[i]) {
           // 開き丸括弧なので深度を1増やす
           nest++;
       }
       else if (')' == exp[i]) {
           // 閉じ丸括弧なので深度を1減らす
           nest--;
           // ★ ここに nest<0 の場合のエラー処理を入れる? ★
           // 最後の文字以外で閉じ丸括弧が現れた場合、最も外側には丸括弧がないと判断する
           if (i < len - 1 && 0 == nest)
             has_outer_most_bracket = 0;  // ★ false ★
       }
   }
                   :
       // 最初と最後の文字を取り除く
       for (i = 0; i < len - 2; i++) {
           exp[i] = exp[i + 1];
       }
       exp[i] = '\0';
       // 再帰的に呼び出す
       // "((1+2))"など、多重になっている括弧を取り除くため再帰的に呼び出す

// ★ この関数は重いので、旧バージョンのように必要な場合のみ呼び出した方が良い ★
// ★ 例えば、次のように変更 ★
// ★ if ( exp[0] == '(' && exp[i-1] == ')' { ★
// ★ if ( remove_outer_most_bracket(exp) < 0 ) return -1; ★
// ★ } ★
// ★ return 0; ★

       return remove_outer_most_bracket(exp);
     }

==========================================================================

parse_expression関数内で使われているmemsetは避けた方がよい?
計算式が長大にると遅くなる。
==========================================================================
int parse_expression(Node* node)
{

             :
       // 演算子の左側を左の部分式としてノードを構成
       // ★ expが長大になるとmemsetは遅くなる                               ★
       // ★ strncpy後にnode->left->exp[pos_operator]='\0'で終端した方が速い ★
       memset(node->left->exp, 0, MAX_EXP_LEN);
       strncpy(node->left->exp, node->exp, pos_operator);
       // 左側のノード(部分式)について、再帰的に二分木へと分割する
       if (parse_expression(node->left) < 0)
           return -1;
       // 演算子の右側を右の部分式としてノードを構成
       // ★ node->expはnull文字で終端されているのでstrncpyではなく、strcpyでOK ★
       // ★     strcpy(node->right->exp, node->exp + pos_operator + 1);          ★
       memset(node->right->exp, 0, MAX_EXP_LEN);
       strncpy(node->right->exp, node->exp + pos_operator + 1, len_exp - pos_operator);

==========================================================================

3つのtraverse関数の出力結果が見難いので、各式の間に空白等の区切り文字を入れた方がよい。
区切り文字を入れないと、2桁以上の数値を計算した場合に問題あり。
==========================================================================
void traverse_postorder(Node* node)
{

            :
   // 巡回を終えた後でノードの演算子または項を表示する
   printf("%s", node->exp);  // ★ 空白を追加して"%s "とすると見易くなる ★

}
==========================================================================

次はソースコードの書き方に関する問題なので、何らかの正解があるわけではありません。
私個人の意見としては "else if"が何度も続くコードは少々読みにくいと感じます。
次の場合のように、if文に連なるブロックが途中でreturnで抜けている場合は、
後続の条件判断は"else if"ではなく"if"文にした方がスッキリして読みやすいと思います。
==========================================================================
int parse_expression(Node* node)
{

          :
   if ((size_t)0 == pos_operator || (size_t)(len_exp - 1) == pos_operator) {
     // 演算子の位置が式の先頭または末尾の場合は不正な式とする
       fprintf(stderr, "invalid expression: %s\n", node->exp);
       return -1;
   }
   else if ((size_t)-1 == pos_operator) { //  ★ else if ではなく、if の方が読みやすい ★
       // 式Expressionに演算子が含まれない場合、Expressionは項であるとみなす
       // (左右に子ノードを持たないノードとする)
       node->left  = NULL;
       node->right = NULL;
       return 0;
   }
   else {  //  ★ else ブロックを止めた方が読みやすい ★
       // 左側・右側のノードを作成
       node->left   = create_node();
       node->right  = create_node();

==========================================================================

その他

 ・コメント文が充実しているのは理解の助けになり大変ありがたいのですが、
   体言止めを使うなどして、できるだけ文章を簡潔に表現した方が読みやすくなると思います。

任意演算のアルゴリズムは処理速度を要求されるインタープリタの一部として使用されるケースもあると思います。
多少は速度を意識した書き方にしておいた方が、多くの方から好感を持たれると思います。

それでは良いお年をお迎えください。

:ID:+LyRQS9z

詳細にわたりレビューしていただきありがとうございます。
C言語は普段使いの言語ではないため細部が甘くなりがちで、またこういった意見を
いただく機会もなかなかないので、大変ありがたく思います。

指摘いただいた箇所については反映したい部分が多々ありますが、修正が完了するまでには
また時間をいただくことになりそうなので、勝手ながら留意事項として本文中に
書き込みへのリンクを貼らせていただく形での暫定的な対応とさせていただきました。
(http://smdn.jp/programming/tips/polish/#Implementation_C)

現状本文の方も変更を考えている部分があるので、それと合わせて修正後に
また改めてお知らせいたします。
(おそらく来年2018年1月中旬〜下旬ごろになると思います)

なお、以下は頂いた部分についての現時点での修正対応予定です。

概ね、コードの簡略化・読みやすさを優先とし、恐縮ながら速度の向上が得られる
のみとなる修正はしない、という方針に基づく判断となります。

  • 採用の方向
    • size_t型に-1? (char*よりはintへの変更で修正予定)
    • priority_currentの初期値をINT_MAXに (なぜ今までそうしなかったのか…)
    • traverse系関数の出力に空白を追加 (前回変更は出力を変えない変更のみとしたため、今後本文と合わせて修正予定)
  • 採用に肯定的
    • remove_outer_most_bracketの先頭部の簡素化 (現行実装が冗長な感があったので、頂いた案を精査の上、改善)
    • remove_outer_most_bracketの再帰呼出し前の必要性チェック (上をそのまま採用するなら、これも同様に)
    • returnで抜けるifの分離とelse部の展開 (読みやすさを見て決定)
  • 採用に消極的
    • parse_expressionでのmemset,strncpy (C言語レベルでもleftとrightで処理に相違がないようにしたい、C言語レベルでの差異を理由に意味的にも何か違いがあるのかという疑問が生じないようにしたい)
    • calculate内で子ノードのポインタにNULL (処理上は冗長だが、子ノードを持たない状態にすることを明示しておきたい。 また、今後の拡張として計算過程のツリーを表示する場合を考えていたので、そのままのしておきたい。)
    • コメント文 (サンプルコードの説明ではコードの意図と目的を明確にしたく、それに従い体現止めの採用には消極的、ただ文体の不一致修正はする)

実用ではなくあくまで理解のためのサンプルコードという位置づけのため、また扱う文字列長も
高々キロバイト単位のため、実用や高速化を目的とした改善はコードの利用者各自で
行ってもらいたく思っています。

速度を意識した改善は行いたくはありますが、あくまでサンプルコードとしての位置づけでの公開ですし、
また実用を考慮しだすと速度以外にも変更したい部分は多々あります。
例えば、演算子も*や/ではなく×や÷を使えるようにしたい、その他記号等も使用したいと考えると
char配列ではなく非ASCIIに対応する文字列型を使うべき。 あるいは計算では浮動小数点ではなく
固定小数点を使うべき、など。 これらに対応するとコード量が増えてサンプルとしては長大になるため、
ここで扱うべき範囲を超えるとして省略しています。

もちろん、memsetやstrlenに関する点は実用を主眼とした場合には有用ですので、今後コードを書く際の
参考にしたいと思います。

いずれにせよ、改善に繋がるご意見は大変ありがたいので、他にももし改良点がありましたら
気兼ねなく書き込んでいただければと思います。
あるいは、改善点を修正したコード全文をこちらに貼っていいただければ、本文に掲載する
コードに直接反映しないにしても、本文中にて紹介という形にさせていただくこともできます。

それでは良いお年を。

:ID:+LyRQS9z

>>48
大変遅くなりましたが、頂いたご指摘をもとに修正した内容を先ほど公開いたしました。
変更した箇所としなかった箇所は下記のとおりとなります。
パフォーマンス関連での修正にはご満足いただけない部分があるかとは思いますが、ご確認いただければと思います。

変更した箇所

size_t型に-1
indexはintに、lengthのみsize_tを使用するように変更
priority_currentの初期値をINT_MAXに
INT_MAXを使用するように変更(他言語も同様に整数の最大に相当する定数値に置き換え)
traverse系関数の出力に空白を追加
すべての記法で項および演算子の間に空白を入れるように変更
前置記法・後置記法では末尾にも空白が出てしまうが、実装の簡略化のため割り切り
remove_outer_most_bracketの先頭部の簡素化
括弧の対応の検証は、新たに関数validate_bracket_balanceを用意して分離し、parseする前に一度だけ呼び出すように変更
式中の文字の検証と同時にlenを計上することにより、strlenの呼び出しを削除
冒頭のif-else ifブロックは変更せず(以下理由)

以下のようにすればi=0からスキャンになり冒頭の見かけ上の冗長さはなくなるが、逆に開き括弧が出現するたびにif (0 == i)が評価されることになり、最終的な判断としては変更なしに

        for (i = 0, len = 0; exp[i]; i++, len++) {
            if ('(' == exp[i]) {
                // 開き丸括弧なので深度を1増やす
                nest++;

                // 0文字目が開き丸括弧の場合、最も外側に丸括弧があると仮定する
                if (0 == i)
                    has_outer_most_bracket = 1;
            }
remove_outer_most_bracketの再帰呼出し前の必要性チェック
括弧を削除したあと、さらに外側に括弧が残る場合のみ再起呼び出しするように変更
returnで抜けるifの分離とelse部の展開
if内でreturnする場合はifを単離し、else部は展開
parse_expressionではreturnする前に不要な処理を行わないよう評価順序も変更

変更しなかった箇所

has_outer_most_bracketの値にtrue/false
関数の成功/失敗をintで統一している、またMSVCでのstdbool.hの扱いに難あり?
検証の上使用するにしても結局ここだけなので、現状維持
parse_expressionのmemset
先にmemsetするべきと考える文化に従うならここ(あるいはcreate_node)でやるのが適当、それを冗長と考えるなら\0で終端するのが適当、そのどちらに寄せるかの判断はここでは留保とし、現状維持
(パフォーマンスを再優先にした改善や、より高度な実用を目指した変更は、やはり目的に応じて個々でやってもらいたいし、それができるようMITライセンスを設定している)
parse_expressionのrightに対するstrncpyはstrcpyにできる
leftとrightはC言語レベルでも差異が出ないようにしておきたい
三項以上の演算子や関数に対応する場合など(cond ? cond-true : cond-false, func(arg1, arg2, arg3...))を考えると、二分木の場合に特化した最適化の感もある
calculateでの子ノードへのポインタにNULL設定は省略できる
冗長といっても単純代入、再帰呼出しやstrlen等に比べればコストは軽微と考え、意味上の明確さを優先のため現状維持

変更箇所の差分を次の投稿にて別途掲載しますので合わせてご覧ください。 また、上記以外(コード以外)の変更点については下記の更新情報をご参照ください。
http://smdn.jp/programming/tips/polish/#DocumentLog

改めて、ご指摘をいただきありがとうございました。

:ID:+LyRQS9z

>>50
以下、変更箇所の差分です。

diff --git a/contents/programming/tips/polish/_source/polish.c b/contents/programming/tips/polish/_source/polish.c
index abd4b22..ef61b7a 100644
--- a/contents/programming/tips/polish/_source/polish.c
+++ b/contents/programming/tips/polish/_source/polish.c
@@ -2,6 +2,7 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
+#include <limits.h>
 
 typedef struct Node Node;
 
@@ -32,24 +33,19 @@ Node* create_node()
 // (成功した場合は0、エラーの場合は-1を返す)
 int remove_outer_most_bracket(char *exp)
 {
-    size_t i;
-    size_t len = strlen(exp);
+    int i;
+    size_t len;
     int has_outer_most_bracket = 0; // 最も外側に括弧を持つかどうか(0=持たない、1=持つ)
-    int nest = 0;
+    int nest = 0; // 丸括弧の深度(式中で開かれた括弧が閉じられたかどうか調べるために用いる)
 
     if ('(' == exp[0]) {
         // 0文字目が開き丸括弧の場合、最も外側に丸括弧があると仮定する
-        nest = 1;
         has_outer_most_bracket = 1;
-    }
-    else if (')' == exp[0]) {
-        // 0文字目が閉じ丸括弧の場合、エラーとする
-        fprintf(stderr, "unbalanced bracket: %s\n", exp);
-        return -1;
+        nest = 1;
     }
 
     // 1文字目以降を1文字ずつ検証
-    for (i = 1; i < len; i++) {
+    for (i = 1, len = 1; exp[i]; i++, len++) {
         if ('(' == exp[i]) {
             // 開き丸括弧なので深度を1増やす
             nest++;
@@ -58,51 +54,48 @@ int remove_outer_most_bracket(char *exp)
             // 閉じ丸括弧なので深度を1減らす
             nest--;
 
-            // 最後の文字以外で閉じ丸括弧が現れた場合、最も外側には丸括弧がないと判断する
-            if (i < len - 1 && 0 == nest)
+            // 最後の文字以外で開き丸括弧がすべて閉じられた場合、最も外側には丸括弧がないと判断する
+            // 例:"(1+2)+(3+4)"などの場合
+            if (0 == nest && exp[i + 1]) {
                 has_outer_most_bracket = 0;
+                break;
             }
         }
-
-    // 括弧の深度が0以外の場合
-    if (0 != nest) {
-        // 開かれていない/閉じられていない括弧があるので、エラーとする
-        fprintf(stderr, "unbalanced bracket: %s\n", exp);
-        return -1;
     }
-    // 最も外側に丸括弧がある場合
-    else if (0 != has_outer_most_bracket) {
-      if (len <= 2) {
+
+    // 最も外側に丸括弧がない場合は、何もしない
+    if (0 == has_outer_most_bracket)
+        return 0;
+
     // 文字列の長さが2未満の場合は、つまり空の丸括弧"()"なのでエラーとする
+    if (len <= 2) {
         fprintf(stderr, "empty bracket: %s\n", exp);
         return -1;
     }
-      else {
-        // 最初と最後の文字を取り除く
+
+    // 最初と最後の文字を取り除く(最も外側の丸括弧を取り除く)
     for (i = 0; i < len - 2; i++) {
         exp[i] = exp[i + 1];
     }
     exp[i] = '\0';
 
-        // 再帰的に呼び出す
-        // "((1+2))"など、多重になっている括弧を取り除くため再帰的に呼び出す
+    // 取り除いた後の文字列の最も外側に括弧が残っている場合
+    // 例:"((1+2))"などの場合
+    if ('(' == exp[0] && ')' == exp[i - 1])
+        // 再帰的に呼び出して取り除く
         return remove_outer_most_bracket(exp);
-      }
-    }
-    // 最も外側に丸括弧がない場合
-    else {
-        // 何もしない
+    else
+        // そうでない場合は処理を終える
         return 0;
-    }
 }
 
-// 式expから最も優先順位が低い演算子を探して位置を返す関数
+// 式expから最も右側にあり、かつ優先順位が低い演算子を探して位置を返す関数
 // (演算子がない場合は-1を返す)
-size_t get_pos_operator(char *exp)
+int get_pos_operator(char *exp)
 {
-    size_t i;
-    size_t pos_operator = -1; // 現在見つかっている演算子の位置(初期値として-1=演算子なしを設定)
-    int priority_current = 4; // 現在見つかっている演算子の優先順位(初期値として4=最高(3)+1を設定)
+    int i;
+    int pos_operator = -1; // 現在見つかっている演算子の位置(初期値として-1=演算子なしを設定)
+    int priority_current = INT_MAX; // 現在見つかっている演算子の優先順位(初期値としてINT_MAXを設定)
     int nest = 0; // 丸括弧の深度(括弧でくくられていない部分の演算子を「最も優先順位が低い」と判断するために用いる)
     int priority;
 
@@ -127,6 +120,7 @@ size_t get_pos_operator(char *exp)
 
         // 括弧の深度が0(丸括弧でくくられていない部分)かつ、
         // 現在見つかっている演算子よりも優先順位が同じか低い場合
+        // (優先順位が同じ場合は、より右側に同じ優先順位の演算子があることになる)
         if (0 == nest && priority <= priority_current) {
           // 最も優先順位が低い演算子とみなし、その位置を保存する
           priority_current = priority;
@@ -142,8 +136,8 @@ size_t get_pos_operator(char *exp)
 // (成功した場合は0、エラーの場合は-1を返す)
 int parse_expression(Node* node)
 {
-    size_t pos_operator;
-    size_t len_exp;
+    int pos_operator;
+    size_t len;
 
     if (!node)
         return -1;
@@ -152,26 +146,28 @@ int parse_expression(Node* node)
     if (remove_outer_most_bracket(node->exp) < 0)
         return -1;
 
-    len_exp = strlen(node->exp);
-
     // 式expから演算子を探して位置を取得する
     pos_operator = get_pos_operator(node->exp);
 
-    if ((size_t)0 == pos_operator || (size_t)(len_exp - 1) == pos_operator) {
-      // 演算子の位置が式の先頭または末尾の場合は不正な式とする
-        fprintf(stderr, "invalid expression: %s\n", node->exp);
-        return -1;
-    }
-    else if ((size_t)-1 == pos_operator) {
-        // 式Expressionに演算子が含まれない場合、Expressionは項であるとみなす
+    if (-1 == pos_operator) {
+        // 式expに演算子が含まれない場合、expは項であるとみなす
         // (左右に子ノードを持たないノードとする)
         node->left  = NULL;
         node->right = NULL;
-
         return 0;
     }
-    else {
-        // 左側・右側のノードを作成
+
+    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();
 
@@ -181,7 +177,7 @@ int parse_expression(Node* node)
         return -1;
     }
 
-        // 演算子の左側を左の部分式としてノードを構成
+    // 演算子の左側を左の部分式としてノードを構成する
     memset(node->left->exp, 0, MAX_EXP_LEN);
     strncpy(node->left->exp, node->exp, pos_operator);
 
@@ -189,9 +185,9 @@ int parse_expression(Node* node)
     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_exp - pos_operator);
+    strncpy(node->right->exp, node->exp + pos_operator + 1, len - pos_operator);
 
     // 右側のノード(部分式)について、再帰的に二分木へと分割する
     if (parse_expression(node->right) < 0)
@@ -202,7 +198,6 @@ int parse_expression(Node* node)
     node->exp[1] = '\0';
 
     return 0;
-    }
 }
 
 // 後行順序訪問(帰りがけ順)で二分木を巡回して
@@ -216,7 +211,8 @@ void traverse_postorder(Node* node)
         traverse_postorder(node->right);
 
     // 巡回を終えた後でノードの演算子または項を表示する
-    printf("%s", node->exp);
+    // (読みやすさのために項の後に空白を補って表示する)
+    printf("%s ", node->exp);
 }
 
 // 中間順序訪問(通りがけ順)で二分木を巡回して
@@ -228,27 +224,36 @@ void traverse_inorder(Node* node)
         printf("(");
 
     // 表示する前に左の子ノードを再帰的に巡回する
-    if (node->left)
+    if (node->left) {
         traverse_inorder(node->left);
 
+        // 読みやすさのために空白を補う
+        printf(" ");
+    }
+
     // 左の子ノードの巡回を終えた後でノードの演算子または項を表示する
     printf("%s", node->exp);
 
     // 表示した後に右の子ノードを再帰的に巡回する
-    if (node->right)
+    if (node->right) {
+        // 読みやすさのために空白を補う
+        printf(" ");
+
         traverse_inorder(node->right);
+    }
 
     // 左右に項を持つ場合、読みやすさのために項の後に閉じ括弧を補う
     if (node->left && node->right)
         printf(")");
 }
 
-  // 先行順序訪問(行きがけ順)で二分木を巡回して
-  // すべてのノードの演算子または項を表示する関数
+// 先行順序訪問(行きがけ順)で二分木を巡回して
+// すべてのノードの演算子または項を表示する関数
 void traverse_preorder(Node* node)
 {
     // 巡回を始める前にノードの演算子または項を表示する
-    printf("%s", node->exp);
+    // (読みやすさのために項の後に空白を補って表示する)
+    printf("%s ", node->exp);
 
     // 左右に子ノードをもつ場合、表示した後にノードを再帰的に巡回する
     if (node->left)
@@ -317,6 +322,40 @@ void remove_space(char *exp)
     *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)ノードを作成する
@@ -329,23 +368,27 @@ int main()
     // 入力された式から空白を除去する
     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");
  • >>1と入力すると1番へのアンカーになります。
  • 投稿内容はPukiWiki記法で整形されます。
    • 以下のPukiWiki記法が使えます。
      • 引用文
      • 番号付きリスト、番号なしリスト、定義リスト
      • 整形済みテキスト
        • 複数行のコードブロック・コマンド出力を書き込むには#code{{〜}}、#prompt{{〜}}と記入してください。
        • AAを書き込むには#aa{{〜}}と記入してください。
      • 表組み
      • 見出し
      • 強調・斜体、取り消し線・下線
      • 文字色(&color)、文字サイズ(&size)
      • 注釈
    • URL・メールアドレスは自動的にリンクになります。
    • 詳しくはPukiWikiのFormattingRulesを参照してください。
  • 書き込み後に投稿内容を編集することは出来ません。