質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.48%

プログラムを制作したい。

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 445
退会済みユーザー

退会済みユーザー

前提・実現したいこと

プログラミングの勉強を初めて2ヶ月ほどのものです。
まだまだわからないことが多いので、お手柔らかにお願いいたします。
c言語について、通常の式を逆ポーランド記法に変換して式自体を出力するプログラムを制作しています。
main.c(関数を使って逆ポーランド記法に変換していくコード)
stack.c(スタック関連の関数を入れているコード)
stack.h (ヘッダファイル)
queue.c (キュー関連の関数を入れているコード)
queue.c(ヘッダファイル)
lib1.c(課題で提供されている関数の入った補助コード)
lib1.h(ヘッダファイル)
これらが関連のファイルで分割コンパイルして実行ファイルmain.exeを作ります。
最終的には括弧の含んだ式の処理もしたいのですが、一旦数字と符号のみの式を考えることにしました。
想定しているアルゴリズムは、
(キーボード入力から得た文字列をトークンtとする。)
(スタックの頂上の内容をsとする。)
・tが数字のとき
→tをenqueue
・tが符号のとき
→スタックが空ならtをpush
・スタックになにかあるとき
・符号優先度がs<tのとき
→tをpush
・符号優先度がs>=tのとき
→スタックが空になるかs<tになるまでpopしてその内容をenqueue
これを入力したトークンtの数だけ実行していき、最後までtを見終えたらスタックをすべてpopして、その内容をenqueueし、
queueを出力すると逆ポーランド記法になっているというものです。

発生している問題・エラーメッセージ

以下、式:1-4*3+2 で実行した実行結果です。
ちなみに、ほしい結果は、143*-2+ です。

% ./main.exe
これは最新版です
input> 1-4*3+2
数字をエンキューします
enqueue(1)
記号の処理を始めます
push(-)
数字をエンキューします
enqueue(4)
記号の処理を始めます
演算子の比較を始めます
s = - 優先度は6        <ーーー(1)
t = * 優先度は7
t>s
push(*)
数字をエンキューします
enqueue(3)
記号の処理を始めます
演算子の比較を始めます
t<s
s = * 優先度は7
t = + 優先度は6
pop = *
enqueue(*)
s = - 優先度は-1       <ーーー(2)
t = + 優先度は6
push(+)
数字をエンキューします
enqueue(2)
--- スタックの中身出していきます ---
pop = +
enqueue(+)
pop = -
enqueue(-)
1 4 3 * 2 + -
%


1行目出力は、今までの変更のバックアップとごっちゃにならないために出力してるものなので気にしないでください...()
問題の箇所は、「<ーーーー(2)」で指している部分で、優先度が正しく得ることが出来ていません。
ちなみに優先度における「-1」という出力はどの符号にも当てはまらなかった場合に出力される値です。

該当のソースコード

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "lib1.h"
#include "stack.h"
#include "queue.h"
#define MAX_TOKEN_NUM 200
int main(void){
   int i,j,k,kakko,result,tnum;
   char a,*s,m,*sp,*tp,*token[MAX_TOKEN_NUM],*p,x;
   printf("これは最新版です\n");
   // 標準入力から1行分の文字列を読み込み,トークンに分割する.
   tnum = input(token,MAX_TOKEN_NUM);
   //■ 中置記法の式の構成要素(トークン)を先頭から順に注目しながら以下を繰り返す.
   for (i = 0; i < tnum; i++) {
       //● 今注目中のトークン t と記号スタックの状態に応じて,表 2 の通り処理する.

       if (isNumberStr(token[i])) {
           //・数字だったとき
           printf("数字をエンキューします\n");
           enqueue(*token[i]);
       }else if (isOperatorStr(token[i])) {
           //・記号だったとき
           printf("記号の処理を始めます\n");
           if (isStackEmpty()) {
               //・スタックが空だったとき
               push(*token[i]);
           }else{
               //・スタックになにかあるとき
               printf("演算子の比較を始めます\n");
               m = peek();
               sp = &m;           //spはpeekの値のアドレス
               tp = &*token[i];   //tpは注目中のトークンのアドレス
               //スタックの中身が演算子だったとき
               if (priority(tp)/*t*/ >= /*s*/priority(sp)) {
               printf("s = %c 優先度は%d\n",peek(),priority(sp));
               printf("t = %c 優先度は%d\n",*token[i],priority(tp));
                   //・tのほうがsより優先度が高いとき
                   //演算子tをpushする
                   printf("t>s\n");
                   push(*token[i]);
               }else{
                   printf("t<s\n"); //・sのほうがtより優先度が高いとき
                   while(isStackEmpty()==0){ //スタックが空になるまでpopしenqueue
                       m = peek();
                       sp = &m;
                       printf("s = %c 優先度は%d\n",peek(),priority(sp));
                       printf("t = %c 優先度は%d\n",*token[i],priority(tp));
                       if (priority(tp)/*t*/ <= /*s*/priority(sp)) {
                           a = pop();
                           p = &a;//この文が何故かpriority(-1)問題において大切
                           enqueue(a);//ここでaの内容をenqueueしている時点で上の行の文は関係はいはず
                       }else break;
                   }
                   push(*token[i]);//演算子tをpushする
               }
           }
       }
   }
   //stackが空になるまでenqueue
   printf("--- スタックの中身出していきます ---\n");
   while(isStackEmpty()==0){
       a = pop();
       enqueue(a);
   }
   printQueue();
}


stack.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"

STACK_TYPE gStack[STACK_SIZE];
int gSNum = 0;

void push(STACK_TYPE x){
   gStack[gSNum++] = x;
   printf("push(%c)\n",x);
}

STACK_TYPE pop(void){
   char x = gStack[gSNum - 1];

   gSNum--;
   printf("pop = %c\n",x);
   return x;
}

void printStack(void){
   int i;
   printf("STACK[ ");
   for (i=0; i<gSNum; i++){
       printf("%.1lf ", gStack[i]);
   }
   printf("]\n");
}

int isStackEmpty(void){
   return gSNum == 0;
}

int isStackFull(void){
   return gSNum == STACK_SIZE;
}
STACK_TYPE peek(void){
   STACK_TYPE x;
   if(isStackEmpty() != 1){
       //空じゃないなら
       x = gStack[gSNum-1];
       return x;
   }else{
       //空状態なら
       fprintf(stderr,"エラー:空状態でpeekはできません\n");
       exit(1);
   }
}
//符号優先度を出す関数
int priority(char *op){
   int result,a=-1;
   result = strcmp(op,"=");
   if(result == 0){
       a = 2;
   }
   result = strcmp(op,"==");
   if(result == 0){
       a = 3;
   }
   result = strcmp(op,"!=");
   if(result == 0){
       a = 3;
   }
   result = strcmp(op,"+");
   if(result == 0){
       a = 6;
   }
   result = strcmp(op,"-");
   if(result == 0){
       a = 6;
   }
   result = strcmp(op,"*");
   if(result == 0){
       a = 7;
   }
   result = strcmp(op,"/");
   if(result == 0){
       a = 7;
   }
   result = strcmp(op,"%");
   if(result == 0){
       a = 7;
   }
   result = strcmp(op,"^");
   if(result == 0){
       a = 8;
   }
   result = strcmp(op,"(");
   if(result == 0){
       a = 99;
   }
return a;
}
STACK_TYPE retrieve(POSITION n){
   if(isStackEmpty()) fprintf(stderr,"retrieve:スタックが空状態です\n");
   if(n<0 || n >= gSNum) fprintf(stderr,"retrieve:位置が正しくありません\n");

   return gStack[n];
}
int stackTop(void){
   int a;
   a = gSNum;

   return a;
}


queue.c

#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
QUEUE_TYPE gQueue[QUEUE_SIZE];
int gQNum = 0;
void error(char *s){
   fflush(stdout);
   fprintf(stderr,"\n%s\n",s);
   exit(1);
}
void enqueue(QUEUE_TYPE x){
   if(isQueueFull())
       error("enqueue:待ち行列はフル状態です\n");

   gQueue[gQNum++] = x;
   printf("enqueue(%c)\n",x);
}
QUEUE_TYPE dequeue(void){
   QUEUE_TYPE x;
   int i;

   if(isQueueEmpty())
       error("dequeue:待ち行列は空状態です\n");

   x = gQueue[0];
   for(i=1;i<=gQNum-1;i++)
     gQueue[i-1] = gQueue[i];
   gQNum--;
   return x;
}
int isQueueEmpty(void){
   return gQNum == 0;
}
int isQueueFull(void){
   return gQNum == QUEUE_SIZE;
}
void printQueue(void){
   int i;
   for(i=0; i<gQNum; i++){
       printf("%c",gQueue[i]);
       if(i != gQNum -1)printf(" ");
   }
   printf("\n");
}


かなり試行錯誤を繰り返して、宣言しているのに使っていない変数や関数がたくさんあり、
ごちゃごちゃしていて申し訳ないです。
また、lib1.cは提供されたものなので、公開できません。

試したこと

とにかくpriority関数あたりがなんだかうまく行ってないので、どのようなときに「-1」と出力されてしまうのかいろんな式で実行しましたが、どういう条件でうまく行かないのかわかりませんでした。
さらに、
main.cの一部抜粋

p = &a;//この文が何故かpriority(-1)問題において大切
enqueue(a);//ここでaの内容をenqueueしている時点で上の行の文は関係はいはず


上記、main.cのコメントでも書いたとおり、ここのp=&a;があるのと無いのとで、出力が変わってきます。
2行目コメントの通り、アルゴリズム上全く関係のない行なのですが、どういう事情なのでしょうか。

補足情報(課題について)

この課題は授業で出された課題の一部です。
教員はこれまでに習ったことを理解すれば解けるといい、質問は一切受け付けていない状況です。
しかし、問題の箇所はアドレスが関連してそうな気が素人なりに勘づいているのですが、そこは授業で習っていません。
おおよそ、スタックとキューと逆ポーランド記法について学んだと言った感じです。
逆に言うと、スタックとキューと逆ポーランド記法以外はなんとなくな理解なので、
もしかするとかなり初歩的な勘違いをしている可能性も大いにあります。
自信がないところとすれば、priority関数について引数の入れ方をpriority(sp) (sp = &m)のようなアドレスで渡すようなやり方は授業内でしたことがない。(習っていない)
授業ではこんなふうに使っていました。

int main(void){
   char *op[OPNUM] = {"+", "*", "-", "/", "&", "^", "%", "=", "==", "!="};
   int i;
   for (i=0; i<OPNUM; i++){
       printf("%s -> %d\n", op[i], priority(op[i]));
   }
   return 0;
}


理解度かなり低い状態ではあると思いますが、
教員に質問できない状況下でかなり時間かけて取り組みました。
回答よろしくおねがいします。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • fiveHundred

    2021/05/30 18:32

    > 自分のプログラムですら公開することが許されないようで、

    残念ながら手遅れです。
    履歴に残っています。
    退会せずに登録したままだったら、運営に連絡して対処できたはずなのに残念ですね(因果応報です)。

    キャンセル

  • 退会済みユーザー

    2021/05/31 09:22

    複数のユーザーから「意図的に内容が抹消された質問」という意見がありました
    解決後に編集機能を用いて質問内容を改変し関係のない内容にしたり、内容を削除する行為は禁止しています。
    投稿していただいた質問は、後に他の誰かが困ったときに助けになる情報資産になると考えるからです。
    「質問を編集する」ボタンから編集を行い、他のユーザにも質問内容が見えるように修正してください。

  • K_3578

    2021/06/01 15:39

    運営による質問文の復元を確認。

    キャンセル

回答 3

checkベストアンサー

+1

まず、mainを以下のように書き換えて実行してみてください

int main(void) {
    char l = '+', m = '*', n = '^';
    printf("%c:%d, %c:%d, %c:%d\n", l, priority(&l), m, priority(&m), n, priority(&n));
}


おそらく、ほとんどの優先度が-1になったはずです。

今度は、以下のmainを実行してみてください。

int main(void) {
    char *l = "+", *m = "*", *n = "^";
    printf("%s:%d, %s:%d, %s:%d\n", l, priority(l), m, priority(m), n, priority(n));
}


今度は、正しい優先度が得られたはずです。

要するに、単なるchar型の変数に&を適用しただけの値をpriorityに渡しても、
正しい優先度は得られないということです。

priorityはヌル終端された文字列が渡されることを前提としています。
単に&を前置して型だけ合わせても、ヌル終端されていないので、正常動作しません。

ところで、priorityの中身をみると、複数文字の符号も許容していることが分かります。
また、数字も複数桁になる可能性があります。
つまり、スタックやキューの型をcharにして1文字しか保存できないようにしていること自体が間違いで、
char*型にしてヌル終端文字列を保持できるようにすることを前提としているように見えます。

STACK_TYPEQUEUE_TYPEchar*型にして、関連する型を調整してあげれば、動作するのではないでしょうか。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2021/05/30 12:02

    全ておっしゃるとおりでした!
    限られた情報の中で、優しく丁寧に教えていただきありがとうございました。

    キャンセル

+1

ソースは全文見てません。
また、lib1.cが非公開とのことで再現テストができません。なので目視での話になります。
検証はしていないのであしからず。

priority関数で、引数のオペレータとリテラルをstrcmpで比較していますね。
文字列はchar[]で、末尾に\0が入っているのが前提です。

priority関数の冒頭で、引数のopをprintf("%s")してみてください。"-"の時だけ表示がおかしくなるかと思います。
これはスタック側のオペレータをpeekで取得した際、内部アドレスを返していると思いますが、-の隣に*が存在するせいだと思います。
質問文の実行結果では、-をpushしたあと*をpushし、一度*をpopしています。
終端のアドレス位置は更新していますが、*があった場所はそのまま残しています。なので、stackの配列は [-, *, \0, ...] となっています。
この状態でpeekすると-のアドレスが返ってきますが、このアドレスを起点とした文字列表現は"-*"となってしまいます。なぜなら連続するchar配列の\0までが文字列の扱いだからです。

解決するには、

  • popした際、取り出した文字のデータ領域を \0 で埋める
  • priorityの判定にstrcmpを使わない。演算子が1文字の前提ならop == '-'のように直接比較するので十分。

となるかと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

    char *op[OPNUM] = {"+", "*", "-", "/", "&", "^", "%", "=", "==", "!="};

"=" はどんなふうに使うのでしょうか?

四則演算と括弧だけなら、この程度のソースでできます。

#include <stdio.h>  // fgets, printf
#include <ctype.h>  // isspace, isdigit
#include <stdlib.h> // strtod

char *p;  unsigned char c;  const char o[] = "+-*/";

int get(void) { while (isspace(c = *p++)); return c; }

void expr(int i)
{
    if (o[i])
        for (expr(i+2); c == o[i] || c == o[i+1]; ) {
            int d = c;
            expr(i+2);
            printf(" %c", d);
        }
    else if (get() == '(') {
        expr(0);
        if (c == ')') get(); else c = 1;
    }
    else if (c == '.' || isdigit(c)) {
        printf(" %.15g", strtod(p-1, &p));
        get();
    }
    else c = 1;
}

int main(void)
{
    char s[256];
    printf("input> ");
    if (p = fgets(s, sizeof s, stdin)) {
        expr(0);
        if (c) puts(" Error"); else putchar('\n');
    }
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2021/05/30 12:36

    補足を見ての通り、授業の一環です。

    目的は構文解析のできるソフトウェアではなく、**生徒が**構文解析の経験を積むことです。

    lib1.c を使うという想定があります。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.48%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る