1

わかりました、これは少しトリッキーなものです。

次のような式ツリーを取得するコードがたくさんあります。

((a + b)/(c + d) + sqrt(e))

プレフィックス形式のベクトル（C ++を使用していますが、アルゴリズムが必要です）に格納されます。

+(/(+(a,b),+(c,d)),sqrt(e))//角かっこは読みやすくするためのものです。各演算子と端末は、ベクトルの要素です。

これで、ORFフォームと呼ばれる式ツリーを表す他の方法があります。

（論文の3ページ目：http：//arxiv.org/ftp/cs/papers/0102/0102027.pdf）

このフォームでは、ツリーを左から右、上から下に読んでいるかのようにツリーを表現します。

((a + b)/(c + d) + sqrt(e))今になる：

+/sqrt++eabcd

私が失敗しているのは、変換できるアルゴリズムを作成することです。

+/sqrt++eabcd// ORF into：
+(/(+(a,b),+(c,d)),sqrt(e))//プレフィックス

これまでに持っているのは、さまざまなレベルでツリーの幅を取得するためのコードだけです。

bool ConvertPrefixToORF(const std::vector<Node> & individual,
                              std::vector<Node> & ETindividual){
bool all_terminal = false;
int breadth;
int breadthOfDepth[individual.size()];
int depthCounter = 0;
breadthOfDepth[0] = 1;
//Resize only once.
ETindividual.reserve(individual.size());

while (all_terminal == false) {
    //Reset breadth
    breadth = 0;
    //Iterate over next level and calculate depth of level after that.
    for (int i = 0; i < breadthOfDepth[depthCounter]; i++) {
        all_terminal = true;
        //If the individual is a function...
        if (individual[current+i].isFunction()) {
            //Get individual from i'th item at this depth
            function f = individual[current + i];
            //Increment breadth of next level with arity
            breadth += f->getArity();
            //if a single function is found
            all_terminal = false;
        }
    }
    //Go down a level in the tree.
    depthCounter++;
    //Set the breadth of that tree depth:
    breadthOfDepth[depthCounter] = breadth;
}
}

助けてくれてありがとう！これは私の頭を使っています。ああ、これはパフォーマンスが重要です:(

4

2 に答える 2

2

私の戦略は、解析ツリーを構築し、それを深さ優先でウォークしてプレフィックス表記を生成することです。

キューを使用してORFから解析ツリーを構築できます。各演算子（または用語）に遭遇したら、それをキューの先頭にある演算子の子にします。キューの先頭にあるノードに十分な子がある場合は、キューからポップします。

あなたの例では...から始めて、+それをキューにプッシュします（最初の要素の特別な場合）。

次のプロセス/。キューの+先頭に子がないため（ただし2つ必要）、を最初の子としてにアタッチし、/をキュー+にプッシュし/ます。したがって、キューは次のようになります。

+/

...そして木は次のようになります

      +
    /   .
  .   .

...どこ "。" が入力されるのを待っている要素です。

次はsqrt。+はキューの先頭にあり、まだ2つの子がないため、をに接続し、をsqrtキュー+にプッシュしsqrtます。したがって、キューは次のようになります。

+/sqrt

...そして木は次のようになります

      +
    /   sqrt
  .   .   .

次は2番目+です。キューの先頭が最初+ですが、現在はすべての子がすでに存在しています。だからそれをキューから外します。キューの次の要素はであり、/まだ子がないため、+これが子になり、キューの最後に移動します。キューは次のようになります。

/sqrt+

...そしてツリーは今：

      +
    /    sqrt
  +   .    .
.   .

次に、3番目+はの2番目の子になり/、キューにプッシュされます。したがって、キューは次のようになります。

/sqrt++

...そしてツリーは次のようになります（申し訳ありませんが、私のASCIIアートは弱いです）：

      +
     /    sqrt
  +    +    .
 . .  . .

これ/で満足できるので、を押すとキューからeポップします。/これでsqrtキューの開始点になるので、eに接続されます。キューは次のようになりました。

sqrt++

...そしてツリーは：

      +
     /    sqrt
  +    +    e
 . .  . .

次の4回の反復では、明らかに残りの葉にa、b、c、dが割り当てられ、解析ツリーが得られます。

std::dequeueちなみに、はキューに使用するのに最適なデータ構造です。

于 2011-06-06T00:38:07.533 に答える
0

ツリーTを作成するだけです。各ノードはタプル(terminal,)または(unary_operator, operand)または(binary_operator, first_operand, second_operand)です。オペランド自体は、ツリー内のノードのインデックスです。

たとえば、式a + (b / c)は、ツリーを持ちますT[0] = (+, 1, 2), T[1] = (a,), T[2] = (/, 3, 4), T[3] = (b,), T[4] = (c,)。これを入手したら、事前注文を行うだけです。これがこのためのPythonコードです。

def preorder(T, i):
  X = [T[i][0]]
  if len(T[i]) > 1:
    X.extend(preorder(T, T[i][1]))
  if len(T[i]) > 2:
    X.extend(preorder(T, T[i][2]))
  return X

def convert(A):
  binary_operators = ['+', '-', '/']
  unary_operators = ['sqrt']
  left = 0
  right = 0
  T = dict([(i, ()) for i in range(len(A))])
  for a in A:
    if a in binary_operators:
      T[left] = (a, right + 1, right + 2)
      right += 2
    elif a in unary_operators:
      T[left] = (a, right + 1)
      right += 1
    else:
      T[left] = (a,)
    left += 1
  return preorder(T, 0)

def main(argv=None):
  A = ['+', '/', 'sqrt', '+', '+', 'e', 'a', 'b', 'c', 'd']
  print convert(A)

ORFからTを作成するときは、式ツリーに入力する必要のある最初のノードを示す左右のポインターを保持し、右は最後のノードを示します。

于 2011-06-06T11:21:31.777 に答える