CODEWITHSUNDEEP
c++algorithmexpression-treesprefix-tree
Forthright
Forthright

Reputation: 199

Convert a prefix expression tree vector to a ORF/Karva notation expression tree vector

Ok, this is a bit of a tricky one.

I have a bunch of code that takes expression trees such that:

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

is stored in a vector (I'm using C++ but I just need the algorithm) in the prefix form:

+(/(+(a,b),+(c,d)),sqrt(e)) //Brackets are just to help you read it. Each operator and terminal is an element in the vector.

Now there is this other means of representing an expression tree known as ORF form

(Third page of the paper: http://arxiv.org/ftp/cs/papers/0102/0102027.pdf)

In this form you represent the tree as if reading the tree from left to right, top to bottom.

((a + b)/(c + d) + sqrt(e)) now becomes:

+/sqrt++eabcd

What I have been failing to do is create an algorithm that can convert:

+/sqrt++eabcd //ORF into:
+(/(+(a,b),+(c,d)),sqrt(e)) //Prefix

All I have so far is some code to get the breadth of the tree at different levels:

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;
}
}

Thanks in advance for any help! This is doing my head in. Oh, and this is performance critical :(

Upvotes: 1

Views: 1189

Answers (2)

Matei Gruber
Matei Gruber

Reputation: 189

Just build a tree T. Each node is a tuple (terminal,) or (unary_operator, operand) or (binary_operator, first_operand, second_operand). The operands themselves indexes of nodes in the tree.

For instance, the expression a + (b / c), would have the tree T[0] = (+, 1, 2), T[1] = (a,), T[2] = (/, 3, 4), T[3] = (b,), T[4] = (c,). Once you have this just do a preorder. Here's the Python code for this.

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)

When you build T from your ORF, keep a left and right pointer which tells you the first node you have to fill in in your expression tree, and right tells you the last node.

Upvotes: 0

Nemo
Nemo

Reputation: 71615

My strategy would be to build the parse tree, then walk it depth-first to generate prefix notation.

You can build the parse tree from ORF with a queue. As you encounter each operator (or term), make it a child of the operator at the head of the queue. When the node at the head of the queue has enough children, pop it off of the queue.

In your example... Start with the + and push it onto the queue (special case for initial element).

Next process the /. Since the + at the head of the queue has no children (but needs two), you attach the / to the + as its first child and push the / onto the queue. So now the queue looks like:

+/

...and the tree looks like

      +
    /   .
  .   .

...where "." is an element waiting to be filled in.

Next comes the sqrt. Since + is at the head of the queue and does not have two children yet, attach the sqrt to the + and push the sqrt onto the queue. So now the queue looks like:

+/sqrt

...and the tree looks like

      +
    /   sqrt
  .   .   .

Next comes the second +. The head of the queue is the first +, but now that has all of its children already. So pop it off the queue. The next element of the queue is the /, and it has no children yet, so this + becomes its child and goes onto the back of the queue. Queue now reads:

/sqrt+

...and tree is now:

      +
    /    sqrt
  +   .    .
.   .

Next the third + becomes the second child of the / and gets pushed onto the queue. So the queue will be:

/sqrt++

...and the tree will be (sorry, my ASCII art is weak):

      +
     /    sqrt
  +    +    .
 . .  . .

Now the / is satisfied, so when you hit the e, you pop the / off of the queue. Now the sqrt is the start of the queue, so the e gets attached to that. Queue is now:

sqrt++

...and tree is:

      +
     /    sqrt
  +    +    e
 . .  . .

The next four iterations obviously assign a,b,c,d to the remaining leaves, giving you your parse tree.

std::dequeue is a perfect data structure to use for the queue, by the way.

Upvotes: 2

Related Questions