6

私はwikiページを見てきました：http://en.wikipedia.org/wiki/Shunting-yard_algorithm

コード例を使用して最初の部分を作成しましたが、基本的には現在次のように変更できます。

3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3の中へ3 4 2 * 1 5 − 2 3 ^ ^ / +

3 4 2 * 1 5 − 2 3 ^ ^ / +しかし、取得するために使用する方法がわかりません3.00012207

そして、wikiのサンプルコードと説明は私には意味がありません.

誰か3 4 2 * 1 5 − 2 3 ^ ^ / +が答えを評価して生成する方法を説明してください。前もって感謝します。コード例は必要ありません。良い説明または例の内訳だけです。

それは問題ではありませんが、私は .net C# を使用しています。

4

4 に答える 4

9

操車場アルゴリズムの目的は、その出力が逆ポーランド記法であるということです。これは簡単に評価できます。

  • 値を保持するスタックを作成する
  • 逆ポーランド記法入力が残っている間：
    • 入力項目を読む
    • 値の場合は、スタックにプッシュします
    • それ以外の場合は操作です。スタックから値をポップし、それらの値に対して操作を実行し、結果をプッシュします
  • 入力が残っていない場合、式が適切に形成されていれば、スタックに値が 1 つだけあるはずです。これが評価結果です。
于 2011-12-01T16:14:12.090 に答える
8

後置記法は、たとえば HP 計算機で計算を行う方法です。

数字を取得するたびにスタックを保持し、それを一番上に追加します。オペレーターが上部から入力を消費し、結果を上部に追加するたびに

token stack
      *empty*
 3    3         //push numbers...
 4    3 4
 2    3 4 2
 *    3 8       //remove 4 and 2, add 4*2=8
 1    3 8 1
 5    3 8 1 5
 -    3 8 -4
 2    3 8 -4 2
 3    3 8 -4 2 3
 ^    3 8 -4 8
 ...    ...
于 2011-12-01T16:12:48.027 に答える
3

次のように要素3 4 2 * 1 5 − 2 3 ^ ^ / +を左から右に処理します。

  1. 数値を保持するためにスタックを初期化します。
  2. 要素が数値の場合は、スタックにプッシュします。
  3. 要素が演算子の場合、スタックから上位 2 つの要素を削除し、それらの 2 つの要素に演算子を適用して、結果をスタックにプッシュします。

最後に到達すると、スタックには結果となる単一の要素が含まれている必要があります。

于 2011-12-01T16:14:13.890 に答える
2

私はパーティーに少し遅れているようです。

私はその質問を見て、Rosetta Code のいくつかのタスクを書いて話題に乗り出しました。たまたま、このタスクがあなたの求めているものかもしれません。これは、トークンごとに RPN 式の値を計算するときに何が起こるかの注釈付きテーブルを提供します。

その出力のサンプルを次に示します。

For RPN expression: '3 4 2 * 1 5 - 2 3 ^ ^ / +'

TOKEN           ACTION                 STACK      
3     Push num onto top of stack 3                
4     Push num onto top of stack 3 4              
2     Push num onto top of stack 3 4 2            
*     Apply op to top of stack   3 8              
1     Push num onto top of stack 3 8 1            
5     Push num onto top of stack 3 8 1 5          
-     Apply op to top of stack   3 8 -4           
2     Push num onto top of stack 3 8 -4 2         
3     Push num onto top of stack 3 8 -4 2 3       
^     Apply op to top of stack   3 8 -4 8         
^     Apply op to top of stack   3 8 65536        
/     Apply op to top of stack   3 0.0001220703125
+     Apply op to top of stack   3.0001220703125  

 The final output value is: '3.0001220703125'
于 2011-12-03T07:34:36.417 に答える