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を探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
- ・ゆるやかでぃべーと タイムマシンを破壊すべきか。
- ・歩いた自慢大会
- ・許せない心理テスト
- ・字面がカッコいい英単語
- ・これ何て呼びますか Part2
- ・人生で一番思い出に残ってる靴
- ・ゆるやかでぃべーと すべての高校生はアルバイトをするべきだ。
- ・初めて自分の家と他人の家が違う、と意識した時
- ・単二電池
- ・チョコミントアイス
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
VB.netでDLLを読み込んで実行す...
-
_CRTIMPの意味は?
-
エラー?メッセージ
-
最大スタックサイズを大きくす...
-
プログラムの規模を表す単位「k...
-
ubuntuで デイスク/deb/loopと...
-
パソコンでインターネット接続...
-
ライン数とステップ数の違いに...
-
hdmiはパラレル?シリアル?
-
7bitのデータ列に1bitのパリテ...
-
ホストアドレスの0とは
-
磁気ディスクの計算問題です
-
L2スイッチの管理VLANに...
-
ブラインドタッチって練習し始...
-
固有パリティについて質問です
-
ステップ数について
-
同じサブネットに属するIPアドレス
-
MoveNextの処理速度は?
-
ブロック長について
-
シェルスクリプトについて
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
VB.netでDLLを読み込んで実行す...
-
printf / sprintf のスタック消...
-
最大スタックサイズを大きくす...
-
_CRTIMPの意味は?
-
スタックフレームの消滅
-
スタックの伸張方向
-
エラー?メッセージ
-
スタックとキューの使い所
-
CASLとCASL2の違いについて
-
逆ポーランド記法
-
キューとスタックの問題です、...
-
再帰関数を使うとき、ソフトウ...
-
pthreadのスタックサイズ設定取...
-
再帰処理を非再帰処理に書き換...
-
二分探索木の行きがけ順走査
-
gccでスタックサイズを変更する...
-
スタックのpush/pop動作について
-
スタックを用いて整数配列を入...
-
ゆゆにゃ。
-
スタック領域変更
おすすめ情報