過去のブログのアーカイブ
この記事は前身のブログのアーカイブを引き継いだものです．
画像が正しく表示できないなど，コンテンツの表示に問題がある恐れがあります．前回逆ポーランド記法の仕組みについて書きました。今回は通常の式から逆ポーランド記法の式に変換するアルゴリズムについて紹介します。
この紹介に間違いがあったことを確認しました。
この記事の紹介では左から右へ演算子を検索していますが、実際にアルゴリズムを組む時は、右から左に検索をすることで正しい変換になります。
基本的な紹介はあってます。検索順序だけ頭の中で置き換えて読んでください。
後日画像を差し替えます。
この記事の紹介では左から右へ演算子を検索していますが、実際にアルゴリズムを組む時は、右から左に検索をすることで正しい変換になります。
基本的な紹介はあってます。検索順序だけ頭の中で置き換えて読んでください。
後日画像を差し替えます。
演算子の優先順位・特性を考慮する
演算子の中には優先順位や特殊な特性のある演算子があります。
また、ここでは演算子として紹介していますが、やりよう次第ではsinやcosなどの関数等にも似たような方法で対応させることもできます！(ここでは割愛させていただきます。)
まず演算子に優先順位をつける作業をしましょう。
通常の四則計算ではこのようになります。
- * /
- + –
- =
そして、=を除いて、左右の数字を処理(計算)するものです。
逆に、=は数字を何かする存在ではないため、ちょっと特殊な存在になります。
あとはひたすらソートする
あとは先ほどの優先順位順に演算子の検索→リストに追加していくとすれば終わりです。
ここで一つポイントがありまして、演算子を追加する際には右の数字から先に追加するとなおベター
なぜかというと、割り算の時とかにわかると思うのですが、
4 / 2 =とかの計算式を左・右の順番でリストに入れてしまうと
4 2 /=になってしまいます。だと楽にコードを書くことができなくなるんですね
Stack<double> stack = new Stack<double>; // 4 2 // ... // 2 / 4と計算してしまう stack.Push(stack.Pop() / stack.Pop());
なのであえて右・左の順番にリストに追加しています。
まとめ
変換の概要は以上です。
あとはsinとかcosとかに対応させるなら、優先順位を考えて処理すればいいだけです。逆ポーランド記法はコンピュータ上の計算式の基礎の基礎です。確実に抑えるようにしましょう。
