Ｃ言語で、再帰呼び出しを使用せずに、文字列"(12 + 3) * (

Ｃ言語で、再帰呼び出しを使用せずに、文字列"(12 + 3) * ( 3 * (4 + 5 ))"を、優先順位が低い順に二分木に入れる関数を作成したいのですが・・・。
char str[15] = ""(12 + 3) * ( 3 * (4 + 5 ))";なら
char n[100];に
n[0] = '*'
n[1] = '+'
n[2] = '*'
n[3] = 12

n[4] = 3
n[5] = 3
n[6] = '+'
n[7] = \0

n[8] = \0

n[9] = \0

n[10] = \0
n[11] = \0
n[12] = \0
n[13] = 4

n[14] = 5

（n[15] 以降は\0が格納されています。）
というように入れたいのですが関数からその関数を呼び出す再帰を使わずに作成する方法がわかりません。
再帰を使用しなければかなり処理が複雑になるような気がしますがどなたか詳しい方よろしくお願いします。

言語はＣ言語です。

No.4 ベストアンサー 回答者： vaguechat 回答日時： 2010/05/17 01:19

耐エラー性はたぶん低い。

0と'\0'は区別できないから正当な数値は1から255。
ヒープ構造というか木構造の子要素が共に0なら数値。

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
typedef unsigned char uchar;
typedef enum{OPERATOR,OPERAND,END}Type;
typedef struct{
Type type;
uchar value;
}Token;
int map(uchar c)
{
static uchar key[]="+*()";
int i;
for(i=0;i<4;i++)if(key[i]==c)return i;
fprintf(stderr,"illegal char: %c\n",c);
exit(0);
}
int left(Token token)
{
static int left[]={2,4,0,4};
return token.type==OPERATOR?left[map(token.value)]:token.type==OPERAND?4:0;
}
int right(Token token)
{
static int right[]={1,3,5,0};
return token.type==OPERATOR?right[map(token.value)]:token.type==OPERAND?5:0;
}
void construct(Token rpn[],int next,char n[])
{
int i,p=0;
for(i=next;--i>=0;){
n[p]=rpn[i].value;
if(rpn[i].type==OPERATOR)p=2*p+2;
else if(p%2)p=p/2-1;
else p--;
}
}
void parse(char*s,char n[])
{
Token input,stack[128],rpn[128];
int need_input=1,top=0,next=0;
stack[top].type=END;
while(1){
if(need_input){
if(isspace(*s)){
s++;
continue;
}
if(*s=='\0'){
input.type=END;
}else if(isdigit(*s)){
char*t=s;
int v;
while(isdigit(*++t));
sscanf(s,"%d",&v);
if(v<=0||v>255){
fprintf(stderr,"out of range: %d\n",v);
exit(0);
}
s=t-1;
input.type=OPERAND;
input.value=v;
}else{
map(*s);
input.type=OPERATOR;
input.value=*s;
}
s++;
}
if(stack[top].type==END&&input.type==END)break;
if(left(stack[top])>right(input)){
Token t;
do{
t=stack[top--];
if(t.type!=OPERATOR||(t.value!='('&&t.value!=')'))rpn[next++]=t;
}while(top>=0&&left(stack[top])>=right(t));
if(top<0){
fprintf(stderr,"syntax error\n");
exit(0);
}
need_input=0;
}else{
stack[++top]=input;
need_input=input.type!=END;
}
}
construct(rpn,next,n);
}
int main(void)
{
int i;
char str[]="(12 + 3) * ( 3 * (4 + 5 ))";
char n[100];
for(i=0;i<100;i++)n[i]=0;
parse(str,n);
for(i=0;i<100;i++){
printf(n[i]==0?" \\0":i>48||n[2*i+1]==0&&n[2*i+2]==0?"%3d":" %c ",(uchar)n[i]);
printf(i%10==9?"\n":" ");
}
return 0;
}

この回答へのお礼

ありがとうございます！参考になりました！

お礼日時：2010/05/19 19:36

No.3 回答者： Tacosan 回答日時： 2010/05/16 23:13

あくまで「原理的には」ですが, スタックを使えばパースは可能. yacc や bison がやってるのと同じことですな. あるいは「演算子順位文法」といってもいいかも.

とはいえ「なぜ再帰を避けてわざわざ面倒な方向に走るのか」が見えないし, 「こんなわけのわからない出力を作る」理由も不明. 素直に再帰を使って普通に二分木を作ろうよ.

この回答へのお礼

ありがとうございます！参考になりました！

お礼日時：2010/05/19 19:36

No.2 回答者： asuncion 回答日時： 2010/05/15 08:33

＞n[3] = 12345

再帰呼び出し以前の話として、
char型に12345を入れようとすると
オーバーフローすることに気づいてください。

この回答への補足

255以上ですのでたしかにオーバーフローしますね。それでは255までの範囲内でよろしいので、二分木にいれる方法をおしえていただけますか？

補足日時：2010/05/16 08:56

No.1 回答者： asuncion 回答日時： 2010/05/15 07:58

念のためにお聞きします。

仮に、当該の数式が
(12345 + 3) * ( 3 * (4 + 5 ))
であるとすると、どういう結果をお望みですか？

この回答への補足

n[0] = '*'
n[1] = '+'
n[2] = '*'
n[3] = 12345
n[4] = 3
n[5] = 3
n[6] = '+'
n[7] = \0
n[8] = \0
n[9] = \0
n[10] = \0
n[11] = \0
n[12] = \0
n[13] = 4
n[14] = 5
です。

補足日時：2010/05/15 08:28