C Exercises 4

Create a POSTFIX tree

Here is an example of a postfix expression:

          12+34*+

This is equivalent to the infix expression:

          (1+2)+(3*4)

A postfix expression composed of only single digit characters can be easily stored as a C array:

         char postfix[] = "12+34*"

Write a function which will accept a postfix string and create an expression tree corresponding to that postfix expression. The function should return the address of the root node of the expression tree.

What is an expression tree?

The expression tree for the postfix expression "12+" is:

                     +
                    /  \
                   1    2

That is, the root node holds '+', and the left and right nodes hold '1' and '2'.

The expression tree for "12+3*" is:

                    *
                  /   \
                  +    3
                 / \
                 1  2

The leaf nodes of an expression tree are all numbers and the internal nodes are all operators.

Hint: The stack based algorithm to evaluate a postfix string can be easily modified to create a postfix tree. The stack should be modified to hold pointers to nodes (instead of numbers).