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/10(木)】
- ・メモのコツを教えてください!
- ・CDの保有枚数を教えてください
- ・ホテルを選ぶとき、これだけは譲れない条件TOP3は?
- ・家・車以外で、人生で一番奮発した買い物
- ・人生最悪の忘れ物
- ・【コナン30周年】嘘でしょ!?と思った○○周年を教えて【ハルヒ20周年】
- ・ハマっている「お菓子」を教えて!
- ・最近、いつ泣きましたか?
- ・夏が終わったと感じる瞬間って、どんな時?
- ・10秒目をつむったら…
- ・人生のプチ美学を教えてください!!
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・都道府県穴埋めゲーム
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
c++の勉強方法を教えてくださ...
-
10進数からN進数に変換するプロ...
-
プログラミングの課題がわから...
-
逆コンパイルと逆アセンブルの...
-
Windows Formアプリからコンソ...
-
ArduinoのジャイロモジュールMP...
-
VisualStudioで、コードを印刷...
-
VisualStudio2022でC言語プログ...
-
C言語って古いですか?
-
パソコン
-
今ってプログラミング言語は何...
-
2つほどお聞きしたいことがあり...
-
どうして+3
-
プログラミング言語についてc++...
-
次の記述について
-
UART通信の取説で,left floati...
-
C#でTreeViewのCheckBoxのサイ...
-
プログラムの実行時に'<'でリダ...
-
私は
-
これて逆じゃないですか?
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
VB.netでDLLを読み込んで実行す...
-
最大スタックサイズを大きくす...
-
gccでスタックサイズを変更する...
-
printf / sprintf のスタック消...
-
_CRTIMPの意味は?
-
スタック領域変更
-
Cプログラミングの関数電卓のア...
-
WINAPについて
-
GCCで関数の引数が渡らない
-
H8マイコン スタック領域に...
-
C言語・スタックを使用した逆...
-
スタックのプログラムを作成し...
-
キューとスタックの問題です、...
-
c言語 リストデータ構造 キ...
-
再帰関数を使うとき、ソフトウ...
-
スタックとキューの使い所
-
マス目上の移動のアルゴリズム
-
フレームポインタについて
-
スタックの伸張方向
-
ポインタ版リスト構造によるス...
おすすめ情報