4

括弧のない分流場アルゴリズムを実装しようとしていますが、理解できません。私はウィキペディアを試しましたが、エントリは本当に悪いです. コードの実装にはほとんど問題がないはずですが、取得できない場合は実装できません。

さて: このアルゴリズムはどのように機能しますか?

これが私が理解していることです：

  • 左から右へ、すべての数値が出力キューに追加され、すべてのオペランドがスタックに追加されます。最後に到達したら、すべてのオペランドをポップして出力に追加します

    Expression: 2+5*4+3/5   ( = 2+20+0.6 = 22.6 )

Stack: +*+/             ( -> top )

OutputQueue: 5 3 4 5 2  ( -> exits)

次に、スタックをポップしてキューに追加します

    OutputQueue: (insert ->) + * + / 5 3 4 5 2   ( -> exit)

私が理解している限り、フォームは次のようになります: 25435/+*+

試して解決しましょう：

    5/3 ~ 1.6 + 4 ~= 5.6 * 5 ~= 28 + 2 ~= 30 (or 30.3 recurring .3 if you insist)

編集:ここで使用した逆ポーランド記法は正しいと確信しているため、問題になることはありません。

私は自分が愚かなことをしていることを知っていますが、私の人生ではそれを理解することはできません.

ウィキペディアからのものであり、他の人が私にそれを指摘しているのを見たので、アルゴリズムは優れているはずなので、誰かが私のロジックのエラーを指摘できれば、それが最も役立つと思います。どこかで何かを台無しにしているだけです。

それはキューですか？私は逆ポーランド記法を十分に扱っていると確信しています。

4

2 に答える 2

4

間違えている ：

Expression: 2+5*4+3/5

トークンごとに：

    token : 2
    outputqueue 2
    stack

    token : +
    outputqueue 2
    stack +

    token : 5
    outputqueue 25
    stack +

    token : "*" 
    "*" has higher predencence as "+", so we push into the stack
    outputqueue 25
    stack +*

    token : 4
    outputqueue 254
    stack +*

    token : "+"
    "+ "has lower predencence as "*", we pop "*" from the stack.
    "+" has same predecence as "+", so we pop "+" from the stack then add the current  token "+" in the stack
    outputqueue 254*+
    stack +

    token : 3
    outputqueue 254*+3
    stack +

    token : "/"
    "/" has lower predencence as "+", we push "/" into the stack
    outputqueue 254*+
    stack +/

    token : 5
    outputqueue 254*+35
    stack +/

式が終了しました。スタックをポップします。

output 254*+35/+

計算：

5*4 = 20
2+20 = 22
3/5 = 0.6
22 + 0.6 = 22.6
于 2012-06-11T11:41:46.313 に答える
2

あなたが望むアルゴリズムがこれほど単純かどうかはわかりません。リンク先の wiki 記事全体を読みましたか? 具体的には、セクション「アルゴリズムの詳細」を参照してください。演算子の優先順位について多くを扱っていますが、現在の実装では破棄していると思います。私の提案は、箇条書きに従って (そして必要に応じて以下の例と比較しながら) そのセクションを一度に 1 ステップずつ見ていき、この問題の適切な形式を考え出すことです。それができれば、アルゴリズム全般の理解に役立つはずです。

于 2012-06-11T11:38:39.503 に答える