CSIS3475 Assignment 4: Expression Trees and Heaps

This is a homework assignment for CSIS3475, requiring students to develop a Java application. Task 1 involves constructing an expression tree from a postfix expression using stacks and a doubly linked list. Task 2 requires implementing an array-based heap with methods for creation, emptiness check, insertion, and deletion. Students must submit their complete Java project by April 3rd, 2017, with comments explaining the logic of their code. The assignment is worth 20 points and is an individual effort.

CSIS3475-070 Winter 2017
Assignment# 4
Due date: Monday April 3rd, 2017
Total scores: 20
Note: Please submit your assignment on the blackboard course web page. There are
maximum three attempts, latest attempt will be graded. This is individual student work,
please submit your own work.
In case of cheating both copy and copied will get zero and violations of Academic Integrity
policy will be reported to the appropriate Responsible Administrator for adjudication.
For this application, don’t forget to add comments to explain logic of your code. Please
submit your complete Java project, MS word documents will not be accepted and will not
be graded.
Task 1 (10 Points):
Create a Java application to construct an expression (binary) tree from the postfix expression
using Stacks. Note: Construct trees using stacks. For this task, create a binary tree using
doubly linked list. Doubly linked list class should be created from scratch and for stack class,
you can use JCF Stack class. Write a program to demonstrate.
Task 2 (10 Points):
Write a Java program for array-based implementation of a heap. Create following basic
methods:
createHeap() // Creates an empty heap.
heapIsEmpty() // Determines whether a heap is empty.
heapInsert(newItem) // Inserts newItem into a heap.
heapDelete() // Retrieves and then deletes a heap’s root item.
Write a program to demonstrate these methods. For reference, have a look at the array-
based implementation of a heap textbook page 669 – 673.