CS162 MP9 - Memory management

Application programming that uses dynamic memory management

Our application program will use the malloc() library function, in contrast to the usual system programs that we have written so far that makes system calls (via library functions).

Write an application program "exprtree.c" that, during run time, dynamically builds an expression tree and evaluates this tree to obtain a numerical value of the expression. The program is invoked as follows:

./exprtree INPUTFILE.TXT

where INPUTFILE.TXT is a plain Unix text file that contains details of the nodes of the expression tree.  For example, for the expression tree:

   +
  / \
25   *
     / \
  17   9

the contents of INPUTFILE.TXT are as follows:

1  OPERATORPLUS   ->2   ->3
2  OPERAND           25.0
3  OPERATORTIMES ->4   ->5
4  OPERAND           17.0
5  OPERAND           9.0

The allowable operators are OPERATORPLUS, OPERATORMINUS, OPERATORNEGATE, OPERATORTIMES, OPERATORDIViDE.  The operands must be of type "long double". You will probably need the following struct for your nodes:

struct node {
  enum nodetype { OPERAND=1, OPERATORPLUS, OPERATORMINUS, FillOutTheRest } op;
  union {
    struct leafptr {
      struct node *left;
      struct node *right;
    } ptr;
    long double nodeval;
  }
}

Your program should dynamically allocate nodes as needed, depending on the contents of INPUTFILE.TXT.  The contents of this file may change from one run of the program to another run.

After the expression tree is built in memory, your program should evaluate the tree, possibly by doing a postorder traversal of the tree, and then print the resulting long double value computed.

Deadline: Today, Feb 15, 2010 before 4:30PM, by email to prmanalastas@gmail.com. The usual file naming convention lastnameFirstname-mp9-evaltree.zip applies.