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で質問しましょう!
似たような質問が見つかりました
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- C言語・C++・C# プログラムが書けません。 4 2023/01/22 22:57
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# C言語初心者 構造体 課題について 2 2023/03/10 19:48
- C言語・C++・C# C言語 3 2022/10/04 15:07
- C言語・C++・C# C言語初心者 構造体 課題について 1 2023/03/10 19:30
- C言語・C++・C# カードシャッフルのブログラムを使ってc言語でブラックジャックをしたい 2 2022/04/12 15:13
- C言語・C++・C# このプログラミングの問題を教えて欲しいです。 キーボードから整数kを入力し、kが配列aの中に何個存在 2 2022/12/19 22:50
- C言語・C++・C# C言語(構造体) 3 2022/07/05 20:08
- C言語・C++・C# このプログラミングの問題を教えてほしいです。 キーボードからデータ数nとn個のデータを入力し、平均値 3 2022/12/19 22:51
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
VB.netでDLLを読み込んで実行す...
-
スタックフレームの消滅
-
_CRTIMPの意味は?
-
GCCで関数の引数が渡らない
-
printf / sprintf のスタック消...
-
H8マイコン スタック領域に...
-
リストを使った逆ポーランド記...
-
ubuntuで デイスク/deb/loopと...
-
ライン数とステップ数の違いに...
-
プログラムの規模を表す単位「k...
-
パソコンでインターネット接続...
-
hdmiはパラレル?シリアル?
-
タイピング練習ソフト
-
15パズルゲームについて
-
SP領域とはなんですか?
-
「ByRef引数の型が一致しません...
-
Ic-PcAn はどこのこと?
-
社内LANのネットワークトラフィ...
-
固定電話機のパソコンとの連動
-
タイピングソフトおすすめは?
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
VB.netでDLLを読み込んで実行す...
-
最大スタックサイズを大きくす...
-
printf / sprintf のスタック消...
-
エラー?メッセージ
-
スタック領域変更
-
gccでスタックサイズを変更する...
-
H8マイコン スタック領域に...
-
スタックを用いて整数配列を入...
-
マス目上の移動のアルゴリズム
-
関数のプロローグとエピローグ...
-
GCCで関数の引数が渡らない
-
スタック C言語
-
CASLとCASL2の違いについて
-
pthreadのスタックサイズ設定取...
-
_CRTIMPの意味は?
-
VC++でプログラムから現在のス...
-
ポーランド記法、逆ポーランド...
-
スタックの伸張方向
-
c言語 リストデータ構造 キ...
-
再帰関数を使うとき、ソフトウ...
おすすめ情報