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

###発生している問題・エラーメッセージ
中置記法の順に代入文の文字列を入力してください: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;

}

ItoTomonori

2016/04/22 17:10 編集

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

awellbottom

2016/04/23 02:21

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

行動規範の内容に同意します

回答2件

こんにちは。

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

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を直接修正していますので、このプログラムで取り扱えるスタックはhead１つだけですね。であれば、ppパラメータはやめにして全てheadをアクセスすれば可読性が大きく改善しますよ。

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

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

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

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

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

投稿2016/04/24 15:39

編集2016/04/24 15:56