逆ポーランドで遊んでみる

作ってみた

JavaScriptで、とても単純な逆ポーランドの記法の処理系を書いてみました。ちなみに足し算しかできません。最も基本的な文法は、こんな形になります。

3 4 plus

これは 3 + 4 を計算します。演算子は「+」だと面白くないので、「plus」にしてみました。もう少し複雑な計算をしてみます。

5 2 plus 11 plus

これは 5 + 2 + 11を計算します。

5 2 11 plus plus

こっちは、5 + ( 2 + 11 ) を計算します。先に ( 2 + 11 ) が計算されるのがポイントです。普段私たちが利用している中置記法では、先に計算して欲しい部分には、括弧をつける必要がありますが、ポーランド記法場合は括弧が不要です。

使い方

上で説明した構文を文字列として定義し、parse関数に渡してやると結果が返ってきます。

var str = "5 2 11 plus plus"; // 5+(2+11)
alert( parse(str) ); //18

ソースコード

結構短いです。引き算、掛け算、割り算あたりはすぐに追加できるでしょう。二乗なんていう処理は、数値1つで出来るので、面白いかもしれませんね。

function init(){
    //var str ="3 4 plus"; //3+4
    //var str ="5 2 plus 11 plus"; //(5+2) + 11
    //var str = "5 2 11 plus plus"; // 5+(2+11)
    var str = "5 2 11 plus plus 3 plus 4 plus 5 plus"; // 5+(2+11) + 3 + 4 + 5
    alert( parse(str) );
}

function parse(stream){
    stream = stream.split(" ");
    var stack = new Array();
    while(0<stream.length){
        var reg1 = stream.shift();
        switch(reg1){
            case "plus" :
                var reg1 = stack.pop();
                var reg2 = stack.pop();
                if(!isNum(reg1) || !isNum(reg2)) throw new Error("構文にミスがあります");
                stack.push(reg1 + reg2);
                break;
            default:
                if( isNum(reg1) ){
                    stack.push(parseInt(reg1));
                }else throw new Error("構文にミスがあります");
                break;
        }
    }
    if(stack.length != 1 || !isNum(stack[0]) ) throw new Error("構文にミスがあります");
    return stack.pop();
}

function isNum(num){
    num = parseInt(num);
    return (typeof num == "number");   
}

余談

ちなみにJavaScriptの型変換がすこし面倒でした。最初は文字列として渡しているので、ちゃんと数値に変換しないと、「＋」の演算子は、文字列として連結されてしまいます。こんな風になりますので、注意してください。

"3" + "4" = "34"

追記 2010/02/02

もうちょっと改良

/**
 * @author Lucy
 */

function init(){
    //var str ="3 4 add"; //3+4
    //var str ="5 2 add 11 add"; //(5+2) + 11
    //var str = "5 2 11 add add"; // 5+(2+11)
    //var str = "5 2 11 add add 3 add 4 add 5 add"; // 5+(2+11) + 3 + 4 + 5
    
    //var str ="3 4 sub"; //3-4
    //var str ="3 -4 sub"; //3-(-4)
    //var str ="3 4 sub 5 sub"; //3-4 -5
    //var str ="3 4 5 sub sub"; // 3 - (4-5)
    
    //var str ="3 4 mul"; //3*4
    //var str ="3 4 mul 5 mul"; //3*4*5
    //var str ="3 4 5 mul mul"; // 3 * (4*5)
    
    //var str ="100 4 div"; // 100/4
    //var str ="100 4 div 5 div"; // 100/4/5
    //var str ="100 4 5 div div"; //100 / (4/5)
    
    //var str ="2 squ"; //2^2
    //var str ="3 squ squ"; // 3^2^2
    
    //var str = "2 del 3"; //3
    var str = "2 3 4 5 del del del"; //2

    document.write( parse(str) );
}

function parse(stream){
    stream = stream.split(" ");
    var stack = new Array();
    while(0<stream.length){
        var reg1 = stream.shift();
        switch(reg1){
            case "add" : //足し算
                var reg1 = stack.pop();
                var reg2 = stack.pop();
                if(!isNum(reg1) || !isNum(reg2)) throw new Error("構文にミスがあります");
                stack.push(reg1 + reg2);
                break;
            case "sub" : //引き算
                var reg1 = stack.pop();
                var reg2 = stack.pop();
                if(!isNum(reg1) || !isNum(reg2)) throw new Error("構文にミスがあります");
                stack.push(reg2 - reg1);
                break;
            case "mul" : //掛け算
                var reg1 = stack.pop();
                var reg2 = stack.pop();
                if(!isNum(reg1) || !isNum(reg2)) throw new Error("構文にミスがあります");
                stack.push(reg1 * reg2);
                break;
            case "div" : //割り算
                var reg1 = stack.pop();
                var reg2 = stack.pop();
                if(!isNum(reg1) || !isNum(reg2)) throw new Error("構文にミスがあります");
                stack.push( reg2 / reg1); //ゼロ割り算の計算結果はjavascriptにまかせる
                break;
             case "squ" : //二乗
                var reg1 = stack.pop();
                if(!isNum(reg1)) throw new Error("構文にミスがあります");
                stack.push( reg1 * reg1 );
                break;
             case "del" : //削除
                stack.pop();
                break;
            default:
                if( isNum(reg1) ){
                    stack.push(parseInt(reg1));
                }else throw new Error("構文にミスがあります");
                break;
        }
    }
    if(stack.length != 1 || !isNum(stack[0]) ) throw new Error("構文にミスがあります");
    return stack.pop();
}

function isNum(num){
    num = parseInt(num);
    return (typeof num == "number");   
}