Cで簡易コマンドライン関数電卓を作ってみた
ご無沙汰しておりました。東に進んだら村を発見したので、とりあえず余していた小麦で交易を始めたぞはるです。
今回は研究をしていたと思ったらいつの間にか構文解析器を作っていたので、どんな感じに仕上がったかを紹介したいと思います。情報系でもないのに何をしているんでしょうね。
設計方針
当初はちゃんと数式を意味を持つ要素ごとに分割した上で構文木を形成し、解析を行うつもりでした。しかし、思った以上に難易度が高く、Cで実装する方法もまるで見当がつかなかったので、今回はかなり簡単な方法を取ることにしました。
以下では実際に与えられた文字列
SIN(t + SIN(t + SIN(t+SIN(t)))) + COS(t)^2
を例として、これに対しての処理を示します。
空白を削る
SIN(t+SIN(t+SIN(t+SIN(t))))+COS(t)^2
まずは色々と邪魔なので表示できない文字(スペースとか、タブとか)を削ってしまいましょう。
両端の括弧を外す
これも数式の解釈には余計なものなので外してしまいましょう。今回は特に外すところはありませんね。
数式を解釈する
ここからが本番です。デカルトさんは「困難は分割せよ」と言いました。一見複雑に見える数式でも部分に分けて考えれば単純な処理で計算できそうですよね。というわけで数式を計算しやすい形に分割してみましょう。
私の採用した方法では、数式の解釈は再帰的な項への分割によって行われ、その優先順位は
- 括弧に囲まれていない加算、減算記号で数式を分割し、その両端を解釈する
- 括弧に囲まれていない乗算、除算記号で数式を分割し、その両端を解釈する
- 括弧に囲まれていないべき乗記号で数式を分割し、その両端を解釈する
- 数式を単項として評価する
となっていて、番号の小さい方の処理から順番に実行されます。
与えられた例に対する再帰的な処理を文章で説明するのは私の日本語運用能力の限界を越えています。ですので、代わりに処理の概要を表した図を用意しました。こんな感じです。この木構造の葉の部分には変数であるtと数しか残っていないところがポイントです。根に向かうにつれてそれらの計算結果が組み合わされていき、最終的に数式全体の計算結果となることがこの数式解釈の目的です。
これをPythonやRubyを用いて実装できる人はそちらで実装するのが一番だと思います。私は両方共使えるとは言い難いので。
この後は、よりにもよってC/C++でどのように「空白文字・括弧の除去、文字列の分割、数式の評価・関数の評価」を行ったのか、について説明したいと思います。
プログラム解説
このプログラムに全文コピペするような価値はないと思うので、関数ごとに掲載して解説しようと思います。(全体的にcharポインタを多用しているので、ポインタにアレルギーのある人は注意です)
空白を取り除く
char* removeEscapes(const char* src) { // 新しく文字列を確保する char* dst = (char*)malloc(sizeof(char) * (strlen(src) + 1)); int count = 0; // コピー元の文字列に終端文字(\0)または改行(\n)が出るまで繰り返す while(*src != '\0' && *src != '\n') { if(*src >= '!' && *src <= '~') { *dst = *src; // 表示可能文字ならコピーする dst++; // コピー先のポインタを進める count++; // コピーした文字数を増やす } *src++; // コピー元のポインタを進める } *dst = '\0'; // 終端にはヌル文字を入れておく return (char*)(dst - count); // コピー先の文字列の先頭の位置を返す }
半角スペースに限らず表示することのできない文字は全て取り除く処理にしています。一応、引数でポインタは与えられているので文字をちまちまと詰めていくことはできるのですが、面倒くさいので新しく確保した文字列に表示することのできる文字だけをコピーするようにしています。メモリリーク?基本的に一回しかしない処理なので多分耐えるでしょう。
両端の括弧を取り除く
char* removeBrackets(char* src) { if(*src != '(') return src; // 先頭が括弧でないならそのままポインタを返す。 else { char* cursol = src; while(*cursol != '\0' && *cursol != '\n') { cursol++; } if(*(cursol - 1) != ')') { // 後ろにだけ括弧がある状況はおかしい fputs("[ERROR] Unclosed brackets\n", stderr); abort(); return NULL; } else { // 正常な(先頭と末尾に括弧がある)場合 *(cursol - 1) = '\0'; // 括弧の部分をヌル文字に変えて return (src + 1); // 先頭から2文字目のアドレスを返す } } }
文字列の分割
char* splitByOperator(char* src, char o) { int n_brackets = 0; // 括弧に囲まれていない演算子にたどり着くまで繰り返す while(*src != o || n_brackets != 0) { if(*src == '\n' || *src == '\0') // 終端に到達した場合 return NULL; // 右側はnull else if(*src == '(') // 括弧に入る n_brackets++; else if(*src == ')') // 括弧から出る n_brackets--; src++; // ポインタを進める } *src = '\0'; // 演算子をヌル文字に置き換える(左側) return (src + 1); // 演算子の1つ右のポインタを返す(右側) }
文字列の分割に関しては結構考えました。最後の二行がその結果です。こういう処理を書いていると、やっぱりポインタを使ったプログラミングは楽しいなぁとなります。
数式の解釈
ここがプログラムの核です。express()関数の中からexpress()関数を呼び出していることが解ると思います。これが再帰処理ですね。そのまま愚直に書いたので、細かい部分に目を向ける必要はあまりありません。
double express(char* function, double t) { if(function == NULL || strlen(function) == 0) { fputs("\"function\" is empty or null string\n", stderr); abort(); } char *left = function; char *right; left = (char*)malloc(sizeof(char) * (strlen(function) + 1)); strcpy(left, function); left = removeBrackets(left); // 両端の括弧を取る if(strlen(left) == 0) { // 括弧の中身が空だった場合エラーを返す fputs("[ERROR] There is empty brackets\n", stderr); abort(); return 0; } else { // 演算子で数式を分割する right = splitByOperator(left, '+'); // 加算 if(right != NULL) return express(left, t) + express(right, t); right = splitByOperator(left, '-'); // 減算 if(right != NULL) return express(left, t) - express(right, t); right = splitByOperator(left, '*'); // 乗算 if(right != NULL) return express(left, t) * express(right, t); right = splitByOperator(left, '/'); // 除算 if(right != NULL) return express(left, t) / express(right, t); right = splitByOperator(left, '^'); // べき乗 if(right != NULL) return pow(express(left, t), express(right, t)); else{ // 演算子によって分割できなくなった switch(left[0]){ // 最小単位が変数である場合 case 't': // 変数の値を返す return t; break; // 最小単位が数字である場合 case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': // 数字を数に変換して返す return atof(left); break; // それ以外の場合 default: // 有効な関数名であればその計算結果を返す return mathfunc[detect(left)](express(left + 3, t)); break; } } } free(left); }
関数の評価
関数ポインタを使うことで今後の拡張性をギリギリ確保できた気でいます。
// 関数ポインタの配列 double (*mathfunc[])(double) = { sin, cos, tan, log, exp }; // 配列にアクセスするための添字一覧 enum Func { SIN, COS, TAN, LOG, EXP, ERR }; // 与えられた式の先頭が関数かどうかを判定し、関数である場合は適切な参照番号を返す Func detect(char *src) { if(strncmp(src, "SIN(", 4) == 0)return SIN; else if(strncmp(src, "COS(", 4) == 0)return COS; else if(strncmp(src, "TAN(", 4) == 0)return TAN; else if(strncmp(src, "LOG(", 4) == 0)return LOG; else if(strncmp(src, "EXP(", 4) == 0)return EXP; else { fputs("[ERROR] Invalid function name\n", stderr); abort(); return ERR; } }
これから使う関数を増やしたい場合はそこの条件分岐に一行付け足せばいいのでしょうか、もうすこしスマートな書き方があったような気がします。ちなみにこの関数ポインタをどのように呼び出しているかというと、一つ前に紹介したexpress()関数のswitch文の中で
default: // 有効な関数名であればその計算結果を返す return mathfunc[detect(left)](express(left + 3, t)); break;
のようにしています。先に角括弧で添字を指定して、次に丸括弧で引数を渡すのが決まりみたいですね。
動作確認
main()関数をこのように書いて、プログラムを実際にテストしてみました。コマンドラインから計算させたい関数、tの最小値、tの最大値、サンプリング数を指定します。
int main(int argc, char **argv) { char *src;、 int N; double t, tmin, tmax, step; if(argc < 5) { printf("Usage: %s [function] [min t] [max t] [sampling level]\n" "\tfunction: This is the function you wanna sample\n" "\tmin t: minimum t value\n" "\tmax t: maximum t value\n" "\tsampling level: 2^(2^N) points will be sampled\n", argv[0]); return -1; } src = removeEscapes(argv[1]); tmin = atof(argv[2]); tmax = atof(argv[3]); N = atoi(argv[4]); step = (tmax - tmin) / pow(2, pow(2, N)); for(t = tmin; t < tmax; t += step) { printf("%f, %f\n", t, express(src, t)); } return 0; }
次に示すコマンドで計算結果をテキストファイルに出力します
$ ./a.out 'SIN(t+SIN(t+SIN(t)))+COS(2*t)' '-3.141592' '3.141592' '3' > result.txt