逆ポーランド記法 |
---|
◆ 逆ポーランド記法 x = A × B + C 普通の人がこれを理解するのは容易なのですけど、コンピュータでは理解が難しいそうです。 そこであるのが逆ポーランド記法、これで変化した式だとコンピュータで理解できるようになるらしいです。 ここでは2分木を使って数式を、逆ポーランド記法で変換した数式にする方法を記述します。 早速、式を2分木で表現します。 2分木にする時の注意ですが、必ず左右に葉を持つ状態にします。 例として下の式を使います。 A + B 親の要素に演算子を、演算子の左側の葉に、演算子の左の部分式を・・・ と言う感じで2分木を作っていきます。 そしたら下のような感じになります。 では次に、Z = (A + B) × C をしてみます。 まず最初に親の要素にする演算子にも優先順位みたいなものが存在するらしいです。 まずは「=」、次に「+」と「−」 そして「×」、「/」 最後に「(式)」順番で親要素に持って行きます。 なので、最初は下のように要素を作りましょう。 つづいて「(式)」があるので「×」の方が優先順位的に親要素になります。 最後に( )の中の式を2分木にします。 と最終的にはこのようになるなります。 ではこれを使って逆ポーランドにします。まず円の左に何か印を付けます。 そしてZの位置から反時計回りで沿って行き、印に通ったら、その要素を取り出します。 要素を順に取り出すと以下のようになると思います。 ZAB+C×= これが逆ポーランド記法への変換だそうです。 |
TOPページに戻る |