3

私はこのように式評価プログラムをやっています。私の問題は、操作の優先順位を処理する方法がわからないことです。再帰を使用して、最も内側の括弧のペアを見つけ、見つかったら、次のようにそれらの中の式を解決します。

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

次のように自分自身を再呼び出しします。

Evaluate("3 * 5")

ここでは、括弧がないため、結果を計算し、もう一度自分自身を呼び出します。

Evaluate("2 + 15")

わかりました。期待どおり、戻り値は 17 です。しかし、私が呼び出すとEvaluate("2 + 3 * 5")、結果は次のようになります。

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

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

4

4 に答える 4

2

役立つ可能性があるのは、ポーランド記法の使用です：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つは演算子用、もう1つはオペランド用です。左から右への評価：

  1. オペレーターに遭遇した場合は、オペレータースタックにプッシュします
  2. オペランド（数値）に遭遇した場合は、オペランドスタックにプッシュします
  3. 最上位の演算子（ほとんどの場合2つ）に十分なオペランドが見つかったら、演算子を調べて、2つのオペランドに対してその操作を実行します。
  4. 手順3の結果をオペランドスタックにプッシュします。

私はいくつかのことを単純化しすぎて、いくつかのステップを逃したかもしれないので、これを出発点としてのみ使用してください。私がスキップした/たくさん覚えていない詳細があります。それらのいくつかには、演算子のバイナリまたは単項、括弧の処理方法、累乗の評価の処理方法などが含まれます。

これがお役に立てば幸いです:)

于 2011-01-16T20:20:26.920 に答える
2

これは、Antlr と .net を使用してこの種のことを行う方法を示す素晴らしい記事です。

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

パーサーを手書きしたいように思えますが、これで、これを正しく行う方法を確認するために必要なすべてが得られます。

基本的に、式を可能な操作のシーケンスとして定義することにより、優先順位を実装します。各操作は次のレベルの下で動作します。操作の優先順位は、このシーケンスの順序でエンコードされます。

たとえば、「+」と「*」を使用した非常に単純な例

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

手書きの再帰降下パーサーは、一番上のルールから始まり、下に向かって進みます。

Antlr を使用して、このような非常に単純な文法を実行し、それが生成するコードを確認できます。この場合、非常に短いコードになるため、非常に簡単に理解できます。

グラマーが複雑になる場合は、とにかく Antlr のようなツールを使用することをお勧めします。これは、解析コードの多くの重労働を取り除くためです。これは、何百回も行われている種類のものです。前と非常に機械的です。式でやりたい興味深いことに集中することができます。

于 2011-01-16T19:35:42.300 に答える
1

とにかく再帰する必要があります。したがって、+ が表示された場合でも、再帰する必要があります。本質的に、括弧を持たないすべての二項演算子は、括弧を持つものとして扱わなければなりません。

2 + 3 * 5 は、実際には 2 + (3 * 5) です。

于 2011-01-16T19:35:45.410 に答える
0

最も優先度の高い演算子を検索し、最初にそれを実行してから次に進みます。したがって、+ と * しかない場合は、* のインスタンスを検索し、部分文字列 aaaa * bbbb を aaaa * bbbb の値に置き換えます。そのようなインスタンスがなくなったら、+ に取り組みます。

特定の演算子内の順序が重要な場合 (たとえば、^ を含める場合)、それらの演算子をどこから開始するかを決定する必要があります。

于 2011-01-16T19:36:04.350 に答える