数学パーサーの賢い設計?

StackOverflow https://stackoverflow.com/questions/114586

  •  02-07-2019
  •  | 
  •  

質問

数学パーサーを設計する最も賢い方法は何でしょうか?私が言いたいのは、数学文字列を受け取る関数です (次のようなもの)。"2 + 3 / 2 + (2 * 5)") を計算して返しますか?私は何年も前に VB6 でこれを作成しましたが、結局は肥大化してしまい、移植性があまり高くありませんでした (さらに言えば、賢明でもありません...)。一般的なアイデア、疑似コード、または実際のコードを歓迎します。

役に立ちましたか？

解決

かなり優れたアプローチには 2 つのステップが含まれます。最初のステップは次のとおりです。 式を中置文字から後置文字に変換する （例えば。経由 ディクストラの操車場）表記です。それが完了したら、次のように書くのは非常に簡単です。 後置評価器.

他のヒント

私は数学パーサーの設計についていくつかのブログ投稿を書きました。一般的なものがあります 導入, に関する基礎知識 文法, Rubyで書かれたサンプル実装 そして テストスイート. 。おそらくこれらの資料が役に立つでしょう。

いくつかのアプローチがあります。動的コードを生成して実行すると、多くのコードを記述することなく、答えを得ることができます。.NET でランタイム生成コードを検索するだけで、たくさんの例が見つかります。

あるいは、実際のパーサーを作成し、式の評価に使用される小さな解析ツリーを生成することもできます。これも基本的な式としては非常に簡単です。codeplex には数学パーサーがあると思うので、そこをチェックしてください。または、例が含まれる BNF を検索してください。コンパイラーの概念を紹介する Web サイトには、基本的な例としてこれが含まれています。

Codeplex 式評価器

これが古いことは知っていますが、より大きなアプリの一部として電卓を開発しようとしてこれに遭遇し、受け入れられた回答を使用するといくつかの問題に遭遇しました。これらのリンクは、この問題を理解して解決するのに非常に役立ちましたので、軽視すべきではありません。私は Java で Android アプリを作成していて、式「文字列」の各項目について、ユーザーがキーパッドで入力するときに実際に String を ArrayList に保存しました。中置から後置への変換では、ArrayList 内の各文字列を反復処理し、新しく配置された文字列の後置 ArrayList を評価しました。これは、少数のオペランド/演算子では素晴らしかったですが、特に式が非整数に評価され始めたとき、より長い計算は一貫してオフになりました。提供されたリンクで、 インフィックスからポストフィックスへの変換, 、スキャンされた項目が演算子であり、topStack 項目の優先順位が高い場合は、スタックをポップすることを提案します。これはほぼ正しいことがわかりました。スキャンされた演算子の優先順位が高いか等しい場合に、topStack 項目をポップすると、最終的に計算が正しくなりました。この問題に取り組んでいる人の助けになれば幸いです。貴重なリンクを提供してくれた Justin Poliey (そしてFAS?) に感謝します。

「常時オン」アプリケーションがある場合は、数学文字列を Google に投稿して、結果を解析するだけです。シンプルな方法ですが、それが必要なものかどうかはわかりませんが、ある意味賢い方法だと思います。

関連する質問 方程式 (式) パーサーに優先順位はありますか? これを始める方法についての良い情報もいくつかあります。

-アダム

入力が文字列形式の中置式であると仮定すると、それを次のように変換できます。 接尾辞 そして、スタックのペアを使用します。演算子スタックとオペランド スタック、そこからソリューションを実行します。一般的なアルゴリズム情報については、Wikipedia のリンクを参照してください。

ANTLR は、非常に優れた LL(*) パーサー ジェネレーターです。強くお勧めします。

開発者は常にクリーンなアプローチを望んでおり、解析ロジックを一から実装しようとしますが、通常は最終的に次のようになります。 ディクストラ操車場のアルゴリズム. 。結果として、コードはきれいに見えますが、バグが多い可能性があります。このようなAPIを開発しましたが、 JMEP, これだけですべてが完了しますが、コードが安定するまでには何年もかかりました。

これだけの作業が完了した後でも、そのプロジェクト ページからでも、JavaCC または ANTLR の使用に切り替えることを真剣に検討していることがわかります。

この質問がなされたときから 11 年後の未来:車輪の再発明をしたくない場合は、世の中には珍しい数学パーサーがたくさんあります。

何年も前に私が書いたものがありますが、これは四則演算、方程式の解き方、微分積分、積分計算、基本統計、関数/式の定義、グラフ作成などをサポートしています。

それは呼ばれています パーサーNG そしてそれは無料です。

式の評価は次のように簡単です。

    MathExpression expr = new MathExpression("(34+32)-44/(8+9(3+2))-22"); 
    System.out.println("result: " + expr.solve());

    result: 43.16981132075472

または、変数を使用して単純な式を計算します。

 MathExpression expr = new MathExpression("r=3;P=2*pi*r;"); 
System.out.println("result: " + expr.getValue("P"));

または関数を使用します。

MathExpression expr = new MathExpression("f(x)=39*sin(x^2)+x^3*cos(x);f(3)"); 
System.out.println("result: " + expr.solve());

result: -10.65717648378352

または、指定された点で導関数を評価するには (数値近似の誤差によって精度が制限されないように、舞台裏で (数値ではなく) 記号的な微分が行われることに注意してください)。

MathExpression expr = new MathExpression("f(x)=x^3*ln(x); diff(f,3,1)"); 
System.out.println("result: " + expr.solve());

 result: 38.66253179403897

何が違うのか x^3 * ln(x) x=3 で 1 回。差別化できる回数は今のところ1回です。

または数値積分の場合:

MathExpression expr = new MathExpression("f(x)=2*x; intg(f,1,3)"); 
System.out.println("result: " + expr.solve());

result: 7.999999999998261... approx: 8

このパーサーはかなり高速で、他にも多くの機能を備えています。

Objective C へのバインディングを介して Swift に移植する作業が完了し、他の反復的なユースケースの中でグラフ作成アプリケーションに使用しました。

免責事項:ParserNG は私が作成しました。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top