逆ポーランド入力
2プラス2、2を掛けますか？
私はあなたのことは知りませんが、学校では、手術とブラケットの優先順位を理解しようとして長い間苦しみました。 それから、すべての初心者プログラマーのように、自分の計算機を書いたとき、操作と括弧の優先度に苦しめられました。 しかし、この苦痛はすべて無駄だったことが判明しました。 結局のところ、逆ポーランド記法として知られている素晴らしいメカニズムがあります。 私はそれが何であり、どのようにそれを扱うかをあなたに伝えたいです。
数学では、オペランド（x + y）ではなく、オペランド（x + y）の間に演算子を配置するという古くからの伝統があります。 オペランドの間に演算子があるフォームは、中置記法と呼ばれます。 オペランドの後に演算子があるフォームは、この表記法の特性を研究したポーランドの論理学者J. Lukasevic（1958）を称えて、後置または逆ポーランド表記法と呼ばれます。
代数公式を表現する場合、逆ポーランド表記法は、中置表記法よりもいくつかの利点があります。 まず、括弧なしで式を表現できます。 第二に、 スタックを持つマシンで数式を計算するのに便利です 。 第三に、中置演算子には、arbitrary意的で望ましくない優先順位があります。 たとえば、ab + cはa（b + c）ではなく（ab）+ cを意味することがわかっています。これは、乗算が加算より優先されることが任意に決定されたためです。 しかし、左シフトは演算ANDより優先されますか？ 誰が知っている 逆ポーランド記法はそのような誤解を排除します。
問題の声明
プログラムの入力は、単一文字の識別子と算術演算の符号で構成される式を受け取ります。 この式をポーランド表記法を逆に変換するか、エラーを報告する必要があります。
逆ポーランド記録アルゴリズム
中置式を逆ポーランド記法に変換するためのアルゴリズムがいくつかあります。 E.ダイクストラ（EWダイクストラ）によって提案されたアイデアが修正されたアルゴリズムを検討します。 数式が変数、2つのオペランドの演算子+、-、*、/、^、および左右の括弧で構成されているとします。 数式の終わりを示すために、最後の文字の後、次の数式の最初の文字の前に文字を挿入します。
この図は、ニューヨークからカリフォルニアへの鉄道とテキサスへの分岐を概略的に示しています。 数式の各記号は、1つのキャリッジで表されます。 列車は西へ（左へ）移動します。 矢印の前で、各車が停止し、カリフォルニアに直行する必要があるかどうか、または途中でテキサスに電話する必要があるかどうかを確認する必要があります。 変数を含むワゴンは常にカリフォルニアに送られ、テキサスに移動することはありません。 他のすべてのシンボルを含むワゴンは、矢印を通過する前にテキサスに行った最も近いワゴンの内容を知っている必要があります。
この表は、どの車両が最後にテキサスに行き、どの車両が矢印にあるかによる状況の依存性を示しています。 最初のワゴン（⊥マーク）は常にテキサスに向けて出発します。
番号は次の状況に対応しています。
1.矢印のワゴンはテキサスに向けて出発します
2.テキサスに向かう最後のワゴンは、向きを変えてカリフォルニアに向かう
3.矢印のワゴンとテキサスに向かう最後のワゴンが盗まれて消えます
4.停止します。 カリフォルニア支店にある記号は、左から右に読む逆ポーランド記法の式を表します
5.停止します。 エラーが発生しました。 元の式のバランスが誤っていた
各アクションの後、矢印にあるワゴン（前の比較と同じワゴンでも、次のワゴンでもよい）と現在テキサスに残っている最後のワゴンの新しい比較が行われます。 このプロセスは、ステップ4に達するまで続きます。テキサスへの行はスタックとして使用され、テキサスへのワゴンの送信はスタックにアイテムを配置し、テキサスに送られた車をカリフォルニアに向けることは要素を押し出すことに注意してくださいスタック。
中置および後置エントリの変数の順序は同じです。 ただし、演算子の順序は常に同じではありません。 逆ポーランド表記では、ステートメントは実行される順序で表示されます。
逆ポーランド記法で式を評価する例
逆ポーランド記法は、スタックのあるコンピューターで数式を計算するのに理想的です。 数式はn文字で構成され、各文字はオペランドまたは演算子です。 スタックを使用して逆ポーランド記法で数式を計算するアルゴリズムは簡単です。 ポーランド語の逆エントリを左から右に読むだけです。 オペランドが見つかった場合、それをスタックにプッシュする必要があります。 演算子が検出された場合、指定された操作を実行する必要があります。
例として、次の式の計算を検討してください：（8 + 2 * 5）/（1 + 3 * 2-4）。 逆ポーランド表記の対応する式は次のようになります：825 * + 132 * + 4- /
スタックの最上部の数字は、右側のオペランドです（左側ではありません）。 これは、この場合のオペランドの順序が重要であるため、除算、減算、およびべき乗の演算にとって非常に重要です（加算および乗算の演算とは対照的に）。 つまり、除算演算は次のように動作します。最初に分子がスタックに配置され、次に分母が配置され、次に演算により正しい結果が得られます。 逆ポーランド記法をマシンコードに変換するのは非常に簡単であることに注意してください：逆ポーランド記法の式で移動するだけで、各文字に1つのコマンドを書き留めることができます。 シンボルが定数または変数の場合、この定数または変数をスタックに配置するコマンドを入力する必要があります。シンボルが演算子の場合、この操作を実行するにはコマンドを入力する必要があります。
PSあなたはいつものように、それがhabraeffectに落ちるまで私のサイトにソースコードをダウンロードできます 。
PPSこれで、誰もが独自の計算機を作成できるようになりました。 ブラックジャックとブラケット付き。
私はあなたのことは知りませんが、学校では、手術とブラケットの優先順位を理解しようとして長い間苦しみました。 それから、すべての初心者プログラマーのように、自分の計算機を書いたとき、操作と括弧の優先度に苦しめられました。 しかし、この苦痛はすべて無駄だったことが判明しました。 結局のところ、逆ポーランド記法として知られている素晴らしいメカニズムがあります。 私はそれが何であり、どのようにそれを扱うかをあなたに伝えたいです。
数学では、オペランド（x + y）ではなく、オペランド（x + y）の間に演算子を配置するという古くからの伝統があります。 オペランドの間に演算子があるフォームは、中置記法と呼ばれます。 オペランドの後に演算子があるフォームは、この表記法の特性を研究したポーランドの論理学者J. Lukasevic（1958）を称えて、後置または逆ポーランド表記法と呼ばれます。
代数公式を表現する場合、逆ポーランド表記法は、中置表記法よりもいくつかの利点があります。 まず、括弧なしで式を表現できます。 第二に、 スタックを持つマシンで数式を計算するのに便利です 。 第三に、中置演算子には、arbitrary意的で望ましくない優先順位があります。 たとえば、ab + cはa（b + c）ではなく（ab）+ cを意味することがわかっています。これは、乗算が加算より優先されることが任意に決定されたためです。 しかし、左シフトは演算ANDより優先されますか？ 誰が知っている 逆ポーランド記法はそのような誤解を排除します。
問題の声明
プログラムの入力は、単一文字の識別子と算術演算の符号で構成される式を受け取ります。 この式をポーランド表記法を逆に変換するか、エラーを報告する必要があります。
逆ポーランド記録アルゴリズム
中置式を逆ポーランド記法に変換するためのアルゴリズムがいくつかあります。 E.ダイクストラ（EWダイクストラ）によって提案されたアイデアが修正されたアルゴリズムを検討します。 数式が変数、2つのオペランドの演算子+、-、*、/、^、および左右の括弧で構成されているとします。 数式の終わりを示すために、最後の文字の後、次の数式の最初の文字の前に文字を挿入します。
この図は、ニューヨークからカリフォルニアへの鉄道とテキサスへの分岐を概略的に示しています。 数式の各記号は、1つのキャリッジで表されます。 列車は西へ（左へ）移動します。 矢印の前で、各車が停止し、カリフォルニアに直行する必要があるかどうか、または途中でテキサスに電話する必要があるかどうかを確認する必要があります。 変数を含むワゴンは常にカリフォルニアに送られ、テキサスに移動することはありません。 他のすべてのシンボルを含むワゴンは、矢印を通過する前にテキサスに行った最も近いワゴンの内容を知っている必要があります。
この表は、どの車両が最後にテキサスに行き、どの車両が矢印にあるかによる状況の依存性を示しています。 最初のワゴン（⊥マーク）は常にテキサスに向けて出発します。
番号は次の状況に対応しています。
1.矢印のワゴンはテキサスに向けて出発します
2.テキサスに向かう最後のワゴンは、向きを変えてカリフォルニアに向かう
3.矢印のワゴンとテキサスに向かう最後のワゴンが盗まれて消えます
4.停止します。 カリフォルニア支店にある記号は、左から右に読む逆ポーランド記法の式を表します
5.停止します。 エラーが発生しました。 元の式のバランスが誤っていた
各アクションの後、矢印にあるワゴン（前の比較と同じワゴンでも、次のワゴンでもよい）と現在テキサスに残っている最後のワゴンの新しい比較が行われます。 このプロセスは、ステップ4に達するまで続きます。テキサスへの行はスタックとして使用され、テキサスへのワゴンの送信はスタックにアイテムを配置し、テキサスに送られた車をカリフォルニアに向けることは要素を押し出すことに注意してくださいスタック。
中置および後置エントリの変数の順序は同じです。 ただし、演算子の順序は常に同じではありません。 逆ポーランド表記では、ステートメントは実行される順序で表示されます。
逆ポーランド記法で式を評価する例
逆ポーランド記法は、スタックのあるコンピューターで数式を計算するのに理想的です。 数式はn文字で構成され、各文字はオペランドまたは演算子です。 スタックを使用して逆ポーランド記法で数式を計算するアルゴリズムは簡単です。 ポーランド語の逆エントリを左から右に読むだけです。 オペランドが見つかった場合、それをスタックにプッシュする必要があります。 演算子が検出された場合、指定された操作を実行する必要があります。
例として、次の式の計算を検討してください：（8 + 2 * 5）/（1 + 3 * 2-4）。 逆ポーランド表記の対応する式は次のようになります：825 * + 132 * + 4- /
スタックの最上部の数字は、右側のオペランドです（左側ではありません）。 これは、この場合のオペランドの順序が重要であるため、除算、減算、およびべき乗の演算にとって非常に重要です（加算および乗算の演算とは対照的に）。 つまり、除算演算は次のように動作します。最初に分子がスタックに配置され、次に分母が配置され、次に演算により正しい結果が得られます。 逆ポーランド記法をマシンコードに変換するのは非常に簡単であることに注意してください：逆ポーランド記法の式で移動するだけで、各文字に1つのコマンドを書き留めることができます。 シンボルが定数または変数の場合、この定数または変数をスタックに配置するコマンドを入力する必要があります。シンボルが演算子の場合、この操作を実行するにはコマンドを入力する必要があります。
PSあなたはいつものように、それがhabraeffectに落ちるまで私のサイトにソースコードをダウンロードできます 。
PPSこれで、誰もが独自の計算機を作成できるようになりました。 ブラックジャックとブラケット付き。
All Articles