×

[PR]この広告は3ヶ月以上更新がないため表示されています。
ホームページを更新後24時間以内に表示されなくなります。

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

"(2 + 4) * (8 - 6)" といった数式を逆ポーランド記法に変換し、それを計算するプログラムです。
計算する部分は、「逆ポーランド記法の計算」で示したコードをそのまま利用しています。

上部のTextBoxに式を入力し、Calcボタンを押せば、その結果を下の ListBoxに表示します。
() の中が、逆ポーランド記法に変換した結果です。

加減乗除を扱える数式を BNF で定義し、それをインタプリタ・パターンを使って、機械的にコーディングすれば、
式を解析することができます。
この式の解析と併せて、逆ポーランド記法に変換しています。

BNFは、以下の通りです。

<exp> ::= <term> {("+"|"-") <term>}
<term> ::= <divterm> {"*" <divterm>}
<divterm> ::= <factor> { "/" <factor>}
<factor> ::= <snumber> | "(" <exp> ")"
<snumber> ::= ["+"|"-"] {<digit>}
<digit> ::= "0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"


BNFの正式な記法は良くわかってないですが、まああたらずとも遠からずかな。

BNFの詳細は、どこかのサイトを見てほしいのですが、
/ と * の優先順位を明確になるように BNFを定義しています。
{} は繰り返し、| は選択、[] はオプション といったことがわかれば、
このページを読んでいる方ならば、読み解けるのではと思います。

数式を表す BNFとしては  "-(2 + 4) / 2" のように、先頭に符号があり、すぐに ()が続くような数式に対応していませんが、そこはご容赦を。

このBNF をインタープリタ・パターンで実装する訳ですが、
<> で囲まれた<exp> <factor> などを、インタープリタ・パターンのNodeクラスとして定義します。
Parseメソッドは、BNFの右辺部分をそのままコード化することになります。
どのようにコード化するのかは、実際にこのページの最後に示したコードを見てもらえばわかると思います。

Parseメソッドの中では、数値が現れたときには、そのままリストに追加するのですが、+ や / などの
オペレータが現れた時にはすぐにリストには追加せずに、オペレータの右側部の解析が終わったら、
リストに追加するようにします。
こうすることで、リストには、逆ポーランド形式で、数値とオペレータが格納されることになります。

逆ポーランドに変換した結果だけを表示するのでは面白くないので、このプログラムでは、
逆ポーランドに変換した式を計算し、その結果を画面に表示するようにしています。

逆ポーランド記法を、計算するには「逆ポーランド記法」で示したコードをそのまま利用しています。

ちなみに、このコードでは、整数しか扱えませんが、少しプログラムを変更すれば、小数点付きの数も
扱えるようになるはずです。

「プログラム小品集」シリーズの中では、比較的、ソースファイル数、クラス数が多いプログラムとなりましたが、一つ一つのクラスは小さめのものばかりですので、頑張って読んでみてください。

以下、C#+Silverlightのコードです。


■ReversePolishNotation .cs


■Tokenizer.cs


■Node.cs


■Context.cs


■RpnCalculator.cs


■MainPage.xaml.cs


■MainPage.xaml