CodeIQ：「そのeval、本当に安全ですか？」

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「そのeval、本当に安全ですか？」（CodeIQ）を参照してください。

問題の概要

簡単に言うと、eval()に渡す式の安全性を確保してください、と言う問題です。
主なポイントは次の通りです。

一般的な数式と同様に、被演算子（値や変数）の間に演算子を書く中置記法
乗算は加減算より演算の優先順位が高い。
数式に記法上のエラーがある場合（括弧閉じ忘れや、引数指定が不正など）は、"Unknown syntax"と出力する。

未定義の変数や関数を呼び出した場合は、"Unknown name"と出力する。
後述する変数及び関数以外は、たとえそれが一般的に用いられる機能であっても、必ず未定義として解釈すること。

種類	名前	戻り値
変数	two	2
関数	mod(x,y)	第一引数(x)を第二引数(y)で割ったときの余り
関数	sumsq(x, ...)	可変個の引数すべての平方根（２乗）の和 ← 問題文がおかしいけれど2乗の和を求める

私のプログラム

JavaScript(Node.js)で解答しています。

process.stdin.resume();
process.stdin.setEncoding('utf8');

var List = Array();

var DefVals = {
    "two": "2",
}

var DefFuncs = {
    "mod":true,
    "sumsq":true,
}

var DefNames = {};

function addDefNames(arg){
    for(var key in arg){
        DefNames[key] = arg[key];
    }
}

function checkDefName(str){
    // 数字を全て取り除く
    var l = str.replace(/\d/g, "");

    // +-*/(),を全てスペースに置換する（関数名だけがスペース区切りで残る）
    l = l.replace(/[\+\-\*\/\(\),]/g, " ").trim();
    l = l.replace(/\s+/g, " ");

    var n = l.split(" ");
    for(var i=0; i<n.length; i++){
        n[i] = n[i].trim();
        if(!n[i]){continue;}

        if(!DefNames[n[i]]){
            console.log("Unknown name");
            return false;
        }
    }

    return true;
}

function execFomula(str){
    try{
        var ret = eval(str);
        if(typeof ret === "number" &apm;& !isNaN(ret)){
            console.log(ret);
        }
        else if(isNaN(ret)){
            console.log("Unknown syntax");
        }
        else{
            console.log("Unknown syntax");
        }
    }
    catch(e){
        //console.log(e);
        console.log("Unknown syntax");
    }
}

function mod(a,b){
    var ra = eval(a);
    var rb = eval(b);
    return ra % rb;
}

function sumsq(){
    var sum = 0;
    for(var i=0; i<arguments.length; i++){
        var a = eval(arguments[i]);
        sum += a*a;
    }
    return sum;
}

function replaceDefVals(str){
    var syntax = str;
    for(var key in DefVals){
        var regex = new RegExp(key , "g");
        syntax = syntax.replace(regex, DefVals[key]);
    }
    return syntax;
}

process.stdin.on('data', function (chunk) {
    var lines = chunk.toString().split('\n');
    for(var i=0; i<lines.length; i++) {
        var input = lines[i].trim();
        if(!input){
            continue;
        }

        List.push(input);
    }
});

process.stdin.on('end', function () {
    addDefNames(DefVals);
    addDefNames(DefFuncs);

    for(var i=0; i<List.length; i++){
        var l = List[i];
        var ok = checkDefName(l);
        if(ok){l = replaceDefVals(l);}
        else {continue;}
        execFomula(l);
    }
});

解説

私の解答はおそらく出題者の意図している正攻法ではありません。
まともにやるならば入力値から構文木を作って解析するのでしょうが、違う手段を用いています。

基本的な考え方

大きな処理の手順は次の通りです。

入力値をチェックする(使用可能な名前だけが使われているかをチェックする)
正しければ入力値を実行する

入力チェックでは不正な関数名、変数名が存在しないことだけをチェックしていて、構文として正しいかは実行可能かどうかで判断しているというのがこのプログラムの特徴です。

チェック用定数

次の3つの大域変数がチェック用の変数です。

DefVals: 定数
DefFuncs: 関数
DefNames: 上の2つをまとめたもの

addDefNames()でDefNamesにDefValsとDefFuncsに含まれる名前を登録しています。

構文チェック

checkDefName()で構文をチェックしています。
手順は次の通りです。具体例をあげながら説明します。
例えば、次のような入力があったとします。

mod(7, two+1) + sumsq(1,2,3)

入力値1行から数字を取り除く
この問題の場合、関数や定数名には数字が含まれません。そのため、数字は常に許される入力値なので無視できます。結果、入力値は次のようになります。

mod(, two+) + sumsq(,,)
+-*/(),を全てスペースに置換する
次に演算子とカッコをスペースに置換します。結果として関数か定数だけがスペース区切りで残ります。スペースが2つ以上連続する部分ができるので2個以上の連続するスペースを1つにします。結果、入力値は次のようになります。

mod two sumsq
スペースで分割してDefNamesに登録されている名前かをチェックする
これまでの手順で残った文字列は関数名か変数名なので使用可能な名前かをチェックします。これはあらかじめ作ったDefNamesに文字列があるかどうかで判断できます。 DefNamesに未登録ならエラーとして終了します。

定数を置き換える

replaceDefVals()で定数を数値に変換しています。
今回は問題ありませんでしたがこの処理は問題があります。もし、「divide_by_two」のような置換対象が別の文字列の部分文字列になっているパターンがあったら正しい結果にはなりません。演算子とカッコで分割してから置換して再度式を構成するなどの処理にする必要があります。

引数を実行する

execFomula()で引数を実行しています。ここに至るまでに、使用できない関数名、変数名が含まれる場合はエラーになっているので組み込み関数のようなものが含まれる式が実行されることはありません。
そして、式自体が正しければきちんと実行されることになります。逆に言うと式自体がおかしい（ex：カッコが正しく対応していない、など）の場合は47行目のeval()がエラーになるのでeval()がエラーになった＝「unknown syntax」ということになります。

mod(a,b)とsumsq(args...)

これらは基本的に仕様通りの計算をするだけですが、私の実装方法では若干の工夫が必要です。
つまり、次のような入力を考慮しなければなりません。

mod(mod(7,4), 2)

関数の引数に別の関数の結果を受け取るような場合を考慮しないといけません。
そのため、引数をそれぞれ再帰的にeval()に渡し、その結果を計算するようにしています。

雑感

以上が私のプログラムの説明です。
今回の問題のように限定的な入力なら私の方法でも大丈夫でしょうが、拡張性などを考えるとこの方法はあまり良くないでしょう。特に、使用可能な関数を全て私の実装のように実装しなければならないのが問題です。
きちんと構文木を作って処理すれば単なる関数呼び出しにできるはずなので、やはり正攻法でやるのが一番いいような気がします。