2

代替テキスト

いくつかのグーグル検索の後、私はそれを見つけました！

中置への接頭辞

このアルゴリズムは、末尾再帰ではない方法です。反転された入力文字列は完全にスタックにプッシュされます。

prefixToInfix(stack)
   1) IF stack is not empty
     a. Temp -->pop the stack
     b. IF temp is a operator
       i. Write a opening parenthesis to output
       ii. prefixToInfix(stack)
       iii. Write temp to output
       iv. prefixToInfix(stack)
       v. Write a closing parenthesis to output
    c. ELSE IF temp is a space -->prefixToInfix(stack)
    d. ELSE
       i. Write temp to output
       ii. IF stack.top NOT EQUAL to space -->prefixToInfix(stack)

スタックトップが

F（ABC）

アルゴリズムを入力すると、現在の値である「A」が出力に書き込まれます。

temp = A（言う）

ここで、アルゴリズムに従って出力列に「-」を取得する方法は、次の一時値は「B」であり、最後の再帰呼び出しの後にスタックからポップされました。ダイアグラムが出力をどのように示しているか"（（A-"..。

私が間違った仮定をしているところは？誰かがそれを説明するのに苦労することができますか？

4

1 に答える 1

1

私はあなたの質問をよく理解していません。

スタックがABCである場合F(ABC)、Aをポップし、ブランチdiに入り、Aを出力に書き込み、d.iiに進みます。そして実行しますF(BC)。これにより、最終的にBとCの両方が出力に書き込まれます。

出力を図のように見せたい場合は、スタックをである必要があります* - A B C（すべての要素間のスペースに注意してください！）。

編集：

（余談ですが、これはすべて、説明するよりも簡単に実行できるため、アルゴリズムをプログラムとして記述し、選択したデバッガーで開始することをお勧めします。）

これで、最初のスタック*を（ tempa）に格納し、（bi）を記述(し、残りのスタック（b.ii.）を使用してアルゴリズムを呼び出しました。これにより空白が破棄-され、次のブランチにを格納しtemp、を記述(して、残りのスタックでアルゴリズムを呼び出します。ある時点で、最終的にd.iiになります。出力するAを書き込んだだけで、次のようになります。

((A

残りのスタックは 

_B_C

上にスペースがあり、BとCの間に別のスペースがあります
。スペースを見つけて、もう何もしません。このコントロールブランチが実行され、元の場所であるd.iiに戻ります。-コントロールブランチで。d.iii。で出力するように書き込み、-d.iv。で残りのスタック（_B_C）を使用してアルゴリズムを呼び出し、そこに進み、、、、、および最後のBを)書き込みます。 *C)

どこから来たのかを覚えておいてください。そうすれば、現在の再帰が完了した後、どこにジャンプして戻るかがわかります。

于 2010-12-07T08:11:01.397 に答える