逆ポーランド記法に変換する


前回逆ポーランド記法の仕組みについて書きました。今回は通常の式から逆ポーランド記法の式に変換するアルゴリズムについて紹介します。

この紹介に間違いがあったことを確認しました。
この記事の紹介では左から右へ演算子を検索していますが、実際にアルゴリズムを組む時は、右から左に検索をすることで正しい変換になります。
基本的な紹介はあってます。検索順序だけ頭の中で置き換えて読んでください。
後日画像を差し替えます。

演算子の優先順位・特性を考慮する

演算子の中には優先順位や特殊な特性のある演算子があります。

また、ここでは演算子として紹介していますが、やりよう次第ではsinやcosなどの関数等にも似たような方法で対応させることもできます!(ここでは割愛させていただきます。)

まず演算子に優先順位をつける作業をしましょう。

通常の四則計算ではこのようになります。

  1. * /
  2. + -
  3. =

そして、=を除いて、左右の数字を処理(計算)するものです。

逆に、=は数字を何かする存在ではないため、ちょっと特殊な存在になります。

あとはひたすらソートする

あとは先ほどの優先順位順に演算子の検索→リストに追加していくとすれば終わりです。

20161010_134440

 

ここで一つポイントがありまして、演算子を追加する際には右の数字から先に追加するとなおベター

なぜかというと、割り算の時とかにわかると思うのですが、

4 / 2 =とかの計算式を左・右の順番でリストに入れてしまうと

4 2 /=になってしまいます。だと楽にコードを書くことができなくなるんですね

なのであえて右・左の順番にリストに追加しています。

まとめ

変換の概要は以上です。

あとはsinとかcosとかに対応させるなら、優先順位を考えて処理すればいいだけです。逆ポーランド記法はコンピュータ上の計算式の基礎の基礎です。確実に抑えるようにしましょう。

Uncategorized

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">