About Trees and Prefix (Polish) Notation?

Question

My MIPS Assembly class required me to read in an expression of unknown size into a Parse Tree. I've never had to deal with trees, so this is how I went around storing values:

Lets say the user entered the expression 1 + 3 - 4 (each operand could only be a digit 1-9)

My leftmost child node would be the starting point and contain 2 pieces of data

1. The operand
2. Pointer to the next node (operator)

This is how I constructed the tree. I would point from operand to operator to next operand to next operator until there were no more values left to be read in.

My next task was to traverse the tree recursively and output the values in infix/prefix/postfix notation.

Infix traversal was no problem considering how I constructed my tree.

I'm stuck on the prefix. Firstly, I don't fully understand it.

When I output our expression (1 + 3 - 4) in prefix should it come out - + 1 3 4? I'm having trouble following the online examples.

Also do you think my tree is constructed properly? I mean, I have no way to go to a previous node from the current node which means I always have to begin traversal from the leftmost child node which instinctively doesn't sound right even though my TA said that was the way to go.

Thank you for any help.

Answer 1

In general you should construct a tree in such a way that all the leaf nodes (those with no children) are operands, and the internal nodes (everything else) are operators. This should be so that the children of an operator node are its operands, or themselves operators which have operands. If you can construct a tree in this way, Forming the various notations (prefix, postfix, infix) are fairly simple -- You just follow the preorder, postorder and inorder traversals of the tree, for which there are well known algorithms.

As far as I can tell, you're not constructing a tree, rather a linked-list, and this isn't going to serve you well. You have 2 different entities -- operands and operators -- you have to treat them differently.

Answer 2

I agree with what sykora says. I would like to add that you can also use a stack in this case. If your assignment requires you to specifically use a tree, then sykora's suggestion would work best. However, a stack might be easier to program for simple expression evaluation.

Answer 3

Your parse tree should look something like this:

        '-'
         |
     +---+---+
     |       |
    '+'     '4'
     |
 +---+---+
 |       |
'1'     '3'

Each node has two pointers. One to its left child and one to its right child. There is no need for pointers to parent nodes, when using recursive traversal.

Here's some pseudocode:

Traversal for infix notation:

void traverse(Node *node) {
    if (node->leftChild != 0) {
        traverse(node->leftChild);
    }

    print(node->value);

    if (node->rightChild != 0) {
        traverse(node->rightChild);
    }
}

Traversal for prefix notation:

void traverse(Node *node) {
    print(node->value);

    if (node->leftChild != 0) {
        traverse(node->leftChild);
    }

    if (node->rightChild != 0) {
        traverse(node->rightChild);
    }
}

Traversal for postfix notation:

void traverse(Node *node) {
    if (node->leftChild != 0) {
        traverse(node->leftChild);
    }

    if (node->rightChild != 0) {
        traverse(node->rightChild);
    }

    print(node->value);
}

You would call the traverse method with the root node of your tree.

Your Node data structure would need three members:

struct Node {
    char value;
    Node *leftChild;
    Node *rightChild;
}

The leaves of the tree would contain null pointers for leftChild and rightChild.

Sometimes it helps to write this stuff in a higher level language (whatever you feel comfortable with) to understand the problem and then "translate" this code to assembler. I remember programming a blocks world simulation in MIPS assembler like this.

Answer 4

This is an instance of the general problem of compiling, which is a solved problem. If you do a google on compiling techniques, you will find out all kinds of information relating to your problem.

Your library should have a copy of Compilers: Principles, Techniques, and Tools by Aho, Sethi, and Ullman. If it doesn't have it, request it for purchase(it's the Standard Work in the field). The first part of it should help you.

Third edition link