逆ポーランド記法

お久しぶりです。
先日の GDC 2012 でついに新作SimCityが発表になり、
今から楽しみで仕方のないタイラです。

さて、Googleの検索機能の中に関数グラフ表示機能があるのをご存知でしょうか？
　 x/2, (x/2)^2, 2^x
を検索するとグラフが表示されます。

今回はこの計算を作ってみました。
計算する方法ですが、逆ポーランド記法(Reverse Polish Notation) を用います。

通常、非演算子の間に演算子を書きますが、
この記法では非演算子の後に演算子を書きます。

変換前(通常)
　1 + 2 * 3 - 4

変換後(逆ポーランド記法)
　1 2 3 * + 4 -

並び替えキューに積んだ後順番に取り出しながらスタックへ積み上げていき、
演算子だった場合はスタックの上から2つの値を用い計算を行います。
キューの最後まで取り出して計算をすると、
最終的にスタック上には1つのデータが残り、式の答えになります。

        [stack]         [queue]
                        1 2 3 * + 4 -
        1               2 3 * + 4 -
        1 2             3 * + 4 -
        1 2 3           * + 4 -
        1 2 3 *         + 4 -
        1 6             + 4 -
        1 6 +           4 -
        7               4 -
        7 4             -
        7 4 -
        3 	// 答え

グラフ表示用では関数用の'x'をそのまま数値と同様に並び替え、
計算時に実際の数値に置き換えれる事で計算が出来ます。

変換前(通常)
　1 + 2 * x - 4

変換後(逆ポーランド記法)
　1 2 x * + 4 -

        // x = 3;
        [stack]         [queue]
                        1 2 x * + 4 -	// 並び替え時も'x'のまま保持
        1               2 x * + 4 -
        1 2             x * + 4 -
        1 2 x           * + 4 -
        1 2 3           * + 4 -		// ここで'x'を置き換える
        1 2 3 *         + 4 -
        1 6             + 4 -
        1 6 +           4 -
        7               4 -
        7 4              -
        7 4 -
        3 	// 答え

xの値を順番に変化させていけばグラフが作れますね。
三角関数や指数関数の計算はスタックの上1つを計算することで実現できます。
関数のバリエーションを増やすと関数電卓の代わりになりますね。

ソースを載せるとかなり長くなるので、サンプルファイルを用意しました。
rpn.cpp

普段使っている物にも意外な機能を持っている事があります。
みなさんも探してみては如何でしょうか？

ちなみにGoogleで
　sqrt(cos(x)) * cos(300x) + sqrt(abs(x)) from -4 to 4
と検索するとハート型に見えますよ。

それでは