ActionScript 3.0 で作る文字列の計算クラス

• AS3 で逆ポーランド記法
• AS3で中置記法を逆ポーランドに変換

アルゴリズムの勉強をするときに、良い題材となるのが、中間記法で書かれた文字列の式を、後置記法（逆ポーランド）に変換して計算するというものです。そこで、今回は、頭の体操として、文字列として与えた計算式を計算するクラスを作ってみます。

はじめに

ここで作る物(目標)

ActionScript 3.0 のクラスで、文字列で与えた計算式を計算する機能を備えたものを作ってみます。どのように実現したら良いのか、その考え方を紹介します。

対象とする読者

• ActionScript 3.0 について基本的な知識を備えている人
• ちょっと頭を使ってみたい人
• 文字列の計算を行う機能を必要としている人

ある晴れた日に

ある日、ふと、Flash/ActionScript で、文字列で与えた計算式を計算する機能を持ったクラスを作ってみようという気になりました。もしかしたら、何かに使えるかもと思ったのに加えて、基本的なアルゴリズムを復習する良い機会になると思ったのです。

仕事の種類にもよると思いますが、業務で作るプログラムでは、頭をひねらないと作れないというものは多くありません。どちらかと言うと、既にある部品を組み合わせたり、フレームワークで決められた手順に沿って作っていくと完成するというものが多いのです。意外とアルゴリズムの教科書に出てくるような、そこそこ頭をひねらないと解けないプログラムを作る機会は多くありません。

文字列を計算するような機能を持ったクラスは、探せば、いくらでも見つかると思います。ですから、車輪の再発明になるのですが、ここは、一度、「頭をひねる」ことを目的にしてプログラムを作ってみたいと思います。

プログラムの下調べ～後置記法について

検索エンジンで「文字列を計算する」という、そのままのキーワードで検索しても、意外と答えらしき物が見あたりません。アルゴリズムについて、ちょっと詳しければ、「後置記法」とか「逆ポーランド」とかのキーワードを思い出すことができます。そのため、「逆ポーランド　アルゴリズム」のキーワードで探すと、詳しい解説を見ることができます。

本記事は、アルゴリズムに詳しくない人でも読めることを目標としていますので、こうしたキーワードについて、簡単に見ていきます。

中置記法と後置記法

数学なので私たちが学んだ一般的な計算式は「中置記法(infix notation)」と呼ばれています。これは、数値の間に演算子が置かれる記述法です。

中置記法：

１＋２　←　数値　演算子　数値

これに対して、後置記法(逆ポーランド)と呼ばれる計算式の記法があります。これは演算子を操作対象の後に記述する記法。後置記法 (postfix notation) とも言う。たとえば、上の「１＋２」を、後置記法で書いてみると次のようになります。

後置記法：

１　２　＋　←　数値　数値　演算子

実は、日本語で計算を行う場合は、この後置記法式で、「１に２を足す」と言いますよね。「１」と「２」が数値で「足す」が演算子です。もう少し複雑な計算式を後置記法に直してみましょう。次の問題を解くことができますか？

【問題】１＋２×３　を後置記法に直してください

日本語式に書けば正解となります。かけ算は足し算よりも先に行うということを考慮しておけば、「１に、２と３を掛けたものを足す」と言えます。ですので、後置記法で書くと次のようになります。

１　２　３　×　＋

さらに、複雑な式「（１＋２）×（３＋４）」はどうでしょうか。これも日本語に直してみると「１と２を足したものと、３と４を足したものを、掛ける」と言うことができます。後置記法は次のようになります。

１　２　＋　３　４　＋　×

後置記法にすると何が嬉しいのか？

中置記法では、足し算とかけ算があれば、足し算よりもかけ算を先に計算する必要がありますし、カッコ（..）があれば、かけ算よりも、カッコの中を計算しなくてはなりません。しかし、後置記法では、こうしたカッコを使うことはなく、演算子の並べ方だけを考慮して計算させることができます。

そして何より後置記法が素晴らしいのは、スタックの構造を使うことで簡単に計算できることです。

（参考）スタックについて

「スタック」とは、後入れ先出しを基本にしたデータ構造のことです。スタックでは、基本的に、PUSH(入れる)とPOP(取り出す)の２つの動作だけを行います。

スタック構造

例えば、３と５のデータがスタックに入っていたとして、８を入れる(PUSHする)と、スタックは次のようになります。

操作　　：PUSH(8)
スタック：３　５　８

さらに４を入れる(PUSHする)と次のようになります。

操作　　：PUSH(4)
スタック：３　５　８　４

そして、１回取り出す（POPする）と、次のようになります。

操作　　：PRINT( POP() ) → 表示結果　４
スタック：３　５　８

さらに取り出す（POPする）と、次のようになります。

操作　　：PRINT( POP() ) → 表示結果　８
スタック：３　５

後置記法の計算とスタック構造

では、後置記法の計算に、スタック構造を使って計算してみます。後置記法の計算を行う上で取るべきルールは次の２つだけです。

1. 数値が表れたら、その数値をスタックに入れる
2. 演算子が表れたら、数値を２個取り出し、計算して結果をスタックに入れる

この２つのルールの通り計算していくと、どんなに複雑な後置記法の計算式も解くことができるのです。やってみましょう。

ここでは、簡単な後置記法の計算式「１　２　３　×　＋」を計算してみます。要素を１つずつ処理してみます。

• 「１」→数値なのでスタックに入れます。（スタック：１）
• 「２」→数値なのでスタックに入れます。（スタック：１　２）
• 「３」→数値なのでスタックに入れます。（スタック：１　２　３）
• 「×」→演算子なので、スタックから数値を２つ取り出して、結果をスタックに入れます。
  • スタックから数値を２つ取り出します。２と３。（スタック：１）
  • 計算結果の６をスタックに入れます。（スタック：１　６）
• 「＋」→演算子なので、スタックから数値を２つ取り出して、結果をスタックに入れます。
  • スタックから数値を２つ取り出します。１と６。（スタック：空）
  • 計算結果の７をスタックに入れます。（スタック：７）
• 最後、スタックから値を１つ取り出すと、それは答えです。（答え：７）

どうでしょうか。ルールを守ることで、計算を解くことができました。では、実際に後置記法の計算式を計算してみてください。

【問題】後置記法の式「１　２　＋　３　４　＋　×」を計算してください。

こちらも、手順を追ってみてみます。

• 「１」→数値なのでスタックに入れます。（スタック：１）
• 「２」→数値なのでスタックに入れます。（スタック：１　２）
• 「＋」→演算子なので、スタックから数値を２つ取り出して、結果をスタックに入れます。
  • スタックから数値を２つ取り出します。１と２（スタック：空）
  • 計算結果の３をスタックに入れます。（スタック：３）
• 「３」→数値なのでスタックに入れます。（スタック：３　３）
• 「４」→数値なのでスタックに入れます。（スタック：３　３　４）
• 「＋」→演算子なので、スタックから数値を２つ取り出して、結果をスタックに入れます。
  • スタックから数値を２つ取り出します。３と４（スタック：３）
  • 計算結果の７をスタックに入れます。（スタック：３　７）
• 「×」→演算子なので、スタックから数値を２つ取り出して、結果をスタックに入れます。
  • スタックから数値を２つ取り出します。３と７。（スタック：空）
  • 計算結果の２１をスタックに入れます。（スタック：２１）
• 最後、スタックから値を１つ取り出すと、それは答えです。（答え：２１）

後置記法の計算プログラム

それでは、今回の最後に、後置記法の計算を行うプログラムを作って終わりたいと思います。ActionScript 3.0 には、Array クラスがありますが、このクラスには、push() / pop() というスタック操作用のメソッドが用意されています。そこで、Array をスタックと見なして計算を行います。

以下のクラスは、後置記法(逆ポーランド記法)を計算するクラスです。（ここでは、演算子「+」「*」のみをサポートしています。）

//後置記法(逆ポーランド記法)を計算するクラス
package
{
    public class CalcRPN
    {
        public static function eval(e:String):Number
        {
            // 数値と演算子に分ける→スペースで区切る
            var items:Array = e.split(" ");
            //　後置記法（逆ポーランド）を計算する
            var stack:Array = new Array(); // 計算用スタック
            var n1:Number, n2:Number;      // 演算子計算用
            for each(var i:String in items) {
                if (i == "+") {
                    n2 = Number(stack.pop());
                    n1 = Number(stack.pop());
                    stack.push(n1 + n2);
                }
                else if (i == "*") {
                    n2 = Number(stack.pop());
                    n1 = Number(stack.pop());
                    stack.push(n1 * n2);
                }
                else {
                    stack.push(i);
                }

            }
            return Number(stack.pop());
        }
    }
}

このクラスは次のように利用します。

trace( CalcRPN.eval("1 2 +") );         // → 3
trace( CalcRPN.eval("1 2 + 3 4 + *") ); // → 21

次回予告

演算子が足すと掛けるのみであるとしても、わずか３０行足らずのプログラムで、文字列の計算ができてしまいました。このように、後置記法（逆ポーランド記法）を使うことで、簡潔に文字列の計算プログラムを作ることができるのです。

しかし、この記法をマスターするには、ちょっとコツが必要となりますので、次回は、一般的な中置記法を計算する方法について考えてみます。