逆ポーランド記法：ホットドッグを調理する方法は？

アプリケーション開発の分野のアマチュアである私は、逆ポーランド記法のアルゴリズム、またはより正確にはスタックを準備するアルゴリズムを理解するのに苦労しました。 インターネット上の記事もほとんど役に立たなかった。



それはすべて、自分のプロジェクト用に簡単なインタープリターを作成し始めたことから始まりました。 複雑な式を解決するために、2つのアルゴリズムから選択することができました：再帰降下と逆ポーランド記法。 問題（または名前自体）を解決するための明白な単純さとアプローチにより、後者は研究の対象になることができました。



2件の記事がこのケースを助けました。 それらの1つはWikipediaにあり、2つ目はHabrの素晴らしいユーザーであるGORKOFFによって書かれており、文字通りすべてを「指で」説明しました。



しかし、最後まで私はまだその重要な質問を理解していませんでした：スタックを構築する方法？



私は茂みの周りをもうbeatりません。順番に始めましょう。 演算とオペランドを持つ特定の配列があり、次の式が記述されていると想像してください： 5 * 2 + 10 。 この式を、逆ポーランド記法のアルゴリズムを「食べる」形式に変換します。 これを行うには、操作のスタックと出力配列が必要です。 次に、操作に優先順位を付けることが重要です。 これは、たとえば、加算よりも乗算を優先するために、数学演算の順序を正しく分布させるために必要です。



高優先度（1）：ここでは、数学の法則に従って、乗算と除算を行います。

低優先度（2）：加算と減算がここに到達します。



優先順位を決定したら、建設自体に移りましょう。 始める前に、私は何かを説明しなければなりません：

すべての数値はオペランドです。 それらは常に出力配列に書き込まれます。 加算、減算などの符号は演算です。 ただし、それらは操作のスタックと出力配列の両方に存在できます。 どこに行くかは、スタックの最後に依存します。 左から右に順番に進みます。



「5」と読みます。

オペランド、出力配列に入れます。

5を出力配列に追加します。

出口の配列：5。

操作のスタック：空。



「*」を読みます。

操作。 オペレーションスタックには何もないので、オペレーションスタックに配置します

操作スタックに*を追加します。

出口の配列：5。

操作のスタック：*。



「2」を読みます。

オペランド、出力配列に入れます。

出力配列に2を追加します。

出口の配列：5、2。

操作のスタック：*。



「+」を読みます。

操作。 操作スタックの最後の文字（*）は、現在の文字（+）よりも優先されます。 したがって、最後の文字を操作のスタックから出力配列に移動します。

*を出口スタックに移動します。 操作スタックに+を追加します。

出口の配列：5、2、*。

操作のスタック：+。



「10」と読みます。

オペランド、出力配列に入れます。

出力配列に2を追加します。

出口の配列：5、2、*、10。

操作のスタック：+。



すべての文字がなくなったので、操作スタックから出力配列にすべてをポップします。

出口の配列：5、2、*、10、+。



これで、逆ポーランド表記法アルゴリズム（左から右）に従って結果の文字列を解くことができます。





その結果、問題の解決策があります。



5 * 2 + 10 = 20



この例は全体像を示すものではありません。 より複雑な式を試してみましょう：



（6 + 10-4）/（1 + 1 * 2）+1



「（」を読みます。

アレスタアルゴリズムは折り畳み可能であると見なされているという事実にもかかわらず、操作のブラケットを考慮しています。 これは開始ブラケットなので、単純にスタックに追加します。

（操作スタックに追加します。

出口の配列：空。

操作のスタック：（。



「6」を読む

出力配列に追加します。

出口の配列：6。

操作のスタック：（。



「+」を読む

操作スタックに追加します。

出口の配列：6。

操作のスタック：（、+。



「10」を読む

出力配列に追加します。

出口の配列：6、10。

操作のスタック：（、+。



「-」を読みます

現在の符号（-）はスタックの最後の符号（+）よりも優先度が高いため、操作のスタックから符号を出力配列にプッシュし、現在の符号をスタックに追加します。

出口の配列：6、10、+。

操作のスタック：（、-。



「4」を読む

出力配列に追加します。

出力配列：6、10、+、4。

操作のスタック：（、-。



「）」を読む

再びブレース、しかし今閉じています。 ここでは、最初の開き括弧まで、スタックからすべての文字を配列にプッシュする必要があります。 両方の括弧を取り除くだけです。

操作の配列に「-」をプッシュします。 括弧を取り除きます。

出口の配列：6,10、+、4、-。

操作のスタック：空。



「/」を読む

スタックに追加します。

出口の配列：6,10、+、4、-。

操作のスタック：/。



「（」を読む

スタックに追加します。

出口の配列：6,10、+、4、-。

操作のスタック：/、（。



「1」を読む

配列に追加します。

出力配列：6.10、+、4、-、1。

操作のスタック：/、（。



「+」を読む

スタックに追加します。

出力配列：6.10、+、4、-、1。

操作のスタック：/、（、+。



「1」を読む

配列に追加します。

出力配列：6.10、+、4、-、1、1。

操作のスタック：/、（、+。



「*」を読む

操作スタックの最後の文字（+）は、現在の文字（*）よりも低い優先度を持ちます。 したがって、スタックの最後の文字には触れず、通常どおりスタックに現在の文字を追加します。

スタックに追加します。

出力配列：6.10、+、4、-、1、1。

操作のスタック：/、（、+、*。



「2」を読む

配列に追加します。

出口の配列：6,10、+、4、-、1、1、2。

操作のスタック：/、（、+、*。



「）」を読む

最後のブラケットです。前回と同様にすべてを行います。

*および+を操作の配列にプッシュします。 括弧を取り除きます。

出口の配列：6,10、+、4、-、1、1、2、*、+。

操作のスタック：/。



「+」を読む

除算記号の優先度が高くなっています。 /を配列にポップします。 スタックに+を追加します。

出口の配列：6,10、+、4、-、1、1、2、*、+、/。

操作のスタック：+。



「1」を読む

配列に追加します。

出力配列：6.10、+、4、-、1、1、2、*、+、/、1。

操作のスタック：+。



式は終了しました。 繰り返しますが、すべてを操作スタックから出力配列にプッシュします。

出口の配列：6,10、+、4、-、1、1、2、*、+、/、1、+。



もう一度数えます。





結果：（6 + 10-4）/（1 + 1 * 2）+ 1 = 5



結論：現在の文字が操作であり、操作のスタックの最後の文字の優先度が低いか等しい場合、スタックの最後の文字が出力配列に移動し、現在の文字がスタックに追加されます。 それ以外の場合、すべてが通常どおり追加されます。 簡単に言えば、操作は出力を配列に追加するための候補ですが、そこに到達するためには、より低い、または同じ入力優先度の記号が必要です。



そうすれば、このスタッキングアルゴリズムを信頼できます。 私は明らかに、平方やルートの計算など、さらに高い優先順位記号を使用しなかったことに注意する必要があります。 これで、アルゴリズムは変わらないので、問題はないと思います。



OPNアルゴリズムの長所と短所、およびその最適化に影響するトピックについては触れません。 ここでは、この問題の解決策を探しているのと同じように、文字通りすべてを説明しようとしました。