Преобразовать вектор дерева префикса выражений в вектор дерева выражений ORF / Karva - PullRequest
Новая
       58

Преобразовать вектор дерева префикса выражений в вектор дерева выражений ORF / Karva

1 голос
/ 06 июня 2011

Хорошо, это немного сложнее.

У меня есть набор кода, который принимает деревья выражений, такие что:

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

сохраняетсяв векторе (я использую C ++, но мне просто нужен алгоритм) в форме префикса:

+(/(+(a,b),+(c,d)),sqrt(e)) // Скобки просто для того, чтобы помочь вам прочитать это.Каждый оператор и терминал является элементом вектора.

Теперь есть еще один способ представления дерева выражений, известный как форма ORF

(Третья страница статьи: http://arxiv.org/ftp/cs/papers/0102/0102027.pdf)

В этой форме вы представляете деревокак будто читая дерево слева направо, сверху вниз.

((a + b)/(c + d) + sqrt(e)) теперь становится:

+/sqrt++eabcd

То, что я не смог сделать, это создатьалгоритм, который может конвертировать:

+/sqrt++eabcd // ORF в:
+(/(+(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;
}
}

Заранее благодарен за любую помощь! Это делает мою голову. О, и это критично для производительности: (

Ответы [ 2 ]

2 голосов
/ 06 июня 2011

Моя стратегия состоит в том, чтобы построить дерево разбора, а затем обойти его по глубине, чтобы создать префиксную нотацию.

Вы можете построить дерево разбора из ORF с помощью очереди. Когда вы встретите каждого оператора (или термин), сделайте его дочерним по отношению к оператору во главе очереди. Когда у узла в начале очереди достаточно дочерних элементов, вытолкните его из очереди.

В вашем примере ... Начните с + и поместите его в очередь (особый случай для начального элемента).

Следующий процесс /. Поскольку + в начале очереди не имеет дочерних элементов (но нуждается в двух), вы присоединяете / к + в качестве первого дочернего элемента и помещаете / в очередь. Так что теперь очередь выглядит так: 

+/

... и дерево выглядит как 

      +
    /   .
  .   .

... где "." элемент, ожидающий заполнения.

Далее следует sqrt. Поскольку + находится в начале очереди и еще не имеет двух дочерних элементов, присоедините sqrt к + и вставьте sqrt в очередь. Так что теперь очередь выглядит так: 

+/sqrt

... и дерево выглядит как 

      +
    /   sqrt
  .   .   .

Далее идет вторая +. Глава очереди - первый +, но теперь у него уже есть все его дети. Так что выкинь это из очереди. Следующим элементом очереди является /, и у него еще нет дочерних элементов, поэтому этот + становится его дочерним элементом и переходит в конец очереди. Очередь теперь гласит: 

/sqrt+

... а дерево сейчас: 

      +
    /    sqrt
  +   .    .
.   .

Затем третий + становится вторым дочерним элементом / и помещается в очередь. Так что очередь будет: 

/sqrt++

... и дерево будет (извините, моя ASCII-графика слаба): 

      +
     /    sqrt
  +    +    .
 . .  . .

Теперь / удовлетворен, поэтому, когда вы нажимаете e, вы вытаскиваете / из очереди. Теперь sqrt является началом очереди, поэтому e привязывается к этому. Очередь сейчас: 

sqrt++

... а дерево есть: 

      +
     /    sqrt
  +    +    e
 . .  . .

Следующие четыре итерации, очевидно, присваивают a, b, c, d оставшимся листьям, давая вам ваше дерево разбора.

Кстати,

std::dequeue - это идеальная структура данных для очереди.

0 голосов
/ 06 июня 2011

Просто создайте дерево 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)

Когда вы строите T из ORF, сохраняйте указатель влево и вправо, который говорит вам о первом узле, который вы должны заполнить в дереве выражений, а справа - о последнем узле.

...