Ｃ言語・スタックを使用した逆ポーランド記法について

質問

Ｃ言語でスタック（リスト構造）を使用した逆ポーランド記法のプログラムを作りたいのですが
計算式（例：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

jjk65536 · ベストアンサー

つい２週間くらい前に逆ポーランドの処理コードを書きました。
言語は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%E7%B4%A2%E6%9C%A8

スタックでは、通常ノードとノードがポインタで連結した構造をとります。
具体的にはこんなコードになるはずです。
http://www.freecprograms.com/lilink.htm

勉強用であればそのままでもいいかもしれませんが、とりあえずポインタのPush/Popが
できるように改造しないとjjk65536案は使えないですね。

回答No.5

jjk65536

No.4です。
ツリーなんてどこにも書いてないですね。
大変失礼しました。
お恥ずかしい。

回答No.3

LOHA

＞どのようにして数字と演算子を区別すればいいのでしょうか？
入力が文字列であると仮定した場合ですが、一文字目から順に見ていって、普通に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 '*': 掛け算の処理
　(以下略）
}
という感じで比べられます。

回答No.2

asuncion

＞スタック（リスト構造）を使用した

と書いてありますが、構造体が自己参照型になってませんね。
リスト構造を使ったことになってないんじゃないですか？

回答No.1

Tacosan

その例の「1234+*+」は何を意味するのですか?