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;
先輩には申し訳ないのですが、余計にわからなくなってしまいました。
この構造体を用いてプログラムをかける方、ご指導のほどよろしくお願いします。
A 回答 (5件)
- 最新から表示
- 回答順に表示
No.5
- 回答日時:
> 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
- 回答日時:
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
- 回答日時:
とりあえず「先輩には申し訳ないのですが、余計にわからなくなってしまいました」じゃダメだね. 「どこがどう」わからないのか, 自分で考えないと.
ちなみに「適当な定数」としては, 例えば ( には '(' を使うことを推奨します.
No.1
- 回答日時:
> 例題プログラムには、スタックに入れる要素が整数値のものしかなく、
その要素は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);
}
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・14歳の自分に衝撃の事実を告げてください
- ・架空の映画のネタバレレビュー
- ・「お昼の放送」の思い出
- ・昨日見た夢を教えて下さい
- ・【お題】絵本のタイトル
- ・【大喜利】世界最古のコンビニについて知ってる事を教えてください【投稿~10/10(木)】
- ・メモのコツを教えてください!
- ・CDの保有枚数を教えてください
- ・ホテルを選ぶとき、これだけは譲れない条件TOP3は?
- ・家・車以外で、人生で一番奮発した買い物
- ・人生最悪の忘れ物
- ・【コナン30周年】嘘でしょ!?と思った○○周年を教えて【ハルヒ20周年】
- ・ハマっている「お菓子」を教えて!
- ・最近、いつ泣きましたか?
- ・夏が終わったと感じる瞬間って、どんな時?
- ・10秒目をつむったら…
- ・人生のプチ美学を教えてください!!
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・都道府県穴埋めゲーム
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
gccでスタックサイズを変更する...
-
関数のプロローグとエピローグ...
-
キューとスタックの問題です、...
-
pthreadのスタックサイズ設定取...
-
二分探索木の行きがけ順走査
-
cloneのスタック管理
-
hdmiはパラレル?シリアル?
-
パソコンでインターネット接続...
-
ubuntuで デイスク/deb/loopと...
-
クロック周波数の計算問題について
-
テンキーで入力時、指の位置
-
第一級陸上特殊無線技士
-
ライン数とステップ数の違いに...
-
プログラムの規模を表す単位「k...
-
線形符号の生成行列、検査行列...
-
AutoCAD LTの中古。
-
TCPではなく、UDPが音声や動画...
-
スイッチの通信量計測
-
RAID 5 のパリティ生成のタイミ...
-
if(($j+$i)%7 == 0){ の0の意味...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
VB.netでDLLを読み込んで実行す...
-
最大スタックサイズを大きくす...
-
gccでスタックサイズを変更する...
-
printf / sprintf のスタック消...
-
_CRTIMPの意味は?
-
Cプログラミングの関数電卓のア...
-
スタック領域変更
-
WINAPについて
-
GCCで関数の引数が渡らない
-
H8マイコン スタック領域に...
-
スタックのプログラムを作成し...
-
C言語・スタックを使用した逆...
-
キューとスタックの問題です、...
-
再帰関数を使うとき、ソフトウ...
-
c言語 リストデータ構造 キ...
-
スタックとキューの使い所
-
マス目上の移動のアルゴリズム
-
逆ポーランド記法
-
スタックの伸張方向
-
ポインタ版リスト構造によるス...
おすすめ情報