CMPS 12M
Introduction to Data Structures Lab Lab Assignment 5
The goal of this assignment is to learn how to use the tree data type to implement Expression Trees. An Expression tree is a binary tree in which each internal node corresponds to operator.
To build an expression tree you will accept input in post-fix notation, also known as Reverse Polish Notation (RPN) which scientific calculators continue to use. The post-fix notation is also the post-order tree traversal which for the above tree is:
7 8 10 – 2 * +
Evaluation of the expression tree is: 7 + ((8-10)*2) = 3
This program you will construct the Expression Tree using a stack and this algorithm:
Loop through input expression and do following for every token (a set of non-whitespace characters)
If token is operand push that into stack
If token is operator pop two nodes from stack make them its child and push current node again.
At the end only element of stack will be root of expression tree.
You will be given the function that constructs the Expression Tree from white space delimited post-fix notation expression. The final PostFixCalculator program will build the Expression Tree the print the in- order traversal with parenthesis (including each integer argument to make things easier), then print the evaluation of the expression. The calculator will accept only integer values and the arithmetic operators:
+, -, *, /.
An example execution will look like:
7 8 10 - 2 * + (this is the input value to your program)
((7)+(((8)-(10))*(2))) = 3 (this is the output from your program)
Your program should create the output line with the in-order expression traversal with complete parenthesis, followed by an equal symbol and the evaluation of the expression. No spaces in the expression output and one space on either side of the equals symbol. Another goal of this lab is to understand the difference between strings and integers. The program you will write accepts input as strings and then does a conversion to integers and enumeration type and then makes arithmetic operations based on the enumeration type.
The program only needs to handle the maximum sized integer values, anything else will cause integer overflow. Input will be read until a EOF marker is detected, also know an CONTROL-D in UNIX systems.
The implementation you are given uses as stack to build a tree according to the algorithm listed above. The stack implementation you are provided with is a stack of void * pointers which means that the stack can hold references to any kind of object. It is not bound to the kind of items are stored in the stack. This typical of the C language approach to abstraction. It does however rely on the competency of the programmer. There is no type checking of items added to the stack. The programmer overrides the compiler’s type checking system and casts the pointer to the right type. So it is the programmers responsibility to ensure that the stack’s use is managed by type. If you review the calls to the stack operation you’ll notice the casting of items that are pushed and popped.
What you will be given:
Makefile - which creates the PostFixCalculator executable ExpTree.h
ExpTree.c - with two unimplemented functions ExpTreeClient.c
Stack.h Stack.c
You must implement inorderTraverse, expressionEval and create comments for all the code you write and comment all the code you receive. While commenting the code you will get a chance to test your understanding of the implementation. This code is intentionally given to you without comments.
You have to design your own test cases to evaluate your logic.
What to Turn In
Submit lab5.zip that contains the lab5 directory. You will need to implement the -The lab5 directory should contain:
README
Makefile ExpTree.h
ExpTree.c - with two unimplemented functions Stack.h
Stack.c
As always start early and ask for help if anything is not completely clear.
