C言語でスタック(リスト構造)を使用した逆ポーランド記法のプログラムを作りたいのですが
計算式(例:1234+*+)が入力された場合、どのようにして数字と演算子を区別すればいいのでしょうか?
一応スタック構造の部分は、
#include <stdio.h>
#include <stdlib.h>
/*スタック構造*/
typedef struct stack
{
int max;
int ptr;
int *stk;
} Stack;
/*スタックの確保・初期化*/
int StackAlloc(Stack *s, int max)
{
s->ptr = 0;
if ((s->stk = calloc(max, sizeof(int))) == NULL)
{
s->max = 0;
return (-1);
}
s->max = max;
return (0);
}
/*スタック解放*/
void StackFree(Stack *s)
{
if (s->stk != NULL)
{
free(s->stk);
s->max = s->ptr = 0;
}
}
/*プッシュ*/
int StackPush(Stack *s, int x)
{
if (s->ptr >= s->max)
return (-1);
s->stk[s->ptr++] = x;
return (0);
}
/*ポップ*/
int StackPop(Stack *s, int *x)
{
if (s->ptr <= 0)
return (-1);
*x = s->stk[--s->ptr];
return (0);
}
/*データのピーク*/
int StackPeek(const Stack *s, int *x)
{
if (s->ptr <= 0)
return (-1);
*x = s->stk[s->ptr - 1];
return (0);
}
/*スタックの大きさを返却*/
int StackSize(const Stack *s)
{
return (s->max);
}
/*データを返却*/
int StackNo(const Stack *s)
{
return (s->ptr);
}
/*スタックは空か*/
int StackEmpty(const Stack *s)
{
return (s->ptr <= 0);
}
/*スタックは満杯か*/
int StackFull(const Stack *s)
{
return (s->ptr >= s->max);
}
/*スタックを空にする*/
void StackClear(Stack *s)
{
s->ptr = 0;
}
といった感じで仕上げています。
No.4ベストアンサー
- 回答日時:
つい2週間くらい前に逆ポーランドの処理コードを書きました。
言語はObjective-Cでしたけど。
記憶に新しいので助言します。
まず、逆ポーランドの処理では、数値も演算子もトークン(呼び方は一例)として
扱います。
C言語でしたら、トークンを構造体で表現するのが自然かと思います。
typedef enum {
TOKEN_TYPE_NUM,
TOKEN_TYPE_OPERAND
} token_type;
typedef struct {
token_type type;
int value; // 数値または演算子
} token;
そうすると、トークンは1234+*+の7つあるわけですから、tokenポインタが7つPushされた
スタックを作ります。
あとはルールに従ってPopとPushで処理していけばいいですよね。
> どのようにして数字と演算子を区別すればいいのでしょうか?
もうお分かりかと思いますが、一例を書きます。
token *t;
StackPop(s, &t);
if(t->type == TOKEN_TYPE_NUM){
// t->valueを数値として処理
}
if(t->type == TOKEN_TYPE_OPERAND){
// (char)t->valueを演算子として処理
}
最後に、ほかの方も指摘していますが、質問者様のコードはツリー型のスタックになっていません。
というか、スタック実装は通常リンクリストであってツリーにはしないです。
ツリーを使う処理として、二分探索木なんかが教科書にはよく登場します。
http://ja.wikipedia.org/wiki/2%E5%88%86%E6%8E%A2 …
スタックでは、通常ノードとノードがポインタで連結した構造をとります。
具体的にはこんなコードになるはずです。
http://www.freecprograms.com/lilink.htm
勉強用であればそのままでもいいかもしれませんが、とりあえずポインタのPush/Popが
できるように改造しないとjjk65536案は使えないですね。
No.3
- 回答日時:
>どのようにして数字と演算子を区別すればいいのでしょうか?
入力が文字列であると仮定した場合ですが、一文字目から順に見ていって、普通にswitchかifで比較・処理するのではダメなのでしょうか?
たとえば、
char* input = "1234+*+";
ならforつかって
if (input[i] >= '0' && input[i] <= '9') { 数値の処理 }
else if (input[i] == '*') { 掛け算の処理 }
(以下略)
あるいは
switch (input[i]) {
case '0': case'1': ... case'9': 数値の処理
case '*': 掛け算の処理
(以下略)
}
という感じで比べられます。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
最大スタックサイズを大きくす...
-
Cプログラミングの関数電卓のア...
-
再帰処理を非再帰処理に書き換...
-
逆ポーランド記法
-
printf / sprintf のスタック消...
-
VB.netでDLLを読み込んで実行す...
-
プログラムの規模を表す単位「k...
-
パソコンでインターネット接続...
-
ライン数とステップ数の違いに...
-
VB.Netから、VC++.Net経由でNat...
-
ステップ数について
-
VB6.0で #の意味
-
hdmiはパラレル?シリアル?
-
ブロック長について
-
磁気ディスク装置についての計算
-
MoveNextの処理速度は?
-
ubuntuで デイスク/deb/loopと...
-
磁気ディスクの計算問題です
-
【電気】フリッカー回路ってな...
-
ブラインドタッチって練習し始...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
VB.netでDLLを読み込んで実行す...
-
printf / sprintf のスタック消...
-
最大スタックサイズを大きくす...
-
_CRTIMPの意味は?
-
スタックフレームの消滅
-
スタックの伸張方向
-
エラー?メッセージ
-
スタックとキューの使い所
-
CASLとCASL2の違いについて
-
逆ポーランド記法
-
キューとスタックの問題です、...
-
再帰関数を使うとき、ソフトウ...
-
pthreadのスタックサイズ設定取...
-
再帰処理を非再帰処理に書き換...
-
二分探索木の行きがけ順走査
-
gccでスタックサイズを変更する...
-
スタックのpush/pop動作について
-
スタックを用いて整数配列を入...
-
ゆゆにゃ。
-
スタック領域変更
おすすめ情報