ポインタ版リスト構造によるスタックの実装

質問

C言語を用いてアルゴリズムの勉強をしています。

現在、ポインタ版リスト構造によるスタックを実装し、入力された文字列の中で括弧の整合性を判定するプログラムを作成しているのですが、難航しています。

プログラムの内容は、以下の通りです。

入力：a{z[e(b){j}(p)]w}(j)
結果：整合
入力：a{z[e(b){j}(p)}w](j)
結果：不整合

ですが、所持している参考書の例題プログラムには、スタックに入れる要素が整数値のものしかなく、文字をスタックに入れるところからわかりません。
また、先輩に尋ねたところ、以下のような構造体を使うと良いとアドバイスされました。

typedef struct {
int max;
int num;
List stk;
} Stack;

typedef struct {
Node *head;
Node *crnt;
} List;

typedef struct node {
char data;
struct node *next;
} Node;

先輩には申し訳ないのですが、余計にわからなくなってしまいました。
この構造体を用いてプログラムをかける方、ご指導のほどよろしくお願いします。

回答No.5

noname#208507

> char型に変更してみたのですが、何故かエラーが発生してしまいます。

関数StackAllocは、きちんと構造体のメモリを確保していますか。まさかとは思いますが、第一と第二引数を関数calloc（もしくは関数malloc）に渡して呼び出しているだけ、ではありませんよね。

ポップするとき、結果を引数で受け取るならStackPop(s, &x)のようにxのアドレスを渡すべきですが、プッシュするときはStackPush(s, x)のようにxを値渡しするべきです。それとデータ型に気を付けてください。

先輩さんのアドバイスを活かすなら、私は下のようにします。あとは括弧の対応を確認する方法ですが、これはスタックの使い方をよく考えれば分かるでしょう。

#include <stdlib.h>

#define StackNo(s) ((s)->num)
#define StackSize(s) ((s)->max)

Stack *StackAlloc(int max)
{
Stack *stack = malloc(sizeof(Stack));
if (stack != NULL) {
stack->max = max;
stack->num = 0;
stack->stk.head = stack->stk.crnt = NULL;
}
return stack;
}

int StackPush(Stack *stack, char data)
{
int ng = 0;
Node *next = malloc(sizeof(Node));
if ((next != NULL) && (stack->num < stack->max)) {
next->data = data;
next->next = NULL;
if (stack->stk.head == NULL) {
stack->stk.head = stack->stk.crnt = next;
} else {
stack->stk.crnt->next = next;
stack->stk.crnt = next;
}
stack->num++;
} else {
free(next);
ng = -1;
}
return ng;
}

int StackPop(Stack *stack, char *data)
{
int ng = 0;
Node *prev = stack->stk.head;
Node *crnt = stack->stk.crnt;
if (prev != NULL) {
*data = crnt->data;
if (prev == crnt) {
stack->stk.head = stack->stk.crnt = NULL;
} else {
while (prev->next != crnt) {
prev = prev->next;
}
prev->next = NULL;
stack->stk.crnt = prev;
}
free(crnt);
stack->num--;
} else {
ng = -1;
}
return ng;
}

void StackFree(Stack *stack)
{
char data = '\0';
if (stack != NULL) {
while (StackPop(stack, &data) != -1);
}
free(stack);
}

回答No.4

kmee

C言語では、char は「文字が表現できるサイズの整数」です。
intはcharより大きな整数なので、「intを格納するスタック」にcharを入れることが可能です。
補足にあった実装では、intへのポインタを使っているので、一旦int型の変数に入れて使えば、そのまま流用できます

Stack *s;
char str[] ; /* 文字列 */
int c ;
(略)
c=str[i] ; /*1文字取り出す*/
StackPush(s, &c)
...
StackPop(s, &c)
str[i]=c ; /*1文字戻す*/

それよりも、本来の目的「括弧の対応を確認する」の方は大丈夫ですか?
スタックをどう作るか、等は小さな問題です。

回答No.3

Tacosan

とりあえず「先輩には申し訳ないのですが、余計にわからなくなってしまいました」じゃダメだね. 「どこがどう」わからないのか, 自分で考えないと.

ちなみに「適当な定数」としては, 例えば ( には '(' を使うことを推奨します.

回答No.2

honor

括弧の整合性を確認したいだけならa-zの文字は読み飛ばしてもいいんですよね。
(){}[]に適当な定数を決めて順番にスタックに入れて、対応するものが来たらスタックから出せばいいんじゃないでしょうか。

補足

ご回答ありがとうございます。

> 括弧の整合性を確認したいだけならa-zの文字は読み飛ばしてもいいんですよね。
はい、その通りです。

> (){}[]に適当な定数を決めて順番にスタックに入れて
『適当な定数』というのは初めに定義しておく、ということでしょうか。

回答No.1

noname#208507

> 例題プログラムには、スタックに入れる要素が整数値のものしかなく、

その要素はint型ですよね？
とりあえずスタックについては、int型をchar型に変えればよいだけでは。

補足

ご指摘ありがとうございます。
char型に変更してみたのですが、何故かエラーが発生してしまいます。

以下、main関数のソースコードです。
※現在、完成しているプログラムは『整数値をプッシュ／ポップする』ところまでです。

/**/

int main(void)
{
Stack *s;

if ((s = StackAlloc(sizeof(int), 100)) == NULL)
{
puts("スタックの確保に失敗しました。");
return (1);
}

while (1)
{
int m;
double x;

printf("現在のデータ数：%d/%d\n", StackNo(s), StackSize(s));
printf("(1) プッシュ　(2) ポップ　(0) 終了：");
scanf("%d", &m);

if (m == 0) break;

switch (m)
{
case 1:
printf("データ：");
scanf("%d", &x);

if (StackPush(s, &x) == -1)
puts("スタックへのプッシュに失敗しました。");
break;

case 2:
if (StackPop(s, &x) == -1)
puts("ポップできません。");
else
printf("ポップしたデータは%dです。\n", x);
break;
}
}

StackFree(s);

return (0);
}