幼稚園時代「何組」でしたか?

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;
}
といった感じで仕上げています。

A 回答 (5件)

つい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案は使えないですね。
    • good
    • 0

No.4です。


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

>どのようにして数字と演算子を区別すればいいのでしょうか?


入力が文字列であると仮定した場合ですが、一文字目から順に見ていって、普通に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 '*': 掛け算の処理
 (以下略)
}
という感じで比べられます。
    • good
    • 0

>スタック(リスト構造)を使用した



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

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

    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!