プログラマ専用SNS ミクプラ

逆ポーランドで悩んでいます。
10 + 20 *(30-40) $
と記入して10 20 30 40 - * +　と出力するようにしたいです。

トークンとトークンの間に空白があったりなかったりしています。

どちらにも対応する必要がありますか？

回答ありがとうございます。
すいません、空白はなくてもいいです。

データ構造を考え直す方がいいのではないでしょうか。

演算子の優先順位を考慮に入れたキュー（待ち行列）を用意するとか。

10+20*30-40$

出力:10 +20*30-40

出力:10 20 *30-40
配列：+

出力:10 20 30-40
配列:+ *

出力:10 20 30 -40
配列:+ *

出力:10 20 30 * 40
配列:+ -

出力:10 20 30 * 40 - +


こういうことですよね。
入力した値を数字か演算子か判断し、数字なら出力する。
演算子なら配列などに格納する。
次が数字なら出力して、演算子が続くならエラーで返す。
数字をはさみ演算子が来る場合、配列の演算子と比較し、＊や/なら配列から出力し、+や-は格納していけばいいと。、

各段階の「出力」と「配列」が何を意味しているか、全くわかりません。

なお、65250の式をRPNで表わすと

10 20 30 * + 40 -

となります。

10に、20と30を掛けたものを足して、40を引く、
と読みます。


RPNへの変換結果が誤っていたので修正しました。

NIDA です。
いつも、お世話になっております。

2 分探索木をつかった方法をちょっと思いついたので、
下記します。

※ 実際に、プログラムを書いて試したわけではありません。

2, 3 の簡単な数式で確認しただけなので、間違ってるかも
しれません。

-------------------------------
(1). 各要素に、下記のような値をつけます。

数字 には、 値 1。
'*' と '/' には、値 2。
'+' と '-' には、値 3。

(2). カッコ内は、別に独立したツリーを作成して、
全体として数字(値 1)として扱う。

(3). 各要素のツリーへのぶら下げ方法は下記のとおり。

(比較対象)
比較相手の右側に子供がいれば、その子供と比較する。
比較相手の右側に子供がいない場合は、その相手と
比較する。

(比較方法)
比較相手の値と自分の値を比較して自分の値のほうが
大きい場合、または相手と自分の値が同じ場合は、
相手の右側の子供になる。
※ 比較相手の右側に子供は、いないはず。

もし相手の値より、自分の値が小さい場合は、相手の左側の
子供になる。ただし、すでに左側に子供がいる場合は、
その子供と比較する。

-------------------------------

これでテストすると、<<10+20*(30-40)>>のツリーは、
下記のようになります。

■ ツリー 1 つ目。

'10'(値 1)
|
+----+----+
| |
'+'(値 3)
|
+----+----+
| |
'20'(値 1)
|
+----+----+
| |
'*'(値 2)
|
+----+----+
| |
'(30-40)'(値 1)


■ ツリー 2 つ目。('30-40' の部分のツリー。)


'30'(値 1)
|
+----+----+
| |
'-'(値 3)
|
+----+----+
| |
'40'(値 1)

-----------------------------------------
★ ツリーの 1 つめを「帰りがけ」で、拾っていくと、
'10' '20' '(30-40)の部分' '*' '+' となります。

2 つ目のツリー("(30-40" の部分)を同様に拾っていくと、
'30' '40' '-' となります。

この 2 つを合わせると、

'10' '20' '30' '40' '-' '*' '+' の順となりますが、
駄目でしょうか ?

■ ちなみに、<<10+(30-40)*20>>だと、
'10' '30' '40' '-' '20' '*' '+' の順に、


'10'(値 1)
|
+----+----+
| |
'+'(値 3)
|
+----+----+
| |
'(30-40)'(値 1)
|
+----+----+
| |
'*'(値 2)
|
+----+----+
| |
'20'(値 1)



<<10+20*30-40>> だと、
'10' '20' '30' '*' '+' '40' '-' の順になります。


'10'(値 1)
|
+----+----+
| |
'+'(値 3)
|
+----+-----------------+
| |
'20'(値 1) '-'(値 3)
| |
+----+----+ +----+----+
| | | |
'*'(値 2) '40'(値 1)
|
+----+----+
| |
'30'(値 1)

以上

二人ともありがとうございました。
一応できました。

void expression()
{
char enzanshi;
term();
while(token.type==PLUS ||token.type ==MINUS)
{
enzanshi=token.str[0];
scan();
T();
printf("%c\n",enzanshi);
}
}
void term()
{
char enzanshi;
factor();
while(token.type==ASTERISK || token.type ==SLASH)
{
enzanshi=token.str[0];
scan();
factor();
printf("%c\n",enzanshi);
}
}
void factor()
{
if(token.type == LPAREN)
{
scan();
expression();
if(token.type!=RPAREN)
error(NULL);
scan();
return;
}
if(token.type == NUMB)
{
scan();
return;
}
error(NULL);
}

木構造も試しておきたいとおもいます。