スタック、配列、プログラミング言語または実装を使用せずに接頭辞式に接頭辞式を変換する方法

Question

スタック、配列、プログラミング言語または実装を使用せずに中置式を接頭辞式に変換するためのアルゴリズムまたは手順を教えてください。ノンCS学生のための単純な人間のアルゴリズム。

誰もがより良いアルゴリズムまたは手順を使用している場合は指定しても、私のためにそれをしてください解決してみてください... :)

（5 + 15/3）^ 2-（8 * 3/3 * 4/5×32/5 + 42）×（3×3/3×5/4）

Answer 1

「単純な人間のアルゴリズム」はスタックを使用します。たとえば、Shunting Yardを考えてみましょう。あなたは紙と鉛筆でそれを行うことができます。 「出力キュー」は単に出力するソリューションです。 「スタック」はちょうど保持場所です。だから、 "スタックに押し込む"と言うとき、その値を他の値のスタックの最上部に置くことを想像してください。それが "スタックからポップ"と言えば、上にあったものを取り除くことを想像してください。

鉛筆と紙で印刷する場合は、ページの下部にある2行の出力キューを用意してください。スタックのページの右側に列を作成します。それが「出力キューに書き込む」と書かれていれば、その値を答え線の次の値として書いてください。

最初に「スタックにプッシュ」と書かれている場合は、その値をスタック列の最下部に書き込んでください。他に何かを押す必要がある場合は、その値よりも上に書いてください。 「スタックからポップする」と言うと、スタックの列から一番上の値を消去し、スペースを解放します。

これは本当に手作業で最も簡単で信頼できる方法です。

私はあなたの例の最初のビットをデモンストレーションに使用します。 (5+15/3)^2を後置に変換したいとしましょう。 Shunting Yardの記事の手順を使用します。

出力キューは空でスタックもスタックです。最初のトークンは(です。指示はスタックに押し込むように指示します。我々が持っているので：

output queue: 
stack: (

を次のトークンが5であることは、出力キューに行く：

output queue: 5 
stack: (

次は+です。スタックの最上部にはトークンがありませんので、我々はそれをプッシュする：

output queue: 5 
stack: (+ 

次は15です。それは次の/ある出力キュー

output queue: 5 15 
stack: (+ 

に行きます。これは演算子であり、スタックに演算子がありますが、/は+より高い優先順位を持ちます。だから、ルールに基づいて、我々はスタック上に/をプッシュ：

output queue 5 15 
stack: (+/

次は3です。これは、出力キューに行く：

output queue 5 15 3 
stack: (+/

次は)です。ルールは、開かれた括弧に到達するまで、スタックから演算子をポップし始めると言っています。あるいは、スタックを空にして開いた括弧がない場合、括弧が一致しません。とにかく、スタックをポップし、出力キューに追加：

output queue: 5 15 3/+ 
stack: <empty> 

次のトークンが^です。スタックに演算子がないので、それを押します。

output queue: 5 15 3/+ 
stack:^

最後に、2があります。これは、出力キューに行く：

output queue: 5 15 3/+ 2 
stack:^

そして、我々は、文字列の末尾にしているので、我々はすべての演算子をポップし、出力キュー上に置く：

output queue: 5 15 3/+ 2^

そして、それはPostfixの(5 + 15/3)^2の表現。

唯一の難しい部分は、演算子の優先権を取得することです。基本的には、指数関数が最も高い。乗算と除算を同じ優先順位で行い、次に同じ優先順位で加算と減算を行います。それらが唯一の演算子であれば、覚えやすいです。そうでなければ、おそらく演算子の優先順位のテーブルが便利なので、アルゴリズムを操作しているときに参照することができます。単項マイナス（すなわち、5 + -1）には特殊なケースが必要です。しかし、実際にはそれはすべてです。