2

データ構造では、順番に変換し、事前に順序付けされた式をツリーに変換します。ただ、私はポストオーダーが苦手です。

与えられた式についてx y z + a b - c * / -

私が思いついた

                   -
                 /   \
                *     / (divide)
               / \    / \   
              x  +    -  c
                / \  /\
               y  z a  b

左のサブツリーの * がデッキのジョーカーであることを除いて、ほとんどの場合、これは適合するようです。ポスト オーダー トラバーサルでは、最後の文字がツリーの最上位ノードになり、それ以外はすべて下に分岐します。ここで、/ および * 演算子は、反対のノードにある必要があることを意味します。ただし、ツリーをトラバースする場合、* を除くすべてが適合します。これは、左のサブツリーがルートの前のノードまで機能し、次に右のサブツリーに切り替える必要があるためです。

正しい方向へのナッジは高く評価されます。

4

2 に答える 2

3

順番に行きます。まず、スタック全体を再度書き出します。

xyz + ab - c * / -

次に、左から始めて、最初の演算子を探します。それと、スタック内の直前の 2 つのオペランドを少し順序どおりに置き換えます。

x (y + z) ab - c * / -

次の演算子に進みます。

x (y + z) (a - b) c * / -

それから次：

x (y + z) ((a - b) * c) / -

x ((y + z) / ((a - b) * c)) -

x - ((y + z) / ((a - b) * c))

さて、それをツリーにするには、真ん中から始めて (元のスタックの最後の要素であることは既にわかっています)、そこから括弧で囲まれた部分式を外側から内側にぶら下げます。

于 2010-10-14T02:02:29.790 に答える
0

実際には、操作の優先順位をチェックする必要がないため、順序付け後の式を順番に解析するプログラムよりも、順序付け後の式を解析するプログラムを作成する方が簡単です。

これを試してください：スタックを作成し、見つけたらオペランドを追加します（左から右）。演算を見つけたら、スタックから期待するオペランドの数を抽出し、小さなツリーを元に戻します。それを終了すると、スタックに結果が1つだけ表示されます。それは、最終的なグラフです。

元：

x y z +  ->  x   +
               /  \
              y    z
于 2010-10-14T01:47:17.840 に答える