表現の評価

Question

私は表現評価プログラムをやっています。ちょうどthisのようです。私の問題は、操作の優先順位をどのように処理するのか分かりません。

Evaluate("2 + (3 * 5)") 

自体を再呼び出し、このようでしょう：今

Evaluate("3 * 5") 

、そこから私はこのように、括弧の最も内側のカップルを見つけて、見つけたときに、それらの内側に式を解くために再帰を使用しましたはかっこではなく、結果を計算して別の時間を呼び出します。

Evaluate("2 + 15") 

いいえ、戻り値は期待どおり17です。私はEvaluate("2 + 3 * 5")を呼び出す場合でも、結果は次のとおりです。明らかに間違っている

Evaluate("2 + 3 * 5") 
Evaluate("5 * 5") 

。
基本的に私は操作を左から右に解決しています。どのようにして最初に実行する必要がある操作を選択できますか？私は、すべての操作を囲む括弧をいくつか追加することを考えていましたが、それほど良く見えません。
それでは、まず式全体を解析する必要がありますか？別の方法がありますか？

Answer 1

最高優先順位の演算子を検索し、最初に実行してから次に進みます。したがって、+と*のみを持つ場合は、*のインスタンスを検索し、部分文字列aaaa * bbbbをaaaa * bbbbの値に置き換えます。そのようなインスタンスが残っていなければ、+で作業してください。

特定の演算子内での順序が重要な場合（たとえば、^を含む場合）、それらの演算子で開始する場所を決定する必要があります。

Answer 2

Antlrを.netで使用してこのようなことを行う方法を示す良い記事です。

http://www.codeproject.com/KB/recipes/sota_expression_evaluator.aspx

あなたのパーサを書く手にしたいように聞こえるが、これはあなたがこれを正しく行う方法を確認するために必要なすべてを提供します。

基本的には、式を一連の可能な操作として定義し、各操作が次のレベルで機能するように優先順位を設定します。操作の優先順位は、このシーケンスの順番でエンコードされます。

など。 '+'と '*'を持つ非常に単純な例

additiveExpression: multiplicativeExpression '+' multiplicativeExpression 
multiplicativeExpression: number '*' number 

あなたの手書きの再帰的降下パーサーは、最初のルールから始まり、動作します。

Antlrを使用してこのような非常に単純な文法を作成し、生成するコードを確認することができます。この場合、非常に短いコードになります。

文法が複雑になる場合は、とにかくAntlrのようなツールを使用することをお勧めします。構文解析コードの重い部分が多く取り除かれています。数百回も前に行われ、非常に機械的です。それは、あなたが表現でやりたい興味深いものに集中することになります。

Answer 3

とにかく繰り返す必要があります。だからあなたが+を見るときでさえ、あなたは反復しなければならない。本質的には、括弧を持たないバイナリ演算子はすべてそれを持つものとして扱わなければなりません。

2 + 3 * 5は実際には2 +（3 * 5）です。

Answer 4

ポーランド語表記の使用に役立つものはhttp://en.wikipedia.org/wiki/Polish_notation#Computer_programmingです。この表記法は、かっこを必要とせず、操作の順序に役立ちます。

これは、この種の表現を評価するアルゴリズムがあることがうれしいです。また、中置式を接頭辞または接尾辞の式に変換することもできます。

は、ここでそれを行うことができる方法の例です - あなたの例「2 + 3 * 5」を取ることができます：

2 + 3 * 5 
b = 3 * 5 
    -convert b- 
b = * 3 5 
2 + b 
    -convert expression- 
+ 2 b 
    -expand b- 
+ 2 * 3 5 

私はこれらの変換をした回の最初のカップルは、私は非常にそれらによって混乱していたが。それがあなたにもあてはまるならば、威圧されずに練習を続けてください。いいのは、この変換を行うのに役立つアルゴリズムを見つけることができるので、少し助けてくれることです。

この変換を行うことの大きな利点は、変更された式を左から右に評価できることです。アルゴリズムは次のように実行されます。

オペレータ用とオペランド用の2つのスタックを維持します。 左から右からの評価：

1. あなたがオペレータに実行する場合は、あなたがした場合はオペレータスタック
2. にプッシュし、オペランド（数が）一度
3. オペランドスタックにプッシュ一番上の演算子（ほとんどの場合2つ）に十分な数のオペランドを見つけ、演算子を見て2つのオペランドに対してその演算を実行します。
4. ステップ＃3の結果をオペランドスタックにプッシュします。

私はいくつかのことをあまり単純化しておらず、いくつかの手順を逃している可能性がありますので、これは出発点としてのみ使用してください。私はスキップした/細かいことは覚えていない。その中には、バイナリや単項演算子、カッコをどのように扱うのか、力の評価を扱う方法などがあります。

・ホープ、これは[簡単な式パーサを書く]の可能な複製を助け、幸運:)