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

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

アルゴリズムの勉強をするときに、良い題材となるのが、中置記法で書かれた文字列の式を、後置記法（逆ポーランド）に変換して計算するというものです。前回より頭の体操として、文字列として与えた計算式を計算するクラスを作ってみます。今回は、再帰下降構法のアルゴリズムを用いて計算を行うクラスを完成させます。

今回作る物

前回、逆ポーランド電卓を作ってみたので、今回は、中置記法で書かれた文字列を計算する ActionScript 3.0 のクラスを作ってみます。そのために、どのようなアルゴリズムを利用するのかも紹介します。

対象とする読者

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

中置記法について

前回、中置記法と後置記法（逆ポーランド）について紹介しました。後置記法で書くと、スタック構造を利用するだけであらゆる計算ができてしまうのでした。しかし、今回作る中間記法はなかなかのくせ者です。なんと言っても、ルールが面倒なのです。以下にルールを書き出してみます。

• 演算子に優先順位がある～足し算と掛け算があれば、掛け算から行うなど
• カッコ（..）があれば、その内側を優先して計算する

こうしたルールをプログラムするのには、決まり切ったやり方があります。その中で一番簡単のは、再帰下降法です。

再帰下降法

これは、関数の再帰を使って式を評価する方法です。それぞれ計算を行う演算子ごとに関数を用意しておいて、優先度の低い所から高い演算子へと再帰的に関数を呼び出すことで計算を行うことができます。

このアルゴリズム、ソースを見た方が、理解が優しいというものです。それほど長くない(70行ほど)ので、まずは眺めてみてください。一番始めに追うのは、Expression() から見てください。

package {
    public class CalcInfix {
        public var items:Array = [];
        private function Factor():Number // 数値やカッコ
        {
            var num:Number = 0;
            var flag:Number = 1;
            var tmp:String = items.shift();
            // フラグのチェック
            if (tmp == "-" || tmp == "+") {
                if (tmp == "-") { flag = -1; }
                tmp = items.shift();
            }
            // 数値か?
            if (tmp.match(/^\d+$/) != null) {
                num = Number(tmp) * flag;
            }
            else if (tmp == "(") { // カッコか？
                num = Expression();
                tmp = items.shift();
                if (tmp != ")") {
                    throw Error("計算式の書き間違い");
                }
            } else {
                items.unshift(tmp);
            }
            return num;
        }
        private function MulDiv():Number // かけ算割り算
        {
            var num:Number = Factor();
            var tmp:String = items.shift();
            while (tmp == "*" || tmp == "/" || tmp == "%") {
                switch (tmp) {
                    case '*': num *= Factor(); break;
                    case '/': num -= Factor(); break;
                    case '%': num %= Factor(); break;
                }
                tmp = items.shift();
            }
            items.unshift(tmp);
            return num;
        }
        private function AddSub():Number // 足し算引き算
        {
            var num:Number = MulDiv();
            var tmp:String = items.shift();
            while (tmp == "+" || tmp == "-") {
                switch (tmp) {
                    case '+': num += MulDiv(); break;
                    case '-': num -= MulDiv(); break;
                }
                tmp = items.shift();
            }
            items.unshift(tmp);
            return num;
        }
        public function Expression():Number // 評価する
        {
            return AddSub();
        }
        public static function eval(e:String):Number
        {
            // 数値と演算子を区切る
            e = e.replace(/\s*/g, '');
            e = e.replace(/(\d+)/g, '$1 ');
            e = e.replace(/([\%\(\)\-\^\+\*\/])/g, '$1 ');
            var items:Array = e.split(/\s/);
            var p:CalcInfix = new CalcInfix();
            p.items = items;
            return p.Expression();
        }
    }
}

Expression() の中で、AddSub() を呼んでいます。そして、この AddSub() の中で、MulDiv() を呼び、MulDiv() の中で、Factor() を呼ぶというように、優先度の低いものから、高い関数を次々と再帰的に呼び出して行きます。この結果計算が行われて結果が返ってきます。

この「CalcInifix」クラスを使うには、以下のように書きます。

trace( CalcInfix.eval("(1 + 2) * 3") ); // 結果→ 9

中置記法を後置記法に変換してから計算する

次に、中置記法を後置記法に変換してから計算する方法について考えてみます。明確に因子について優先順位を設定します。その方法はスタック構造を２つ用意しておいて、これを移動させることで変換します。

変換のためには、次のように処理を行います。このために、一時待避用のstackと、変換結果のpolishの２つのスタックを用意します。

• （１）式の最後まで以下の処理を行う
  • （２）式から１つ因子を取り出してTとする
  • （３）優先順位が(T ≦ stackのトップ)の間以下を繰り返す
    • （４）polish に stackのトップを積む
  • （５）T を stack に積む
• （６）stack に残った因子を polish に積み直す

この処理を行うことで、中置記法の計算式を後置記法に変換できます。

package {
    public class CalcInfix2 {
        public var items:Array;
        public function Expression():String {
            //--- 中置記法を逆ポーランドに変換
            var stack:Array = [];
            var polish:Array = [];
            var priority:Object = {'n':3, '*':2, '/':2, '%':2, '+':1, '-':1};
            var getPriority:Function = function(s:String):int {
                return (priority[s] != undefined) ?
                        priority[s] : priority["n"];
            };
            for each (var tmp:String in items) { // --- (1)(2)
                if (tmp == "" || tmp == " ") continue;
                while (stack.length > 0) { // --- (3)
                    var top:String = stack[stack.length - 1];
                    if (getPriority(tmp) <= getPriority(top)) {
                        polish.push(stack.pop()); // --- (4)
                    } else break;
                }
                stack.push(tmp); // --- (5)
            }
            while (stack.length > 0) { polish.push(stack.pop()); }
            return polish.join(" "); // 結果を出力
        }
        public static function eval(e:String):Number
        {
            // 数値と演算子を区切る
            e = e.replace(/\s*/g, '');
            e = e.replace(/(\d+)/g, '$1 ');
            e = e.replace(/([\%\(\)\-\^\+\*\/])/g, '$1 ');
            var p:CalcInfix2 = new CalcInfix2();
            p.items = e.split(/\s/);
            trace(p.Expression());
            return 0;
        }
    }
}

但し、上記の方法では、カッコ(..)を処理することができません。そこで、カッコが来た時の処理を例外的に追加します。ここでは、優先順位では、カッコの優先度を一番下げておき、例外的に stack から polish に移動させます。

package {
    public class CalcInfix2 {
        public var items:Array;
        public function Expression():String {
            //--- 中置記法を逆ポーランドに変換
            var stack:Array = [];
            var polish:Array = [];
            var priority:Object = {
                'n':3, '*':2, '/':2, '%':2, '+':1, '-':1, '(':0};
            var getPriority:Function = function(s:String):int {
                return (priority[s] != undefined) ?
                        priority[s] : priority["n"];
            };
            var top:String;
            for each (var tmp:String in items) {
                if (tmp == "" || tmp == " ") continue;
                if (tmp == "(") {
                    stack.push(tmp);
                }
                else if (tmp == ")") {
                    while (stack.length > 0) {
                        top = stack[stack.length - 1];
                        if (top != "(") {
                            polish.push(stack.pop());
                        } else break;
                    }
                    stack.pop();// skip '('

                }
                else {
                    while (stack.length > 0) {
                        top = stack[stack.length - 1];
                        if (getPriority(tmp) <= getPriority(top)) {
                            polish.push(stack.pop());
                        } else break;
                    }
                    stack.push(tmp);
                }
                // DEBUG
                trace("polish=", polish.join(" "));
                trace("stack =", stack.join(" "));
                trace("---");
            }
            while (stack.length > 0) { polish.push(stack.pop()); }
            return polish.join(" "); // 結果を出力
        }
        public static function eval(e:String):Number
        {
            // 数値と演算子を区切る
            e = e.replace(/\s*/g, '');
            e = e.replace(/(\d+)/g, '$1 ');
            e = e.replace(/([\%\(\)\-\^\+\*\/])/g, '$1 ');
            var p:CalcInfix2 = new CalcInfix2();
            p.items = e.split(/\s/);
            trace(p.Expression());
            return 0;
        }
    }
}

上記のプログラムでは、プログラムの動作が分かりやすいように、stack と polish の内容を繰り返しのたびに見られるようにしています。例えば、「1+2*(3+4)」の実行結果は次のようになります。

それでは、これに前回作った後置記法の計算を組み込んでみます。以下が完成版のソースとなります。結局、再帰下降法と同じくらいの行数になりました。

package {
    public class CalcInfix2 {
        public var items:Array;
        public function Expression():Number {
            //--- 中置記法を逆ポーランドに変換
            var stack:Array = [];
            var polish:Array = [];
            var priority:Object = {
                'n':3, '*':2, '/':2, '%':2, '+':1, '-':1, '(':0};
            var getPriority:Function = function(s:String):int {
                return (priority[s] != undefined) ?
                        priority[s] : priority["n"];
            };
            var top:String;
            for each (var tmp:String in items) {
                if (tmp == "" || tmp == " ") continue;
                if (tmp == "(") {
                    stack.push(tmp);
                }
                else if (tmp == ")") {
                    while (stack.length > 0) {
                        top = stack[stack.length - 1];
                        if (top != "(") {
                            polish.push(stack.pop());
                        } else break;
                    }
                    stack.pop();// skip '('

                }
                else {
                    while (stack.length > 0) {
                        top = stack[stack.length - 1];
                        if (getPriority(tmp) <= getPriority(top)) {
                            polish.push(stack.pop());
                        } else break;
                    }
                    stack.push(tmp);
                }
            }
            while (stack.length > 0) { polish.push(stack.pop()); }
            //--- 逆ポーランドを計算
            var v1:Number, v2:Number;
            var getStack2:Function = function():void{
                v2 = Number(stack.pop());
                v1 = Number(stack.pop());
            };
            for each(var i:String in polish) {
                switch(i) {
                    case '+': getStack2(); stack.push(v1 + v2); break;
                    case '-': getStack2(); stack.push(v1 - v2); break;
                    case '*': getStack2(); stack.push(v1 * v2); break;
                    case '/': getStack2(); stack.push(v1 / v2); break;
                    case '%': getStack2(); stack.push(v1 % v2); break;
                    default: stack.push(i); break;
                }
            }
            return Number(stack.pop());
        }
        public static function eval(e:String):Number
        {
            // 数値と演算子を区切る
            e = e.replace(/\s*/g, '');
            e = e.replace(/(\d+)/g, '$1 ');
            e = e.replace(/([\%\(\)\-\^\+\*\/])/g, '$1 ');
            var p:CalcInfix2 = new CalcInfix2();
            p.items = e.split(/\s/);
            return p.Expression();
        }
    }
}

ただし、上記の物は、-5 のような負数や 3.14 のような実数を正しく扱えません。ちょっと工夫することで実現できます。以下に、floor(N) や sin(N) のような関数機能を追加した完全版を載せて、この記事を終わりたいと思います。

文字列計算クラスの改善版

文字列で書かれた計算式を計算して返します。関数(floor/ceil/sin/cos/tan/random/absなど)や実数の計算に対応しています。

/**
 * 文字列計算クラス CalcInfix
 * [author] kujirahand (http://kujirahand.com)
 * [date]   2009-01-11
 * @example 文字列で書かれた式を計算する
 * var n:Number = CalcInfix.eval("1+floor(2^3/5)");
 * trace(n);
 */
package {
    public class CalcInfix
    {
        public var items:Array;
        public function Expression():Number {
            //--- 中置記法を逆ポーランドに変換
            var stack:Array = [];
            var polish:Array = [];
            var priority:Object = {
                'func':4, 'num':4,
                '^':3, '*':2, '/':2, '%':2, '+':1, '-':1,
                '(':0
            };
            var getPriority:Function = function(s:String):int {
                if (priority[s] != undefined) {
                    return priority[s];
                }
                if (s.match("^\w+$") != null) {
                    return priority["func"];
                }
                return priority["num"];
            };
            var top:String;
            for each (var tmp:String in items) {
                if (tmp == "" || tmp == " ") continue;
                if (tmp == "(") {
                    stack.push(tmp);
                }
                else if (tmp == ")") {
                    while (stack.length > 0) {
                        top = stack[stack.length - 1];
                        if (top != "(") {
                            polish.push(stack.pop());
                        } else break;
                    }
                    stack.pop();// skip '('

                }
                else {
                    while (stack.length > 0) {
                        top = stack[stack.length - 1];
                        if (getPriority(tmp) <= getPriority(top)) {
                            polish.push(stack.pop());
                        } else break;
                    }
                    stack.push(tmp);
                }
                // DEBUG
                //trace("polish=", polish.join(" "));
                //trace("stack =", stack.join(" "));
                //trace("---");
            }
            while (stack.length > 0) { polish.push(stack.pop()); }
            return calcPostfix(polish);
        }
        public static function calcPostfix(polish:Array):Number
        {
            var stack:Array = [];
            var v1:Number, v2:Number;
            var getStack2:Function = function():void {
                v2 = Number(stack.pop());
                v1 = Number(stack.pop());
            };
            var getStack1:Function = function(): void {
                v1 = Number(stack.pop());
            };
            for each(var i:String in polish) {
                switch(i) {
                    // 演算子
                    case '+': getStack2(); stack.push(v1 + v2); break;
                    case '-': getStack2(); stack.push(v1 - v2); break;
                    case '*': getStack2(); stack.push(v1 * v2); break;
                    case '/': getStack2(); stack.push(v1 / v2); break;
                    case '%': getStack2(); stack.push(v1 % v2); break;
                    case '^': getStack2(); stack.push(Math.pow(v1,v2)); break;
                    // 関数
                    case 'floor': getStack1(); stack.push(Math.floor(v1)); break;
                    case 'ceil':  getStack1(); stack.push(Math.ceil(v1)); break;
                    case 'random':  getStack1();
                        stack.push(Math.floor(Math.random()*v1)); break;
                    case 'sin': getStack1(); stack.push(Math.sin(v1)); break;
                    case 'cos': getStack1(); stack.push(Math.cos(v1)); break;
                    case 'tan': getStack1(); stack.push(Math.tan(v1)); break;
                    case 'asin': getStack1(); stack.push(Math.asin(v1)); break;
                    case 'acon': getStack1(); stack.push(Math.acos(v1)); break;
                    case 'atan': getStack1(); stack.push(Math.atan(v1)); break;
                    case 'abs': getStack1(); stack.push(Math.abs(v1)); break;
                    default: stack.push(i); break;
                }
            }
            return Number(stack.pop());
        }
        private function checkMinus():void
        {
            var tmp:String;
            // 先頭のマイナスを数値に反映させる
            if (items[0] == "-") {
                items[1] = items[1] * -1;
                items.shift();
            }
            // 演算子の直後のマイナスを数値に反映させる
            var enzansi:String = "()+-*/%^";
            var i:int = 0;
            while ( i < items.length ) {
                if (enzansi.indexOf(items[i]) >= 0) {
                    if (items[i+1] == "-") {
                        items[i+2] = items[i+2] * -1;
                        items.splice(i+1, 1);
                    }
                }
                i++;
            }
        }
        /**
        * 文字列の計算式を計算して返す
        * @param    e    文字列で計算式を指定する(中置記法)
        * @rerurn        計算結果
        */
        public static function eval(e:String):Number
        {
            // 数値と演算子を区切る
            e = e.replace(/\s*/g, ''); // 空白を除去
            e = e.replace(/((\d+\.\d+|\d+))/g, '$1 '); // 数値の後にスペース
            e = e.replace(/([a-z\_]+)/g, '$1 '); // 関数の後にスペース
            e = e.replace(/([\%\(\)\-\^\+\*\/\^])/g, '$1 ');
            var p:CalcInfix = new CalcInfix();
            p.items = e.split(/\s/);
            p.checkMinus();
            return p.Expression();
        }
    }
}

参考にしたもの

• 河西朝雄著『Java によるはじめてのアルゴリズム入門』(技術評論社)