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

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

ただいまの
回答率

90.50%

  • C

    3806questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • ポインタ

    112questions

    ポインタはアドレスを用いてメモリに格納された値を"参照する"変数です。

  • コンパイル

    65questions

    コンパイルとは、プログラミング言語のテキストソース(ソースコード)をコンピュータ上で実行可能な形式(オブジェクトコード)に変換することをいいます

  • リストボックス

    14questions

    ユーザーがリストから1つ以上のアイテムを選択できるようにするGUI要素です。

Cでスタックを用いて逆ポーランド記法という順で出力し直すプログラムの修正

受付中

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 2,757

awellbottom

score 8

前提・実現したいこと

被演算数(1文字分の英字)、演算子、および括弧(左括弧「(」と右括弧「)」) のトークンで構成された中置記法の算術式を読み込み、 スタックを用いて逆ポーランド記法の式を出力する Cのプログラムを作成する。

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

中置記法の順に代入文の文字列を入力してください:A=B
s[0]:A
s[1]:=
s[2]:B
prior(s[0]):5
prior(s[1]):0
prior(s[2]):5
p[0]:B
p[1]:B
p[2]:B
p[]にうまく文字がはいらない

'''

include<stdio.h>

include<stdlib.h>

include<string.h>

define TRUE 1

define FALSE 0

define SUCCESS 1 /* 成功 */

define FAILURE 0 /* 失敗 */

typedef char data_type; /*char型をdata_type型に置き換える */

typedef struct node_tag {
 data_type data; 
 struct node_tag *next;     /* 後続ノードへのポインタ */
} node_type;                /* ノードの型 */

 node_type *head; /* スタックの先頭へのポインタ (変数宣言)*/

void initialize(node_type **pp)    /* スタックの初期化 */
{
 *pp = NULL;              /* スタックは空(先頭ノードなし) */
}

/* ノードを後ろに付け加える*/

node_type* new_node(data_type data, node_type** head) {
  node_type* n = malloc(sizeof(data_type));
  node_type* p;
  n->data = data;
  n->next = NULL;
  if (*head == NULL) {
    *head = n;
    return n;
  }
  p = *head;
  while(1) {
    if (p->next == NULL) {
      p->next = n;
      break;
    }
    p = p->next;
  }
  return n;
}

//末尾のノードの文字を出力する
data_type last_node(node_type **pp)
{
 node_type *temp=*pp;
 if (*pp == NULL) return 0;
 while (1) {
   if (temp->next == NULL) {
     break;
   }
   temp = temp->next;
 } 
 return(temp->data);
}

int is_empty(node_type *p) {        /* 空スタックのとき真、  そうでないならば偽を返す */
 if (p == NULL) return TRUE;        /* 空スタックのとき */
 else return FALSE;                 /* 空スタックでないとき */
}

//スタックの先頭ノードの削除
int pop(node_type **pp)
{
 node_type *temp;
 if (*pp != NULL) {
 temp = (*pp)->next;
 free(*pp); /* メモリの解放 */
 *pp = temp;
 return SUCCESS;
 }
 else return FAILURE;
}

//スタックの先頭へのノードの挿入
int push(node_type **pp, data_type x)
{
  node_type *temp;
  temp = new_node(x, pp); 
  if (temp == NULL) return FAILURE;
  *pp = temp;
  return SUCCESS;
}

//文字の優先順位を出力する
int prior(data_type s){
  if(s=='A' || s== 'B' ||s== 'C' ||s== 'D' ||s== 'E' ||s== 'F' || s=='G')
    return 5;
  if(s=='=')
    return 0;
  if(s=='(')
    return 4;
  if(s==')')
    return 1;
  if(s=='+'||'-')
    return 2;
  if (s=='*'||s=='/')
    return 3;
}

//スタックの先頭のデータの取得
data_type top(node_type *p)
{
 if (p == NULL) /* 空スタックのとき */
   return   ('\0'); 
 else /* 空スタックでないとき */
 return p->data; /* スタックの先頭のデータを返す */
}

int main(void){
  int n=0,i=0,j=0;
  data_type s[50],p[50];

  printf("中置記法の順に代入文の文字列を入力してください:");
  scanf("%s",s);
  n = strlen(s);

  for(i=0;i<n;i++){
    printf("s[%d]:%c\n",i,s[i]);
  }
  initialize(&head);
  //優先順位の出力(優先順位がついているかの確認用)
  for(i=0;i<n;i++){
    new_node(s[i],&head);
    printf("prior(s[%d]):%d\n",i,prior(s[i]));
    }

  for(i=1;i<n;i++){
    while(prior(last_node(&head))>=prior(s[i]) && is_empty(head)==FAILURE){
      //新たに読み取った文字の方が、スタック最上部の文字より優先度が低ければ、スタックをポップしてそれを読み取る。
      p[j]=last_node(&head);
      pop(&head);
      j++; 
    }      

    //スタックの最上部の文字より新たに読み取った文字の優先順位が高ければ、スタックに積む
    if(prior(last_node(&head))<prior(s[i])){
      push(&head,s[i]);
    }
  }

  //逆ポーランド記法の順に出力する  
  for(i=0;i<j;i++){
    printf("p[%d]:%c\n",i,p[i]);
    }

  return 0;

}

```

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

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

  • ItoTomonori

    2016/04/23 02:01 編集

    すいませんが、まずは、コード部分を、コードブロック ``` で囲んでいただけませんでしょうか? あと、これは学校かなにかの課題?でしょうかね?ご自身で解決する必要がある事であれば、どこまで、ご自身で解析できたのかも、記載願います。 あと、うるさくてすいません、マルチポストですね、、、前のスレッドで継続して、解決に向かわれた方がよいのでは???

    キャンセル

  • awellbottom

    2016/04/23 11:21

    コードブロックというものがあるのですね。 ご指摘ありがとうございます。

    キャンセル

  • 退会済みユーザー

    2016/04/23 22:31

    こちらの質問が他のユーザから「やってほしいことだけを記載した丸投げの質問」という指摘を受けました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

回答 2

0

"c" 逆ポーランド記法
で google 検索するとよいです。

そんななかから1つ紹介します。

 # 質問文のコードを変更してみようとしましたが、時間がかかりそうなので諦めました。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

0

こんにちは。

解析に軽くトライしてみましたが、う~ん、複雑すぎてギブアップです。

push()から呼び出したnew_node()でpush処理を実行されているようですが、push(a)->push(b)->pop()->pop()とした時、b, aの順序でちゃんとpop()されるでしょうか?

pop()はリストを追跡してないですがnew_node()はリストを追跡しているようなのでスタックではなくキュー(待ち行列)になっているような印象を受けます。コメントも「ノードを後ろに付け加える」となってますし。push()のコメント「スタックの先頭へのノードの挿入」と矛盾している印象です。

ですので、どうもpush()/pop()が結構大きくバグっているような気がします。
逆ポーランドの前に、まずpush(), pop()をきちんと動かすことをお勧めします。
例えば、push(a), push(b), pop(), pop()してちゃんとb, aの順序で読み出せることのテストです。
その時、is_empty()もテストしましょう。


【余談ですが】
すいません、厳しいことを言います。ソース、なかなか読みにくいです。
回答がほとんどつかないのはそれが原因と思います。読みにくいプログラムを読むのは本当にたいへんなのです。

さて、インデントが1文字や2文字と言うのは初めてみました。インデントの数を場所によって変えるのはよろしくないです。また、1文字はいくらなんでも少なすぎます。最低2文字以上つけましょう。私が一番良くみるインデント量は4文字です。(2文字のソース、8文字のソースも時々見ます。)
変数名は意味のある名前をつけましょう。nとかpとかppとかではawellbottomさんの意図を読み取れません。

push/popの呼び出し回数を同じになるようにしましょう。回数がアンバランスな時、そこにバグが潜む可能性が高いです。

push()から呼び出されているnew_node()でheadを直接修正していますので、このプログラムで取り扱えるスタックはhead1つだけですね。であれば、ppパラメータはやめにして全てheadをアクセスすれば可読性が大きく改善しますよ。

headをパラメータとすることで複数のスタックを使えるようなプログラムを目指すことはたいへん好ましいことです。ですが、そのようなプログラムはデバッグの難易度も高くなりますし、可読性が落ちやすいので変数名の付け方等、可読性への配慮をより多くしないといけません。
自力でのデバッグを諦めるような時は、諦める前に抽象化を断念してデバッグすることをお勧めします。
それでもダメな時に初めて他の人に聞くと、抽象化されていない分把握しやすいプログラムになっていますので、他の人も回答しやすくなります。

最後に、initialize()のような1行関数は、他の人にデバッグを依頼する場合は、障害になります。
head=NULL;と書いてあればその場で把握できるのに、initialize(&head);と書かれているとinitialize()関数が何か悪さしてないか確認するために、ソースの上の方を見に行かないといけません。しかも、バグりやすい2重ポインタです。本当に間違ってないのか確認するために、デバッグ文を仕込む必要もあるかも知れません。なかなか痛いです。


【オブジェクト指向のススメ】
C言語で、複数のスタックを同時に使えるようにするためには、headをパラメータとして一々渡す必要があり、しかも、関数側でポインタの変更が必要なため、2重ポインタを使う必要が有ります。どうしても可読性/メンテナンス性が低下しやすいです。

しかし、C++言語のオブジェクト指向を使えば、C言語の性能をほとんど落とすことなく、必要な変数群とそれを操作する関数群をスタック・クラスとしてひとまとめにできます。一々headをパラメータとして渡すことなくスマート(2重ポインタなど使わず)にアクセスでき、しかも、複数のスタック実体を作れます。本当に便利ですよ。

汎用性のあるプログラムを開発するよう努力されているようですので、ある程度C言語を使いこなせるようになったら、C++言語も検討されることをお勧めします。

投稿

編集

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

関連した質問

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

  • C

    3806questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • ポインタ

    112questions

    ポインタはアドレスを用いてメモリに格納された値を"参照する"変数です。

  • コンパイル

    65questions

    コンパイルとは、プログラミング言語のテキストソース(ソースコード)をコンピュータ上で実行可能な形式(オブジェクトコード)に変換することをいいます

  • リストボックス

    14questions

    ユーザーがリストから1つ以上のアイテムを選択できるようにするGUI要素です。