|
上へ
実行時間計測ラブラリ
EXIF情報ライブラリ
文字式演算
クイックソートライブラリ
多倍長演算ライブラリ
多倍長演算ライブラリⅡ
画像処理ライブラリ
| |
|
文字式演算(FreeFormula) |
|
目次 |
| 最終更新日：2007/05/19
一部修正 |
●概要
文字列で与えられた数式を数値演算し、その値を求める。逆ポーランド形式の式も得られる。
●原理
通常の数式は、中置法で、3 + 5
などと書く。しかし、この書式はコンピュータにとっては処理が困難となるので、後置法(Postfix
form)と呼ばれる方式で表す。3 5 +
となる。この方法では、演算子が現れたら、それ以前の変数をそれで演算することになり、機械的に処理できる。
少し、複雑な例で説明する。
3 + 5 * 7/(8 - 6) → 3 5 7 * 8 6 - / +
- 逆ポーランド数式を頭から検索し、数値であれば、スタックに積む。3,5,7
- 演算子の場合は演算を行う。例では、先ず、*
が現れるので、その前の、5 と 7 を乗算する。この時、演算結果と5.7を置き換える。3,(5*7)
- 8、6は数値なのでスタックに積むだけ。3,(5*7),8,6
- 次に、- があるので、その前の8、6 で演算する。3,(5*7),(8-6)
- / があるが、この場合は、,(5*7)、(8-6) で演算する。3,(5*7)/(8-6)
- 最後に、+ があるので、3 + (5*7)/(8-6) を演算する。
原理の詳細はTipsの逆ポーランドと文字式演算を参照方。
このライブラリでは、更に複雑な、数学関数(単項、二項)も記述できるようにしている。
●特徴
- ライブラリは共有型となっている。
- 初等関数を使った数式を扱える。
- 変数、定数、数学定数を記述できる。
- 数値は全てDouble扱い。
- 一応の文法チェックを行っている。
●技術解説
○処理概要
例では項が一文字であるが、実際には複数文字の集合が最小単位(これをトークンと言う)になっているので、解析処理はやや複雑になる。概ね、以下の手順となっている。
- 与えられた原始数式に不正な文字がないかを調べる。
- 数式を最小単位であるトークンに分解する。
- トークンに隣接するトークンを調べ、文法チェックを行う。
- 二項数学関数f(a,b)であれば、その関数の終端までに、分離符
","
が1個あることを確認する。その他の場合は、不正とする。
- トークン群から逆ポーランド形式の数式にする。
- 逆ポーランド数式と変数配列(数式に現れた変数の一覧)を返す。
- 要求があれば、数式を演算する。
○トークン分解
トークンは、数値、変数、演算子、括弧、分離符、関数などとなる。以下のように、優先度(Priority)と識別番号(TokenID)を定義しており、構造体Tokenで表し、トークン配列(Tokens())のサイズは1000固定としている。これは、以前は動的配列であったが、頻繁に配列の生成/消滅があり、メモリを浪費するので固定長とした。1000トークンあれば、実用上問題はない。
・Priority：大きい方が優先度高い
9 = (
5 = 変数、定数、常数、数値
4 = 関数
3 = ^
2 = * /
1 = + -
0 = )
-1 = # #は内部処理用（ストッパー）
・TokenID
0 = 非因子
1 台 = 括弧
10 台 = 演算子
100 台 = 関数(単項)
200 台 = 関数(二項)
500 台 = 変数X、Y
600 台 = 定数A、B、C、D・・・・
700 台 = 数値(文字列)
800 台 = 常数π、e
・文字列のかぶり｣処理
例えば、A、 Abs、あるいは、Sin、 Sinh
は、頭がかぶっているので、検索は、文字数の多いものを優先して確認する。
・単項演算子処理
+式や -式は単項演算子でもあるので、前後関係より以下のような特殊処理が必要となる。
+ が先頭であるか直前のトークンが、"("、","
であれば、これは単項演算子なので、この + は省く。
- が先頭であるか直前のトークンが、"("、","
であれば、これは単項演算子なので、0 - 式 にする。
○文法チェック
面倒くさい処理であるが、それなりに実装している。全体的、機械的に行える手法が必要である。以下の方法で行っている。
- あるトークンを取りだす。
- 先頭にあっても良いかチェック
- 最後尾にあって良いかチェック
- それが、二項数学関数であれば、関数の終端までをチェックし、(式1,
式2) となっているか確認する。但し、ここでは式１/2の中身まではチェックしない。ここで見つけた正しい
"," のTokenID を 9 にして置く(通常は 3)。
- それが、単項数学関数であれば、関数の終端までをチェックし、(式)
となっているか確認する。但し、ここでは式の中身まではチェックしない。
- 次のトークンを調べ、許可された組み合わせかどうかチェックする。
例えば、+
であれば、次のトークンは、関数、変数、数値、(
のみが許されるなど。
- 途中、"," で、TokeID が 3
のものが見つかれば、不正な"," となる。
- "(" があれば、+1 し、")" があれば、-1
する括弧カウンタを儲け、途中で、カウンタが負になれば、エラーで、最後に、カウンタが
0 でなくてもエラーとする。
○逆ポーランド変換
文法チェックを経たトークン群は、機械的に逆ポランド変換できる。二つのスタック(サイズ1000、Stack()とPostFix())を準備する。スタックは構造体Tokenの配列である。Stack(0)にスタッパを入れておく。
- Tokens()から一つ、トークンを取り出す。
- "("ではなく、この優先度が、Stack()トップの優先度と同じか低い間は、PostFix()にStack()からトークンを移動する。但し、","は無視する。
- 上記が終われば、")"以外をStack()に積む。
- これを繰り返す。
- 全トークンの処理が終われば、Stack()に残存するトークンをPostFix()に移動する。
PostFix() の1から逆ポーランド数式のトークンが格納されている。
|