前回は「数値を引数に持つ関数」を評価し、その値を求めてみました。今回は、関数の引数として関数自体も指定できるようにしてみましょう。つまり、関数の引数を数値のみとするのではなく「数値として評価しうる文字列」とするわけです。この処理は、関数の引数が数値になるまで再帰的に評価関数を呼び出すことで実現できます。
引数の再帰的評価
まず、今回扱う関数は以下のように関数名(関数名(数値))という「関数の中に関数がある」いわば合成関数です。もちろん前回同様引数に数値を取ることもできますし、関数は最終的には数値として評価され、関数の引数として直接処理できるのも数値のみなので、今回の関数も引数として取れるのは「（即値、あるいは評価結果としての）数値」のみ、ということに変わりはありませんが。
| 文字列 | 値 |
|---|---|
| inc(inc(2)) | 4 | sqr(inc(inc(inc(3)))) | 36 |
このような関数を評価するには「一番内側の関数から数値として評価していく」処理が適しているでしょう。たとえば、sqr(inc(inc(inc(3))))なら、
sqr(inc(inc(inc(3)))) sqr(inc(inc(4))) sqr(inc(5)) sqr(6) 36
という形で内側の関数をまず評価し、その評価値の「数値」を引数に一つ外側の関数を評価するわけです。上の例では、「関数の評価」を自明のものとして書いていますが、ある文字列が関数か即値であった場合にその値を評価する関数parse()があったとすれば、以下のようにも書けるでしょう。
sqr(inc(inc(parse(inc(3))))) parsqr(inc(parse(inc(4)))) sqr(parse(inc(5))) parse(sqr(6)) 36
この処理の流れの通りに一番内側の関数を見つけ順次評価していっても良いのですが、それだと最初に関数が何階層になっているか調べないといけませんね。さらに、その階層のどこまで評価したのか自分で管理しながら評価していかなくてはならず処理が複雑になってしまいます。そこで、「現在評価している文字列の一番外側の関数（上の例の最初ではsqr()）」に注目して、その引数がさらに関数になっているならその引数の関数で再帰的に自分自身（parse()）を呼び出すようにしましょう。
具体的には、評価関数parse()を以下のような流れにします。
- 渡された文字列が関数か即値として評価可能であれば、受理
- 渡された文字列が即地か即値を引数に持つ関数であれば、その評価値を返す
- 渡された文字列が関数でその引数も関数（func2）なら return parse(関数名(parse(func2)))
これでparse()では、引数がすぐに評価可能か、あるいはさらに自分自身に渡すか判断するだけなので、何階層になっているか意識する必要はなくなります。parse()が自分自身を呼び出す度に自分自身に渡す文字列の階層が確実に一つ減って、やがて一番内側に達すれば数値の評価を得られるからです。後は、再帰から戻っていく過程で内側の評価値が順次外側の関数の引数に適用され評価されていきます。
たとえば、inc(inc(2))という文字列をparse()に渡すと、inc(inc(2))は関数（関数）という形なので
return parse(inc(parse(inc(2))))
というreturn文が実行されます。この文では、最初に外側のparse()に渡す引数を評価するため内側のparse(inc(2))が実行されて3という評価値が戻ってくるので、parse(inc(2))の部分が3に置き換わり
return parse(inc(3))
となりますね。このparse(inc(3))は4という評価結果を返し、その評価結果がそのままreturnされてparse()の最終結果である4が得られるわけです。
評価関数の実装
では、評価関数parse()を実装してみましょう。最も重要な数値と引数に数値を持つ関数の評価に関しては前回と同様に行えば良いのですが、今回はparse()の戻り値も文字列にしました。また、文字列が関数であるか判定する処理をisFunc()として、関数の形になっている文字列の関数名と引数部分を取り出す処理をgetFunc()、getArg()として関数化します。
まずisFunc()は、文字列が関数の形になっているか判定するため「正しく対応した()が一組以上あり、最初の(の前に関数名になりうる文字列がある、そして文字列の最後が)で閉じられている」という条件で判定するので、以下のようになります（()の処理はこちらを参照）。
private boolean isFunc(String stArg) {
int len=stArg.length(),n=0,s=0;
boolean bErr=false;
if (len==0)
return false;
if (stArg.charAt(len-1)!=')')
return false;
// ()を検査
for (int i=0;i<len;i++) {
if (stArg.charAt(i)=='(') {
// (が最初にあればエラー
if (i==0)
bErr=true;
else
n=1;
s++;
}
if (stArg.charAt(i)==')')
s--;
if (s<0) // 途中で)の数が(の数を上回ったらエラー
bErr=true;
}
if (bErr || s!=0 || n==0)
return false;
return true;
}
関数名を取り出す処理は「最初の(の前の文字列」を取り出すだけ、また関数の引数は「一番外側の()内の文字列」なので、getFunc()、getArg()は以下のようになります。
private String getFunc(String stArg) {
int len=stArg.length();
if (!isFunc(stArg))
return "";
for (int i=0;i<len;i++)
if (stArg.charAt(i)=='(')
return stArg.substring(0,i);
return "";
}
private String getArg(String stArg) {
int len=stArg.length();
if (!isFunc(stArg))
return "";
for (int i=0;i<len;i++)
if (stArg.charAt(i)=='(')
return stArg.substring(i+1,len-1);
return "";
}
これで、関数や数値に関する検査・評価、さらに関数の要素切り分けができるようになりました。あとは、「渡された文字列が数値か引数に数値を取る関数ならその値を評価して返し、引数に関数を持つ関数なら引数の関数で再帰呼び出しを行う」parse()を以下のように書くだけです。
private String parse(String stArg) { // 文字列の構文を検査し評価
if (isNum(stArg)) // 数値なら、その値を返す
return String.valueOf(parseNum(stArg));
if (!isFunc(stArg)) // 数値でも関数でもなければエラー
return "Error";
String stStr=getArg(stArg); // 関数の引数取得
if (stStr.length()==0)
return "Error";
if (isFunc(stStr)) // 関数の引数が関数なら、再帰呼び出し
return parse(getFunc(stArg)+"("+parse(stStr)+")");
if (isNum(stStr)) { // 関数の引数が数値なら、評価
String stFunc=getFunc(stArg);
int arg=parseNum(stStr);
if (stFunc.equals("inc"))
return String.valueOf(arg+1);
if (stFunc.equals("sqr")) {
return String.valueOf(arg*arg);
}
return "Error";
}
プログラム
実行したら左側のString入力欄に文字列を入力し、=ボタンをクリックしてその文字列を評価してみてください。使用可能な構文は、数値列と関数で、関数は前回同様inc()とsqr()が使用できます。
実行すると結果が右側に表示され、下のテキストエリアには、
呼び出された回数:arg:渡された文字列 return:returnされた文字列
という形でparse()の呼び出し履歴が表示されるので、再帰の過程を確認してみましょう。
実行例
String sqr(3) = 9 1 - arg:sqr(3) return:9
数値や引数に数値を持つ関数は、前回同様そのまま評価されます。
String inc(sqr(3)) = 10 1 - arg:inc(sqr(3)) return:parse(inc(parse(sqr(3))) 2 - arg:sqr(3) return:9 3 - arg:inc(9) return:10
この例では、inc()の引数であるsqr(3)が再帰呼び出しで評価され（2）、その評価値9によって呼び出されたparse("inc(9)")の結果が返されます（3）。
String sqr(inc(sqr(3))) = 100 1 - arg:sqr(inc(sqr(3))) return:parse(sqr(parse(inc(sqr(3)))) 2 - arg:inc(sqr(3)) return:parse(inc(parse(sqr(3))) 3 - arg:sqr(3) return:9 4 - arg:inc(9) return:10 5 - arg:sqr(10) return:100
この例では、2で一番内側の関数sqr(3)に達し、3以降で内側から外側の関数に向かって評価されて行っています。