プログラミング関連の話題・質問用のスレッド。 (最新5件の投稿) Atom 1.0

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

: ID:cipeco0y

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

: 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");
: ID:JffJ8cfs

はじめまして。
プログラムの参考に閲覧しました。
プログラムに疑問がわいたのでこちらに失礼します。

Programming / Tips / 二分木を使った数式の逆ポーランド記法化と計算
にある最後のC言語でのコードについて。
入力計算式を
1 (10 * 10) / 10
などとカッコの前後に演算子のない数値を記入したとき。
計算成功,になりますが,計算結果はでたらめです。
本来は計算成功ではないと思われますが,これは仕様なのでしょうか。

初歩的な質問で,失礼しました。

: ID:5U/9Z0Js

>>52
ご質問ありがとうございます。

制限事項としても明記していますが、例示いただいた式のような
「暗黙の乗算を含む部分式に関する動作は未定義」となります。
ですので、ご指摘のとおり本来なら計算成功ではありませんが、
現状の動作で仕様通りということになります。

現時点での実装では、こういった式をエラーとするような処理は
実装していないため、エラー報告はされずに処理が継続し、
最終的には計算成功扱いとなるという動作になっています。

また、式"2(1+2)"は"2*(1+2)"のように暗黙の乗算を含む式とは解釈されず、
計算できない単一の項"2(1+2)"として扱われそのまま出力されるため、
計算成功扱いにはなりますが期待するような結果は出力されないという動作になります。

  • 書き込み完了後に投稿内容を編集することは出来ません。
  • >>1と入力すると1番へのアンカーになります。
  • 投稿内容はPukiWiki記法で整形されます。
    • 以下のPukiWiki記法が使えます。
      • 引用文
      • 番号付きリスト、番号なしリスト、定義リスト
      • 整形済みテキスト
        • 複数行のコードブロックを書き込むには次のように記入してください。
          #code{{
          int x = 2;
          int y = 3;
          }}
        • 複数行のコマンド出力を書き込むには次のように記入してください。
          #prompt{{
          C:\> echo "foo"
          "foo"
          }}
      • 表組み
      • 見出し
      • 強調・斜体、取り消し線・下線
      • 文字色(&color)、文字サイズ(&size)
      • 注釈
    • URL・メールアドレスは自動的にリンクになります。
    • 詳しくはPukiWikiのFormattingRulesを参照してください。